否则分A为两个(或多个)子集:A=4A,4∩A2=④,解相应的松弛间题:mnf(x)J=2 若XB∈A,则A1问题已解决(否则,对A1重复A的过程)。同样若XB∈A2,则A2问题已解决, 从而min{f(XB),(XB)即为所求最小值。若XB∈4而BA2(但f(X)≥f(Xx)),则 A2亦不必考虑了;否则,对A2继续实行如同A的步骤,如此进行,直到求得最优值为止(∫取最 小的子集先考虑 (IV)旅行商问题和最小调整法 设有n个城市,C1,…,Cn,由C到C的路程dn为已知,一旅行商为了推销货物,从一城市 (如C1)出发,要经过所有城市,且每个城市正好经过一次,然后回到出发点。问题是如何选择 条最优路线。容易看出,旅行商有(n-1)!种方案可供选择,对于n=21这个不大的数目,就有 20!种方案,20!是个天文数字,即使用高速计算机也无法处理这一问题。这类问题至今没有有效 算法,甚至连有效的近似算法(JA)-1≤a,a>0与集合1无关)亦没有,被称为NP困难(完 fopr (n) 全)问题。 但是上述问题有着广泛的实际背景和深刻的经济含义,例如,在计算机的集成电路的设计中就 出现这一问题,还包括派车,排序,底板布线,考古学中的排号,自动钻井,工件加工顺序,邮局 到各个邮箱开箱收信,以及去各分局送邮件等其它许多方面。所有这些需要又促使我们不得不研究 它的解法。下面考虑用最小调整法来求解。 最小调整法的思想和步骤如下: 旅行商问题的关系矩阵为A A 其中元素an表示由第ⅰ个城市到第j个城市的路程 (1°)取每列的一个最小值,画圈,得一最小方案。若这些画圈元素又分属于不同行,则得到 相应分派问题的最优解,转(3°);否则转(2°)。 (2°)应把有二个以上画圈元素的行中的一个改画到同列的别处,待到某一无圈行中有一元素 画上圈,则算一次调整。如此进行,直到每行均有一个画圈元素时为止,然后转入 (3°)即可。而每次调整均以目标函数(其值为各画圈元素之和)增值最小为原则。 (3°)如果从1°或2°得到的分派问题最优解元素的任一行指标i出发,先到其列指标j,接着 从以j为行指标的元素出发,再到其列指标,如此进行下去,最后回到以i为列指标的元素止,便 形成一个圈,若圈中的元素恰为n个,则所得方案即为最优方案;否则,便会形成两个以上的子圈, 它不是最优解,需进行再调整,转(4°) (4)以增值最小的原则实行对调调整,所谓对调调整,就是于任二子圈中各取一个元素,如an14 否则分 A 为两个（或多个）子集： 1 2 1 2 A A A A A =   =  , ，解相应的松弛问题： min ( ) 1,2 X Bj f X j  = ； 若 1 1 o X A B  ，则 A1 问题已解决（否则，对 A1 重复 A 的过程）。同样若 2 2 o X A B  ，则 A2 问题已解决， 从而 1 2 0 0 min{ ( ), ( )} B B f X f X 即为所求最小值。若 1 1 o X A B  而 2 2 o X A B  （但 2 1 ( ) ( ) B B f X f X    ），则 A2 亦不必考虑了；否则，对 A2 继续实行如同 A 的步骤，如此进行，直到求得最优值为止（ f 取最 小的子集先考虑）。 （IV）旅行商问题和最小调整法 设有 n 个城市，C1，···，Cn，由 Ci 到 Cj 的路程 ij d 为已知，一旅行商为了推销货物，从一城市 （如 C1）出发，要经过所有城市，且每个城市正好经过一次，然后回到出发点。问题是如何选择一 条最优路线。容易看出，旅行商有（n－1）！种方案可供选择，对于 n＝21 这个不大的数目，就有 20！种方案，20！是个天文数字，即使用高速计算机也无法处理这一问题。这类问题至今没有有效 算法，甚至连有效的近似算法（ ( ) 1 , 0 ( ) A opt f I f I −     与集合 I 无关）亦没有，被称为 NP-困难（完 全）问题。 但是上述问题有着广泛的实际背景和深刻的经济含义，例如，在计算机的集成电路的设计中就 出现这一问题，还包括派车，排序，底板布线，考古学中的排号，自动钻井，工件加工顺序，邮局 到各个邮箱开箱收信，以及去各分局送邮件等其它许多方面。所有这些需要又促使我们不得不研究 它的解法。下面考虑用最小调整法来求解。 最小调整法的思想和步骤如下： 设旅行商问题的关系矩阵为 A 12 1 1 21 2 2 1 2 1 2 j n j n i i ij in n n nj a a a a a a A a a a a a a a       =    其中元素 ij a 表示由第 i 个城市到第 j 个城市的路程。 （1º）取每列的一个最小值，画圈，得一最小方案。若这些画圈元素又分属于不同行，则得到 相应分派问题的最优解，转（3º）；否则转（2º）。 （2º）应把有二个以上画圈元素的行中的一个改画到同列的别处，待到某一无圈行中有一元素 画上圈，则算一次调整。如此进行，直到每行均有一个画圈元素时为止，然后转入 （3º）即可。而每次调整均以目标函数（其值为各画圈元素之和）增值最小为原则。 （3º）如果从 1º或 2º得到的分派问题最优解元素的任一行指标 i 出发，先到其列指标 j，接着 从以 j 为行指标的元素出发，再到其列指标，如此进行下去，最后回到以 i 为列指标的元素止，便 形成一个圈，若圈中的元素恰为 n 个，则所得方案即为最优方案；否则，便会形成两个以上的子圈， 它不是最优解，需进行再调整，转（4º）。 （4º）以增值最小的原则实行对调调整，所谓对调调整，就是于任二子圈中各取一个元素，如 ij a