试设计一个解最大团问题的迭代回溯算法.

迭代法的一个缺点是算法的逻辑结构复杂。()

算法是为解决某个问题而设计的步骤和方法。以下关于算法的叙述中，不正确的是 (52)。

A.解决同一个问题，不同的人（甚至是同一个人）可能会写出几种不同的算法

B.常用算法主要有迭代法、穷举搜索法、递推法、递归法、贪婪法、回溯法等

C.递推法是利用所解问题本身所具有的递推关系来求得问题解的一种算法

D.任何可以用递推法解决的问题，亦可用递归法解决，反之亦然

图5-16a给出了一个赋权网络，用迭代算法求值为12的最小费用流。

 

设LP有最优解，用单纯形法迭代到某步出现退化的基可行解，但尚未达到最优，并且只有一个基变量取零值．试证明：这个基可行解在以后的迭代过程中(即使采用最大检验数规则确定进基变量)必然会转移，且转移后不会再现．

设线性方程组

试考察解此方程组的雅可比迭代法及高斯一塞德尔迭代法的收敛性。

遗传算法是一种算法设计策略。不同的问题甚至相同的问题都可以设计不同的遗传算法进行求解，不同的遗传算法如可能解编码的不同、交叉与变异规则的不同、概率模型的选择不同等。

(1)如何衡量遗传算法的性能好坏，下列说法正确的是 _____。

(A)对一些已知最优解的问题类别， 可以通过精确算法获得最优解， 然后使用“近似率”来衡量解的质量。所谓近似率是指算法求得的解与问题最优解的近似程度。则有：近似率越高的遗传算法，性能越好;

(B)对理论最优解不知道的问题类别，可以通过不同遗传算法在相同问题实例集上测试结果的横向比较来进行评价，即有：在执行相同次数的迭代后，获得满意解越好的遗传算法，性能越好;

(C)对于具有迭代特征的近似算法，在迭代多少次后能够使得结果稳定 (通俗来讲，即结果不再随进一步迭代而发生变化或发生极小的可以被忽略的变化 )—这被称为收敛速度，它从一定程度反映了算法求解的“快慢”。在达到期望的满意解的前提下，迭代次数越少越好。

(D)遗传算法不一定能够得到满意解。 因此，当不同算法均应用多次后，求得满意解次数越多的算法越好!

(E)除上述衡量性能的指标外，还有其他的指标来衡量性能。

(2)如何衡量遗传算法的性能好坏，下列说法不正确的是 _____。

(A)近似率越高的算法，性能越好;

(B)在执行相同次数的迭代后，获得满意解越好的算法，性能越好;

(C)在达到期望满意解的前提下，迭代次数越多的算法，性能越好;

(D)当不同算法均应用多次后，求得满意解次数越多的算法，性能越好!

(3)如何衡量遗传算法的性能好坏，下列说法不正确的是 _____。

(A)近似率越低的算法，性能越好;

(B)在执行相同次数的迭代后，获得满意解越好的算法，性能越好;

(C)在达到期望满意解的前提下，迭代次数越少的算法，性能越好;

(D)当不同算法均应用多次后，求得满意解次数越多的算法，性能越好!

试求初值问题

的Picard迭代序列，并通过求迭代序列的极限求出初值问题的解，这里P(t)，Q(t)均为连续函数．

试证：在原仿射尺度算法的迭代公式x^(k+1)=x^(k)+α_kd^(k)中的步长系数若取为，则当迭代点x^(k+1)的某分量x_j^(k+1)=0时，x^(k+1)必为L的最优解．

3．试证：在原仿射尺度算法的迭代公式x^(k+1)=x^(k)+α_kd^(k)中的步长系数若取为，则当迭代点x^(k+1)的某分量x_j^(k+1)=0时，x^(k+1)必为L的最优解．

若将森林中的每棵树视作一个等价类，则Kruskal算法迭代过程所涉及的计算不外乎两类：

支持以上操作接口的数据结构，即所谓的独立集(disjoint set)，亦称作并查集(union-find set)。

a)试基于此前介绍过的基本数据结构实现并查集，并用以组织Kruskal算法中的森林;

b)按你的实现，find()和union()接口的复杂度各是多少?相应地，Kruskal算法的复杂度呢?