中文XML论坛--求最优化算法

贴子主题：求最优化算法

本主题类别:

一、问题描述

1、货郎担问题

原始的欧几里德货郎担问题是指一个货郎需要走过多个城市，并且每一个城市只需要经过一次，最后回到出发点，如何确定一条路线为最短的路线。把这个问题描述为数学问题即为对平面给定的n个点确定一条连结各点的、闭合的最短游历路线问题。

2、问题扩展一（我们的问题）

现在我们的问题是，如果把原始的货郎担问题进行扩展：假设货郎需要走过多个国家，每一个国家内又有多个城市，如何确定一条最短的行走路线。
约束条件：货郎必需逐个国家进行行走。
即货郎可以选择任意一个国家做为出发点，进入国家内后，也可以选择任意一个城市做为出发点，但必须走完该国家内的所有城市之后方可进入下一个国家。

特殊要求：可按给定的出发点做为起始点进行计算，该要求可做为参数来控制是否需要考虑。

3、问题扩展二（在扩展一的基础上）
在问题扩展一（由城市扩展到国家）的基础上，再由国家扩展到洲：假设货郎需要走过多个洲，每一个洲内又包括多个国家，每一个国家内又有多个城市，如何确定一条最短的行走路线。
约束条件：货郎必需逐个洲、逐个国家进行行走。
即货郎可以选择任意一个洲做为出发点，进入洲内也可以选择任意一个国家做为出发点，进入国家内后，同样也可以选择任意一个城市做为出发点，但必须走完该洲内所有的国家，才能进入到下一个洲，在洲内的国家内行走时，也必须先走玩一个国家内的所有城市之后方可进入下一个国家。

特殊要求：洲的选择顺序可以按给定的顺序进行行走，不可以调整原有顺序，该要求可做为参数来控制是否需要考虑。

这两个问题便时我们目前所遇到问题的抽象化的一个描述。

二、捎带要求（可有参数控制是否需要）

在上面所描述的问题中，我们又有一个捎带的特殊要求，假设两个国家内有两个或者多个城市的距离在一定的范围内（可自定义）时，则可以在一个国家内行走的时候，捎带把另一个国家的一个或者多个城市走过，但这种捎带不可以无限捎带，即捎带之后要求可以再回到原国家内的下一个城市，洲之间城市不可以进行捎带（可通过参数控制）。

三、数据描述(城市即坐标数据)
1、洲的数量多集中在20种左右；
2、国家数量多集中在200个国家左右；
3、国家内的城市数量最多一般在200个左右；
4、有些国家内可能只有一个城市；
5、可能只有一个洲；
6、可能会有一个洲内只有一个国家，同时这个国家内也只有一个城市。

关于最优化算法,补充以下信息(最好用Delphi):
1.    两点间最短距离D并非我们通常的距离计算.理解如下:
城市表示C1(X1,Y1),C2(X2,Y2),C3(X3,Y3),C4…..
C1到 C2的距离 Dc1-c2= MAX （|X2-X1|，|Y2-Y1| ）
C1到 C3的距离 Dc1-c3= MAX （|X3-X1|，|Y3-Y1| ）
........
Dc1-c2 与 Dc1-c3 比较然后确定其先后顺序.
(以上假定 C1为起始点)
2.    既要求每个城市到城市的距离最短,同时又要求在该国家内整体距离最短(优);
3.    因为国家的遍历顺序不同,会有不同距离,所以满足2的同时又要求遍历完所有国家的距离最短( 优);
4.    优先保障最友结果,再确保整体运算速度快,再尽可能少占内存;
5. 在该实现中我们可以另外假定一个起始点 .


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	77.637ms