分支限界法(费用矩阵).doc

8.1 分枝与限界法的基本思想 回溯法是用深度优先的有哪些信誉好的足球投注网站方法，遇到死结点才回溯到父结点。分枝与限界法是在有哪些信誉好的足球投注网站过程中对目标函数进行估计，存入结点表中，再根据结点表中的目标函数的最大（或最小），来决定下一步有哪些信誉好的足球投注网站的路径。两种有哪些信誉好的足球投注网站方式 8.2 货郎担问题 假设l是图G的哈密尔顿通路。w(l)是这条回路的费用。费用矩阵是c. 引理8.1 令G=(V,E)是一个有向赋权图， l是图G的一条哈密尔顿通路，c是G的费用矩阵。则回路上的边对应于费用矩阵c中每行每列各一个元素。 定义8.1 费用矩阵的第i行（列）中的每个元素减去一个正常数lhi（chi），得到一个新的费用矩阵,使其第i行（列）中最小的元素等于零，称为费用矩阵的行归约（列归约）。这个正常数称为原费用矩阵的行归约常数（列归约常数）。 定义8.2 对费用矩阵作行和列的归约，使得新矩阵的每行每列至少有一个零元素，称新矩阵为费用矩阵的归约。令h是所有行归约常数和列归约常数之和，称h是原费用矩阵的归约常数。 定理8.1 令G=(V,E)是一个有向赋权图， l是图G的一条哈密尔顿通路，c是G的费用矩阵， w(l)是这条回路的费用。如果 是其归约矩阵，归约常数是h, 是新的费用。那么， 定理8.2 令G=(V,E)是一个有向赋权图， l是图G的一条哈密尔顿通路，c是G的费用矩阵。 是其归约矩阵。令 是图 的邻接矩阵。则l是图 的一条哈密尔顿通路. 1. 界限的确定-----费用矩阵.(左图) 费用矩阵的行归约.（中图） 费用矩阵的列归约（右图） 归约矩阵和归约常数（下左）；选择路径；（中图：选c10 和不选c10，两者必居其一。若不选c10，那么c10如变成∞，而第二行和第一列需要分别选一个，分别不小于13和4，记为d10=13+4=17）； 2. 分枝的选择 选费用矩阵的元cjk,相当于选择从顶点j到顶点k的路径(j,k)。分枝的选择按两个思路进行： （1）沿cjk方向，使所选择的路线尽可能短。 （2）沿djk,最大的方向，使不选(j,k)的费用下界最大。 注意：由于我们分别考虑选cjk和不选cjk的情况，我们并没有忽略任何一条路径。因此，策略(2)只影响有哪些信誉好的足球投注网站的次序，并不影响结果。 选择路径（上页右图）； 4 步骤一 步骤二 步骤三 步骤四 步骤五 步骤六 步骤七 步骤八 步骤九 步骤十 步骤十一 步骤十二 步骤十三 步骤十四 步骤十五 步骤十六 步骤十七 步骤零