动态规划算法基本思想
<P>和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。<BR><BR>例3-1 [最短路经] 考察图1 2 - 2中的有向图。假设要寻找一条从源节点s= 1到目的节点d= 5的最短路径，即选择此路径所经过的各个节点。第一步可选择节点2，3或4。假设选择了节点3，则此时所要求解的问题变成：选择一条从3到5的最短路径。如果3到5的路径不是最短的，则从1开始经过3和5的路径也不会是最短的。例如，若选择的子路径（非最短路径）是3，2，5 (耗费为9 )，则1到5的路径为1，3，2，5 (耗费为11 )，这比选择最短子路径3，4，5而得到的1到5的路径1，3，4，5 (耗费为9) 耗费更大。<BR><BR>所以在最短路径问题中，假如在的第一次决策时到达了某个节点v，那么不管v 是怎样确定的，此后选择从v 到d 的路径时，都必须采用最优策略。<BR><BR>例3-2 考察1 3 . 4节的0 / 1背包问题。如前所述，在该问题中需要决定x1 .. xn的值。假设按i = 1，2，.，n 的次序来确定xi 的值。如果置x1 = 0，则问题转变为相对于其余物品（即物品2，3，.，n），背包容量仍为c 的背包问题。若置x1 = 1，问题就变为关于最大背包容量为c-w1 的问题。现设r?{c，c-w1 } 为剩余的背包容量。<BR><BR>在第一次决策之后，剩下的问题便是考虑背包容量为r 时的决策。不管x1 是0或是1， 必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案，因而是一个更好的方案。<BR><BR>假设n=3, w=, p=, c= 11 6。若设x1 = 1，则在本次决策之后，可用的背包容量为r= 116-100=16 。= 符合容量限制的条件，所得值为1 5，但因为= 同样符合容量条件且所得值为1 8，因此 = [ 0，1] 并非最优策略。即x= [ 1，0，1] 可改进为x= [ 1，1，0 ]。若设x1 = 0，则对于剩下的两种物品而言，容量限制条件为11 6。总之，如果子问题的结果不是剩余情况下的一个最优解，则也不会是总体的最优解。<BR><BR>例3-3 [航费] 某航线价格表为：从亚特兰大到纽约或芝加哥，或从洛杉矶到亚特兰大的费用为$ 1 0 0；从芝加哥到纽约票价$ 2 0；而对于路经亚特兰大的旅客，从亚特兰大到芝加哥的费用仅为$ 2 0。从洛杉矶到纽约的航线涉及到对中转机场的选择。如果问题状态的形式为（起点，终点），那么在选择从洛杉矶到亚特兰大后，问题的状态变为（亚特兰大，纽约）。从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约，票价$ 1 0 0。而使用直飞方式时，从洛杉矶到纽约的花费为$ 2 0 0。不过，从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约，其总花费为$ 1 4 0（在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径：亚特兰大-芝加哥-纽约）。<BR><BR>如果用三维数组（t a g，起点，终点）表示问题状态，其中t a g为0表示转飞， t a g为1表示其他情形，那么在到达亚特兰大后，状态的三维数组将变为（ 0，亚特兰大，纽约），它对应的最优路径是经由芝加哥的那条路径。<BR><BR>当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程（ d y n a m i c -programming recurrence equation），它可以帮助我们高效地解决问题。<BR><BR>例3-4 在例3 - 2的0 / 1背包问题中，最优决策序列由最优决策子序列组成。假设f (i,y) 表示例1 5 - 2中剩余容量为y，剩余物品为i，i + 1，.，n 时的最优解的值，即：和利用最优序列由最优子序列构成的结论，可得到f 的递归式。f ( 1 ,c) 是初始时背包问题的最优解。可使用（ 1 5 - 2）式通过递归或迭代来求解f ( 1 ,c)。从f (n, * )开始迭式， f (n, * )由（1 5 - 1）式得出，然后由（ 1 5 - 2）式递归计算f (i,*) ( i=n- 1，n- 2，.， 2 )，最后由（ 1 5 - 2）式得出f ( 1 ,c)。<BR><BR>对于例1 5 - 2，若0≤y＜1 0，则f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用递归式（1 5 - 2），可得f (2, y) = 0 ( 0≤y＜10 )；f（2，y）= 1 5（1 0≤y＜1 4）；f（2，y）= 1 8（1 4≤y＜2 4）和f（2，y）= 3 3（y≥2 4）。因此最优解f ( 1 , 11 6 ) = m a x {f（2，11 6），f（2，11 6 - w1）+ p1} = m a x {f（2，11 6），f（2，1 6）+ 2 0 } = m a x { 3 3，3 8 } = 3 8。<BR><BR>现在计算xi 值，步骤如下：若f ( 1 ,c) =f ( 2 ,c)，则x1 = 0，否则x1 = 1。接下来需从剩余容量c-w1中寻求最优解，用f (2, c-w1) 表示最优解。依此类推，可得到所有的xi (i= 1.n) 值。<BR><BR>在该例中，可得出f ( 2 , 11 6 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接着利用返回值3 8 -p1=18 计算x2 及x3，此时r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此时r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。<BR><BR>动态规划方法采用最优原则（ principle of optimality）来建立用于计算最优解的递归式。所谓最优原则即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。由于对于有些问题的某些递归式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。若不能保持最优原则，则不可应用动态规划方法。在得到最优解的递归式之后，需要执行回溯（t r a c e b a c k）以构造最优解。<BR><BR>编写一个简单的递归程序来求解动态规划递归方程是一件很诱人的事。然而，正如我们将在下文看到的，如果不努力地去避免重复计算，递归程序的复杂性将非常可观。如果在递归程序设计中解决了重复计算问题时，复杂性将急剧下降。动态规划递归方程也可用迭代方式来求解，这时很自然地避免了重复计算。尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免重复计算的递归程序更快。<BR></P>分枝定界算法基本思想
<P>分枝定界（branch and bound）是另一种系统地搜索解空间的方法，它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成E-节点。当一个节点变为E-节点时，则生成从该节点移动一步即可到达的所有新节点。在生成的节点中，抛弃那些不可能导出（最优）可行解的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充，直到找到解或活动表为空，扩充过程才结束。<BR><BR>有两种常用的方法可用来选择下一个E-节点（虽然也可能存在其他的方法）：<BR><BR>1) 先进先出（F I F O） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。<BR><BR>2) 最小耗费或最大收益法在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是具有最小耗费的活节点；如果希望搜索一个具有最大收益的解，则可用最大堆来构造活节点表，下一个E-节点是具有最大收益的活节点。<BR><BR>例5-1 [迷宫老鼠] 考察图16-3a 给出的迷宫老鼠例子和图1 6 - 1的解空间结构。使用F I F O分枝定界，初始时取（1，1）作为E-节点且活动队列为空。迷宫的位置（ 1 , 1）被置为1，以免再次返回到这个位置。（1，1）被扩充，它的相邻节点（ 1，2）和（2，1）加入到队列中（即活节点表）。为避免再次回到这两个位置，将位置（ 1，2）和（2，1）置为1。此时迷宫如图1 7 - 1 a所示，E-节点（1，1）被删除。<BR><BR>节点（1，2）从队列中移出并被扩充。检查它的三个相邻节点（见图1 6 - 1的解空间），只有（1，3）是可行的移动（剩余的两个节点是障碍节点），将其加入队列，并把相应的迷宫位置置为1，所得到的迷宫状态如图17-1b 所示。节点（1，2）被删除，而下一个E-节点（2，1）将会被取出，当此节点被展开时，节点（3，1）被加入队列中，节点（3，1）被置为1，节点（2，1）被删除，所得到的迷宫如图17-1c 所示。此时队列中包含（1，3）和（3，1）两个节点。随后节点（1，3）变成下一个E-节点，由于此节点不能到达任何新的节点，所以此节点即被删除，节点（3，1）成为新的E-节点，将队列清空。节点（ 3，1）展开，（3，2）被加入队列中，而（3，1）被删除。（3，2）变为新的E-节点，展开此节点后，到达节点（3，3），即迷宫的出口。<BR><BR>使用F I F O搜索，总能找出从迷宫入口到出口的最短路径。需要注意的是：利用回溯法找到的路径却不一定是最短路径。有趣的是，程序6 - 11已经给出了利用F I F O分枝定界搜索从迷宫的（1，1）位置到（n，n） 位置的最短路径的代码。<BR><BR>例5-2 下面比较分别利用F I F O分枝定界和最大收益分枝定界方法来解决如下背包问题：n=3, w=, p=, c= 3 0。F I F O分枝定界利用一个队列来记录活节点，节点将按照F I F O顺序从队列中取出；而最大收益分枝定界使用一个最大堆，其中的E-节点按照每个活节点收益值的降序，或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。本例所使用的背包问题与例1 6 . 2相同，并且有相同的解空间树。<BR><BR>使用F I F O分枝定界法搜索，初始时以根节点A作为E-节点，此时活节点队列为空。当节点<BR><BR>A展开时，生成了节点B和C，由于这两个节点都是可行的，因此都被加入活节点队列中，节点A被删除。下一个E-节点是B，展开它并产生了节点D和E，D是不可行的，被删除，而E被加入队列中。下一步节点C成为E-节点，它展开后生成节点F和G，两者都是可行节点，加入队列中。下一个E-节点E生成节点J和K，J不可行而被删除，K是一个可行的叶节点，并产生一个到目前为止可行的解，它的收益值为4 0。<BR><BR>下一个E-节点是F，它产生两个孩子L、M，L代表一个可行的解且其收益值为5 0，M代表另一个收益值为1 5的可行解。G是最后一个E-节点，它的孩子N和O都是可行的。由于活节点队列变为空，因此搜索过程终止，最佳解的收益值为5 0。<BR><BR>可以看到，工作在解空间树上的F I F O分枝定界方法非常象从根节点出发的宽度优先搜索。它们的主要区别是在F I F O分枝定界中不可行的节点不会被搜索。最大收益分枝定界算法以解空间树中的节点A作为初始节点。展开初始节点得到节点B和C，两者都是可行的并被插入堆中，节点B获得的收益值是4 0（设x1 = 1），而节点C得到的收益值为0。A被删除，B成为下一个E-节点，因为它的收益值比C的大。当展开B时得到了节点D和E，D是不可行的而被删除，E加入堆中。由于E具有收益值4 0，而C为0，因为E成为下一个E-节点。<BR><BR>展开E时生成节点J和K，J不可行而被删除，K是一个可行的解，因此K为作为目前能找到的最优解而记录下来，然后K被删除。由于只剩下一个活节点C在堆中，因此C作为E-节点被展开，生成F、G两个节点插入堆中。F的收益值为2 5，因此成为下一个E-节点，展开后得到节点L和M，但L、M都被删除，因为它们是叶节点，同时L所对应的解被作为当前最优解记录下来。最终，G成为E-节点，生成的节点为N和O，两者都是叶节点而被删除，两者所对应的解都不比当前的最优解更好，因此最优解保持不变。此时堆变为空，没有下一个E-节点产生，搜索过程终止。终止于J的搜索即为最优解。<BR><BR>犹如在回溯方法中一样，可利用一个定界函数来加速最优解的搜索过程。定界函数为最大收益设置了一个上限，通过展开一个特殊的节点可能获得这个最大收益。如果一个节点的定界函数值不大于目前最优解的收益值，则此节点会被删除而不作展开，更进一步，在最大收益分枝定界方法中，可以使节点按照它们收益的定界函数值的非升序从堆中取出，而不是按照节点的实际收益值来取出。这种策略从可能到达一个好的叶节点的活节点出发，而不是从目前具有较大收益值的节点出发。<BR><BR>例5-3 [旅行商问题] 对于图1 6 - 4的四城市旅行商问题，其对应的解空间为图1 6 - 5所示的排列树。F I F O分枝定界使用节点B作为初始的E-节点，活节点队列初始为空。当B展开时，生成节点C、D和E。由于从顶点1到顶点2，3，4都有边相连，所以C、D、E三个节点都是可行的并加入队列中。当前的E-节点B被删除，新的E-节点是队列中的第一个节点，即节点C。因为在图1 6 - 4中存在从顶点2到顶点3和4的边，因此展开C，生成节点F和G，两者都被加入队列。下一步，D成为E-节点，接着又是E，到目前为止活节点队列中包含节点F到K。下一个E-节点是F，展开它得到了叶节点L。至此找到了一个旅行路径，它的开销是5 9。展开下一个E-节点G，得到叶节点M，它对应于一个开销为6 6的旅行路径。接着H成为E-节点，从而找到叶节点N，对应开销为2 5的旅行路径。下一个E-节点是I，它对应的部分旅行1 - 3 - 4的开销已经为2 6，超过了目前最优的旅行路径，因此， I不会被展开。最后，节点J，K成为E-节点并被展开。经过这些展开过程，队列变为空，算法结束。找到的最优方案是节点N所对应的旅行路径。<BR><BR>如果不使用F I F O方法，还可以使用最小耗费方法来搜索解空间树，即用一个最小堆来存储活节点。这种方法同样从节点B开始搜索，并使用一个空的活节点列表。当节点B展开时，生成节点C、D和E并将它们加入最小堆中。在最小堆的节点中， E具有最小耗费（因为1 - 4的局部旅行的耗费是4），因此成为E-节点。展开E生成节点J和K并将它们加入最小堆，这两个节点的耗费分别为1 4和2 4。此时，在所有最小堆的节点中，D具有最小耗费，因而成为E-节点，并生成节点H和I。至此，最小堆中包含节点C、H、I、J和K，H具有最小耗费，因此H成为下一个E-节点。展开节点E，得到一个完整的旅行路径1 - 3 - 2 - 4 - 1，它的开销是2 5。节点J是下一个E-节点，展开它得到节点P，它对应于一个耗费为2 5的旅行路径。节点K和I是下两个E-节点。由于I的开销超过了当前最优的旅行路径，因此搜索结束，而剩下的所有活节点都不能使我们找到更优的解。<BR><BR>对于例5 - 2的背包问题，可以使用一个定界函数来减少生成和展开的节点数量。这种函数将确定旅行的最小耗费的下限，这个下限可通过展开某个特定的节点而得到。如果一个节点的定界函数值不能比当前的最优旅行更小，则它将被删除而不被展开。另外，对于最小耗费分枝定界，节点按照它在最小堆中的非降序取出。<BR><BR>在以上几个例子中，可以利用定界函数来降低所产生的树型解空间的节点数目。当设计定界函数时，必须记住主要目的是利用最少的时间，在内存允许的范围内去解决问题。而通过产生具有最少节点的树来解决问题并不是根本的目标。因此，我们需要的是一个能够有效地减少计算时间并因此而使产生的节点数目也减少的定界函数。<BR><BR>回溯法比分枝定界在占用内存方面具有优势。回溯法占用的内存是O（解空间的最大路径长度），而分枝定界所占用的内存为O（解空间大小）。对于一个子集空间，回溯法需要(n)的内存空间，而分枝定界则需要O ( 2n ) 的空间。对于排列空间，回溯需要(n) 的内存空间，分枝定界需要O (n!) 的空间。虽然最大收益（或最小耗费）分枝定界在直觉上要好于回溯法，并且在许多情况下可能会比回溯法检查更少的节点，但在实际应用中，它可能会在回溯法超出允许的时间限制之前就超出了内存的限制。<BR><BR>练习<BR><BR>1. 假定在一个L I F O分枝定界搜索中，活节点列表的行为与堆栈相同，请使用这种方法来解决例5 - 2的背包问题。L I F O分枝定界与回溯有何区别？<BR><BR>2. 对于如下0 / 1背包问题：n=4, p=, w=, c =6。<BR><BR>1) 画出有四个对象的背包问题的解空间树。<BR><BR>2) 像例1 7 - 2那样，描述用F I F O分枝定界法解决上述问题的过程。<BR><BR>3) 使用程序1 6 - 6的B o u n d函数来计算子树上任一叶节点可能获得的最大收益值，并根据每一步所能得到的最优解对应的定界函数值来判断是否将节点加入活节点列表中。解空间中哪些节点是使用以上机制的F I F O分枝定界方法产生的？<BR><BR>4) 像例1 7 - 2那样，描述用最大收益分枝定界法解决上述问题的过程。<BR><BR>5) 在最大收益分枝定界中，若使用3）中的定界函数，将产生解空间树中的哪些节点？</P>回溯算法基本思想
<P>回溯（b a c k t r a c k i n g）是一种系统地搜索问题解答的方法。为了实现回溯，首先需要为问题定义一个解空间（ solution space），这个空间必须至少包含问题的一个解（可能是最优的）。在迷宫老鼠问题中，我们可以定义一个包含从入口到出口的所有路径的解空间；在具有n 个对象的0 / 1背包问题中（见1 . 4节和2 . 2节），解空间的一个合理选择是2n 个长度为n 的0 / 1向量的集合，这个集合表示了将0或1分配给x的所有可能方法。当n= 3时，解空间为{ ( 0 , 0 , 0 )，( 0 , 1 , 0 )，( 0 , 0 , 1 )，( 1 , 0 , 0 )，( 0 , 1 , 1 )，( 1 , 0 , 1 )，( 1 , 1 , 0 )，( 1 , 1 , 1 ) }。<BR><BR>下一步是组织解空间以便它能被容易地搜索。典型的组织方法是图或树。图1 6 - 1用图的形式给出了一个3×3迷宫的解空间。从( 1 , 1 )点到( 3 , 3 )点的每一条路径都定义了3×3迷宫解空间中的一个元素，但由于障碍的设置，有些路径是不可行的。<BR><BR>图1 6 - 2用树形结构给出了含三个对象的0 / 1背包问题的解空间。从i 层节点到i+ 1层节点的一条边上的数字给出了向量x 中第i个分量的值xi ，从根节点到叶节点的每一条路径定义了解空间中的一个元素。从根节点A到叶节点H的路径定义了解x= [ 1 , 1 , 1 ]。根据w 和c 的值，从根到叶的路径中的一些解或全部解可能是不可行的。<BR><BR>一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。在迷宫老鼠问题中，开始节点为入口节点( 1 , 1 )；在0 / 1背包问题中，开始节点为根节点A。开始节点既是一个活节点又是一个E-节点（expansion node）。从E-节点可移动到一个新节点。如果能从当前的E-节点移动到一个新节点，那么这个新节点将变成一个活节点和新的E-节点，旧的E-节点仍是一个活节点。如果不能移到一个新节点，当前的E-节点就“死”了（即不再是一个活节点），那么便只能返回到最近被考察的活节点（回溯），这个活节点变成了新的E-节点。当我们已经找到了答案或者回溯尽了所有的活节点时，搜索过程结束。<BR><BR>例4-1 [迷宫老鼠] 考察图16-3a 的矩阵中给出的3×3的“迷宫老鼠”问题。我们将利用图1 6 -1给出的解空间图来搜索迷宫。<BR><BR>从迷宫的入口到出口的每一条路径都与图1 6 - 1中从( 1 , 1 )到( 3 , 3 )的一条路径相对应。然而，图1 6 - 1中有些从( 1 , 1 )到( 3 , 3 )的路径却不是迷宫中从入口到出口的路径。搜索从点( 1 , 1 )开始，该点是目前唯一的活节点，它也是一个E-节点。为避免再次走过这个位置，置m a z e( 1 , 1 )为1。从这个位置，能移动到( 1 , 2 )或( 2 , 1 )两个位置。对于本例，两种移动都是可行的，因为在每一个位置都有一个值0。假定选择移动到( 1 , 2 )，m a z e( 1 , 2 )被置为1以避免再次经过该点。迷宫当前状态如图16-3b 所示。这时有两个活节点(1,1) (1,2)。( 1 , 2 )成为E-节点。<BR><BR>在图1 6 - 1中从当前E-节点开始有3个可能的移动，其中两个是不可行的，因为迷宫在这些位置上的值为1。唯一可行的移动是( 1 , 3 )。移动到这个位置，并置m a z e( 1 , 3 )为1以避免再次经过该点，此时迷宫状态为1 6 - 3 c。图1 6 - 1中，从( 1 , 3 )出发有两个可能的移动，但没有一个是可行的。所以E-节点( 1 , 3 )死亡，回溯到最近被检查的活节点( 1 , 2 )。在这个位置也没有可行的移动，故这个节点也死亡了。唯一留下的活节点是( 1 , 1 )。这个节点再次变为E-节点，它可移动到( 2 , 1 )。现在活节点为( 1 , 1 )，( 2 , 1 )。继续下去，能到达点( 3 , 3 )。此时，活节点表为( 1 , 1 )，( 2 , 1 )，( 3 , 1 )，( 3 , 2 )，( 3 , 3 )，这即是到达出口的路径。<BR><BR>程序5 - 1 3是一个在迷宫中寻找路径的回溯算法。<BR><BR>例4-2 考察如下背包问题：n= 3，w= [ 2 0 , 1 5 , 1 5 ]，p= [ 4 0 , 2 5 , 2 5 ]且c= 3 0。从根节点开始搜索图1 6 - 2中的树。根节点是当前唯一的活节点，也是E-节点，从这里能够移动到B或C点。假设移动到B，则活节点为A和B。B是当前E-节点。在节点B，剩下的容量r 为1 0，而收益c p 为4 0。从B点，能移动到D或E。移到D是不可行的，因为移到D所需的容量w2 为1 5。到E的移动是可行的，因为在这个移动中没有占用任何容量。E变成新的E-节点。这时活节点为A , B , E。在节点E，r= 1 0，c p= 4 0。从E，有两种可能移动（到J 和K），到J 的移动是不可行的，而到K的移动是可行的。节点K变成了新的E-节点。因为K是一个叶子，所以得到一个可行的解。这个解的收益为c p= 4 0。x 的值由从根到K的路径来决定。这个路径（ A , B , E , K）也是此时的活节点序列。既然不能进一步扩充K，K节点死亡，回溯到E，而E也不能进一步扩充，它也死亡了。接着，回溯到B，它也死亡了，A再次变为E-节点。它可被进一步扩充，到达节点C。此时r= 3 0，c p= 0。从C点能够移动到F或G。假定移动到F。F变为新的E-节点并且活节点为A, C,F。在F，r= 1 5，c p= 2 5。从F点，能移动到L或M。假定移动到L。此时r= 0，c p= 5 0。既然L是一个叶节点，它表示了一个比目前找到的最优解（即节点K）更好的可行解，我们把这个解作为最优解。节点L死亡，回溯到节点F。继续下去，搜索整棵树。在搜索期间发现的最优解即为最后的解。<BR><BR>例4-3 [旅行商问题] 在这个问题中，给出一个n 顶点网络（有向或无向），要求找出一个包含所有n 个顶点的具有最小耗费的环路。任何一个包含网络中所有n 个顶点的环路被称作一个旅行（t o u r）。在旅行商问题中，要设法找到一条最小耗费的旅行。<BR><BR>图1 6 - 4给出了一个四顶点网络。在这个网络中，一些旅行如下： 1 , 2 , 4 , 3 , 1；1 , 3 , 2 , 4 , 1和1 , 4 , 3 , 2 , 1。旅行2 , 4 , 3 , 1 , 2；4 , 3 , 1 , 2 , 4和3 , 1 , 2 , 4 , 3和旅行1 , 2 , 4 , 3 , 1一样。而旅行1 , 3 , 4 , 2 , 1是旅行1 , 2 , 4 , 3 , 1的“逆”。旅行1 , 2 , 4 , 3 , 1的耗费为6 6；而1 , 3 , 2 , 4 , 1的耗费为2 5；1 , 4 , 3 , 2 , 1为5 9。故1 , 3 , 2 , 4 , 1是该网络中最小耗费的旅行。<BR><BR>顾名思义，旅行商问题可被用来模拟现实生活中旅行商所要旅行的地区问题。顶点表示旅行<BR><BR>商所要旅行的城市（包括起点）。边的耗费给出了在两个城市旅行所需的时间（或花费）。旅行表示当旅行商游览了所有城市再回到出发点时所走的路线。 <BR><BR>旅行商问题还可用来模拟其他问题。假定要在一个金属薄片或印刷电路板上钻许多孔。孔的位置已知。这些孔由一个机器钻头来钻，它从起始位置开始，移动到每一个钻孔位置钻孔，然后回到起始位置。总共花的时间是钻所有孔的时间与钻头移动的时间。钻所有孔所需的时间独立于钻孔顺序。然而，钻头移动时间是钻头移动距离的函数。因此，希望找到最短的移动路径。<BR><BR>另有一个例子，考察一个批量生产的环境，其中有一个特殊的机器可用来生产n 个不同的产品。利用一个生产循环不断地生产这些产品。在一个循环中，所有n 个产品被顺序生产出来，然后再开始下一个循环。在下一个循环中，又采用了同样的生产顺序。例如，如果这台机器被用来顺序为小汽车喷红、白、蓝漆，那么在为蓝色小汽车喷漆之后，我们又开始了新一轮循环，为红色小汽车喷漆，然后是白色小汽车、蓝色小汽车、红色小汽车，..，如此下去。一个循环的花费包括生产一个循环中的产品所需的花费以及循环中从一个产品转变到另一个产品的花费。虽然生产产品的花费独立于产品生产顺序，但循环中从生产一个产品转变到生产另一个产品的花费却与顺序有关。为了使耗费最小化，可以定义一个有向图，图中的顶点表示产品，边＜(i , j)＞上的耗费值为生产过程中从产品i 转变到产品j 所需的耗费。一个最小耗费的旅行定义了一个最小耗费的生产循环。<BR><BR>既然旅行是包含所有顶点的一个循环，故可以把任意一个点作为起点（因此也是终点）。<BR><BR>针对图1 6 - 4，任意选取点1作为起点和终点，则每一个旅行可用顶点序列1, v2 ,., vn , 1来描述，<BR><BR>v2 , ., vn 是(2, 3, ., n) 的一个排列。可能的旅行可用一个树来描述，其中每一个从根到叶的路<BR><BR>径定义了一个旅行。图1 6 - 5给出了一棵表示四顶点网络的树。从根到叶的路径中各边的标号定义了一个旅行（还要附加1作为终点）。例如，到节点L的路径表示了旅行1 , 2 , 3 , 4 , 1，而到节点O的路径表示了旅行1 , 3 , 4 , 2 , 1。网络中的每一个旅行都由树中的一条从根到叶的确定路径来表示。因此，树中叶的数目为(n- 1 )！。<BR><BR>回溯算法将用深度优先方式从根节点开始，通过搜索解空间树发现一个最小耗费的旅行。对图1 6 - 4的网络，利用图1 6 - 5的解空间树，一个可能的搜索为A B C F L。在L点，旅行1 , 2 , 3 , 4 , 1作为当前最好的旅行被记录下来。它的耗费是5 9。从L点回溯到活节点F。由于F没有未被检查的孩子，所以它成为死节点，回溯到C点。C变为E-节点，向前移动到G，然后是M。这样构造出了旅行1 , 2 , 4 , 3 , 1，它的耗费是6 6。既然它不比当前的最佳旅行好，抛弃它并回溯到G，然后是C , B。从B点，搜索向前移动到D，然后是H , N。这个旅行1 , 3 , 2 , 4 , 1的耗费是2 5，比当前的最佳旅行好，把它作为当前的最好旅行。从N点，搜索回溯到H，然后是D。在D点，再次向前移动，到达O点。如此继续下去，可搜索完整个树，得出1 , 3 , 2 , 4 , 1是最少耗费的旅行。<BR><BR>当要求解的问题需要根据n 个元素的一个子集来优化某些函数时，解空间树被称作子集树（subset tree）。所以对有n 个对象的0 / 1背包问题来说，它的解空间树就是一个子集树。这样一棵树有2n 个叶节点，全部节点有2n+ 1－1个。因此，每一个对树中所有节点进行遍历的算法都必须耗时W ( 2n )。当要求解的问题需要根据一个n 元素的排列来优化某些函数时，解空间树被称作排列树（permutation tree）。这样的树有n! 个叶节点，所以每一个遍历树中所有节点的算法都必须耗时W (n! )。图1 6 - 5中的树是顶点{ 2 , 3 , 4 }的最佳排列的解空间树，顶点1是旅行的起点和终点。<BR><BR>通过确定一个新近到达的节点能否导致一个比当前最优解还要好的解，可加速对最优解的搜索。如果不能，则移动到该节点的任何一个子树都是无意义的，这个节点可被立即杀死，用来杀死活节点的策略称为限界函数（ bounding function）。在例1 6 - 2中，可使用如下限界函数：杀死代表不可行解决方案的节点；对于旅行商问题，可使用如下限界函数：如果目前建立的部分旅行的耗费不少于当前最佳路径的耗费，则杀死当前节点。如果在图1 6 - 4的例子中使用该限界函数，那么当到达节点I时，已经找到了具有耗费2 5的1 , 3 , 2 , 4 , 1的旅行。在节点I，部分旅行1 , 3 , 4的耗费为2 6，若旅行通过该节点，那么不能找到一个耗费小于2 5的旅行，故搜索以I为根节点的子树毫无意义。<BR><BR>小结<BR><BR>回溯方法的步骤如下：<BR><BR>1) 定义一个解空间，它包含问题的解。<BR><BR>2) 用适于搜索的方式组织该空间。<BR><BR>3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。<BR><BR>回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前E-节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。<BR><BR>练习<BR><BR>1. 考察如下0 / 1背包问题：n= 4，w= [ 2 0 , 2 5 , 1 5 , 3 5 ]，p= [ 4 0 , 4 9 , 2 5 , 6 0 ]，c= 6 2。<BR><BR>1) 画出该0 / 1背包问题的解空间树。<BR><BR>2) 对该树运用回溯算法（利用给出的p s , w s , c值），依回溯算法遍历节点的顺序标记节点。确定回溯算法未遍历的节点。<BR><BR>2. 1) 当n= 5时，画出旅行商问题的解空间树。<BR><BR>2) 在该树上，运用回溯算法（使用图1 6 - 6的例子）。依回溯算法遍历节点的顺序标记节点。确定未被遍历的节点。<BR><BR>3. 每周六， Mary 和Joe 都在一起打乒乓球。她们每人都有一个装有1 2 0个球的篮子。<BR><BR>这样一直打下去，直到两个篮子为空。然后她们需要从球桌周围拾起2 4 0个球，放入各自<BR><BR>的篮子。Mary 只拾她这边的球，而Joe 拾剩下的球。描述如何用旅行商问题帮助Mary 和<BR><BR>Joe 决定她们拾球的顺序以便她们能走最少的路径。</P> 论坛之星勋章实至名归啊。建议发到资料中心。
咚咕里个咚，咚咕里个咚。
回复 #49 toes 的帖子
这个东西太好了！ 问一下，线搜索法是优化里面的算法吗？ 42楼的傅立叶变换根本打不开，楼主自己也不会编，就硬说有这个程序，骗人吧？？？ 不错!难得有这么齐的算法!好顶! 请问楼主，有没有同伦延拓法的程序？谢谢了！ 这么强的帖，在不顶还说的过去吗，狂顶一顿 楼主太棒了，我想弱弱地问下，这些代码是用matlab写的吗？回复 42楼 的帖子
怎么看不见啊！哪位给说明一下！谢谢！ 原帖由 无水1324 于 2007-10-15 22:01 发表 http://www.chinavib.com/forum/images/common/back.gif问一下，线搜索法是优化里面的算法吗？
是的 原帖由 kanglingucas 于 2007-12-7 14:38 发表 http://www.chinavib.com/forum/images/common/back.gif
42楼的傅立叶变换根本打不开，楼主自己也不会编，就硬说有这个程序，骗人吧？？？
论坛已经关闭了相关下载，会不会我自己知道就可以了 原帖由 zyb628 于 2007-12-17 17:14 发表 http://www.chinavib.com/forum/images/common/back.gif
请问楼主，有没有同伦延拓法的程序？谢谢了！
http://orion.math.iastate.edu/burkardt/f_src/pitcon/pitcon.html