D
dingfuhai
Unregistered / Unconfirmed
GUEST, unregistred user!
货郎担问题
货郎担问题（Traveling salesman problem）有名的难题，起源于商业经济发达的欧美。原始问题是这样提出的：某推销员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路程（或旅费）最小。问题开始提出时不少人都认为很简单。后来人们从实践中才逐步认识到其计算复杂性是输入的指数函数，属于相当难解的问题之一。下面是这一问题的形式描述。
设G = ( V , E ) 是一个有向图。图中各条边的耗费 > 0 。当 时，定义 = 。设 = n >1。图中的一条周游路线是包括V中的每个顶点在内的一条有向回路。一条周游路线的耗费是这条路线上所有边的耗费之和。所谓货郎担问题就是要在G中找出一条有最小耗费的周游路线。
不失普遍性，考虑以顶点1为始点和终点的一条周游路线。每条这样的路线均可表示为这种形式：对于某个K V－{1，k}的每个顶点各一次。不难看出，如果以顶点1为始点和终点的某条周游路线是最佳的，那么，这条路径上从顶点K到顶点1的部分路径（经过V－{1，k}的每个顶点各一次），必是从K到1的一条最短路径。因此，最佳原理是适用的。设g( i, S )是从顶点i出发，经过S中除去顶点i之外的其它顶点各一次并回到顶点1的一条最短路径的长。那么g ( 1, V－{1} )就是一条最佳旅游路线的长。按最佳原理，我们有
g(1, V－{1})= { +g( k, V－{1，k})}……( 1.1 )
一般地，当i S时，有
g ( i ,s ) = { + g ( j, S －{ j } ) } ……( 1.2 )
如果对所有选定的k,已知g ( k, V－{1，k}) , 从 ( 1.1 ) 可以求得g ( 1, V－{1} )。各g ( i ,s )的值可以从式 ( 1.2 ) 逐步求得。令g( i, ) = , 1 i n,这是初始状态。往后，逐次对元素个数为1的集合S，能求得一切g ( i ,s )。然后求得 < n－1时，对任何g ( i ,s )，必须满足i 1, 1 S, i S。最后可以求得问题的最佳解。
货郎担问题（Traveling salesman problem）有名的难题，起源于商业经济发达的欧美。原始问题是这样提出的：某推销员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一遍最后回到驻地的路线，使总的路程（或旅费）最小。问题开始提出时不少人都认为很简单。后来人们从实践中才逐步认识到其计算复杂性是输入的指数函数，属于相当难解的问题之一。下面是这一问题的形式描述。
设G = ( V , E ) 是一个有向图。图中各条边的耗费 > 0 。当 时，定义 = 。设 = n >1。图中的一条周游路线是包括V中的每个顶点在内的一条有向回路。一条周游路线的耗费是这条路线上所有边的耗费之和。所谓货郎担问题就是要在G中找出一条有最小耗费的周游路线。
不失普遍性，考虑以顶点1为始点和终点的一条周游路线。每条这样的路线均可表示为这种形式：对于某个K V－{1，k}的每个顶点各一次。不难看出，如果以顶点1为始点和终点的某条周游路线是最佳的，那么，这条路径上从顶点K到顶点1的部分路径（经过V－{1，k}的每个顶点各一次），必是从K到1的一条最短路径。因此，最佳原理是适用的。设g( i, S )是从顶点i出发，经过S中除去顶点i之外的其它顶点各一次并回到顶点1的一条最短路径的长。那么g ( 1, V－{1} )就是一条最佳旅游路线的长。按最佳原理，我们有
g(1, V－{1})= { +g( k, V－{1，k})}……( 1.1 )
一般地，当i S时，有
g ( i ,s ) = { + g ( j, S －{ j } ) } ……( 1.2 )
如果对所有选定的k,已知g ( k, V－{1，k}) , 从 ( 1.1 ) 可以求得g ( 1, V－{1} )。各g ( i ,s )的值可以从式 ( 1.2 ) 逐步求得。令g( i, ) = , 1 i n,这是初始状态。往后，逐次对元素个数为1的集合S，能求得一切g ( i ,s )。然后求得 < n－1时，对任何g ( i ,s )，必须满足i 1, 1 S, i S。最后可以求得问题的最佳解。