算法设计与分析6章 动态规范算法.ppt

哈密尔顿回路环球旅行问题即从一个结点出发经过所有结点回到出发点结点不能重复经过 设v1v2.vn是已知的n个城镇城镇vi到城镇vj的距离为dij现求从v1出发经各城镇一次且仅一次返回v1的最短路程 问题描述 解决方案 1.穷举法 2.动态规划 设S表示从v1到vi中间所可能经过的城市集合S实际上是包含除v1和vi两个点之外的其余点的集合但S中的点的个数要随阶段数改变 阶段 S中的点的个数 建立动