《计算机算法设计与分析 第6章》.ppt

* 6.7 旅行售货员问题 1. 问题描述 某售货员要到若干城市去推销商品已知各城市之间的路程(或旅费)他要选定一条从驻地出发经过每个城市一次最后回到驻地的路线使总的路程(或总旅费)最小 路线是一个带权图图中各边的费用权为正数图的一条周游路线是包括V中的每个顶点在内的一条回路周游路线的费用是这条路线上所有边的费用之和 旅行售货员问题的解空间可以组织成一棵树从树的根结点到任一叶结点的路径定义了图的一