个性化阅读
专注于IT技术分析

旅行商问题介绍和解法

点击下载

假设一个推销员想访问分配给他的一定数量的城市。他知道每对城市之间的旅程距离。他的问题是选择一条从他的家乡出发的路线, 经过每个城市一次, 然后以最短的距离返回他的家乡。这个问题与找到最小长度的哈密顿电路密切相关。如果我们用连接两个城市边缘的顶点和道路来表示城市, 则会得到一个加权图, 其中每个边缘ei都有一个数wi(weight)关联。

上述摘要的物理解释是:将图G视为n个城市的地图, 其中w(i, j)是城市i和j之间的距离。推销员希望游览在同一城市开始和结束的城市, 包括只一次访问一次剩余的每个城市。

在图中, 如果我们有n个顶点(城市), 那么就有(n-1)个!完整的n个顶点图中的边(路径)和哈密顿回路总数。

最近邻法

此过程为旅行商问题提供了合理良好的结果。方法如下:

步骤1:选择一个任意顶点, 然后找到最接近该起始顶点的顶点, 以形成一条边的初始路径。

步骤2:让v表示添加到路径的最新顶点。现在, 在不在路径中的顶点的结果中, 选择最接近v的顶点, 然后添加路径, 边连接v和此顶点。重复此步骤, 直到图G的所有顶点都包含在路径中为止。

第三步:将起始顶点与一条边添加的最后一个顶点连接起来, 形成电路。

示例:对于从起点v1开始的无花果图中的图, 使用最近邻方法来解决以下旅行商问题。

旅行商问题

解决方案:我们必须从顶点v1开始。通过使用最近邻居方法, 图或哈密顿电路的逐顶点构造如图所示:

旅行商问题

这条路线的总距离是18。


赞(0)
未经允许不得转载:srcmini » 旅行商问题介绍和解法

评论 抢沙发

评论前必须登录!