S - k 算法设计 根据递归式,需要构造一个解空间树来记录 Dk S。
下面是城市数量为 4 的解空 间树 需要游走的城市数量为 4 时的解空间树 树中的每一个节点需要记录游走过的城市集合,以及游走这些城市所需的花费。
此外树还要保存最短路径信息,因此节点要保存当前游走的城市以及之前游走过的城市集合的引用。
下面是节点的数据结构struct Node int cost // 旅行的费用 int cur // 当前所在的城市 int prev // 之前旅行过的城市 Node int _prev -1 int _cur 0 int _cost MAX_COST : cost _cost prev _prev cur _cur 树是怎样产生的? 首先解空间树是一层一层计算的,上一层的节点计算产生下一层的节点数据。
对第 i 层来说,它有 Cn 个节点,每个节点记录了游走过的城市集合。
对每个节点又将进 i行 n 次计算,每次计算中都向集合中新增加一个没有游走过的城市。
集合 S 增加一个元素 k,会产生一个新集合 S,这个集合存储在下一行节点中。
现在需要做的是根据现有的集合 S 和新增加城市 k,找到集合 S应该在下一行的哪个位置,这是可以办到的。
找到 S后,需要比较 S.cost dist S.cur k 与 S.cost 的大小。
如果小于的话表示找到一条更短的路径周游集合 S,更新 S的 cost、cur、prev 属性。
这样一层一层的计算下去直到第 n - 1 行,这时对该行的每个节点的 cost 属性进行如下计算 S.cost dist S.cur k // k 表示最后一个没有游走的城市 S.cost dist k 0 然后选择 cost 最小的一个节点,根据该节点就可以计算出货郎担问题的最短周游路径。
根据周游城市集合 S,如何确定它在某行中的位置? 这是一个排列问题,假设 S 为集合1,3,表示已经周游了两个城市:城市 1和城市 3。
那么它在第 2 行中所处的位置可以如下计算 int t 0 t C3 // 从 2、3、4 中选两个 2 t C1 // 从 4 中选一个 1 2 int p C4 - t – 1 1 上面是一个简单的举例,用来说明已知一个序列可以计算它在排列中的位置,而且一点也不复杂。
一般化的情况可以由这个例子推导而得,由于时间问题这里略写。
算法伪代码 For 遍历解空间每一层 For 遍历一层中的每个节点 For i 1 n IF 判断城市是否已经周游过 如果没有游走过,加入集合 S,产生新集合 S 并根据集合 S计算它在下一行中的位置 IF 判断新游走的一个城市的花费是否小于 S的花费 如果是的话更新 S节点数据 // 解空间树构造完毕 For 遍历最后一层解空间树 更新每个节点的 cost 属性,使他表示周游所有城市的花费 选择 cost 值最小的节点,根据该节点计算出周游路线算法的时间复杂性 该算法的时间复杂性比较复杂,首先它需要对解空间树的每个节点进行遍历,每次遍历都需要进行 n 次计算,每次计算过程中要计算城市是否已经游走过,以及计算新增加一个城市,节点将指向下一行的哪.
上一篇:
并行编程模式
下一篇:
用遗传算法解决车辆优化调度问题