论最优路径——走遍全中国摘要
论最优路径——走遍全中国摘要
摘要
本文讨论的是一个所谓“最优路径”问题，乍看之下，此问题与“旅行商问题”极为相似，但在仔细研究过后，我们发现两个问题存在本质上的差别。“旅行商问题”更接近于一个理想化的数学游戏，而本题更多的涉及到实际情况。再三考虑之下，我们决定抛弃“旅行商问题”的经典解题思路，用其他方法解决问题。
在查阅了大量真实数据之后，我们发现本问题更接近于一个数据处理问题。于是，我们尝试用MATLAB和编程来辅助我们处理数据，我们建立了历程和票价的矩阵，并通过自编的程序处理数据以获得最优路径，最优票价。最后，我们通过引用“权值”来平衡路程和票价间的关系，这使得我们的模型更接近实际情况。在第一个建模完成后，我们试图更深入了解关于“最优路径”问题的相关信息。通过图书馆、网络等媒介搜集了大量信息后，我们发现，“遗传算法”方面已经有了一套完整的关于解决“最优路径”问题的方案。我们将此方案引入，并进行简单修改，使其更适合解决本题。我们的假设 起到了“单亲演化过程”在“遗传算法”中提高初始群体适应度的作用。该假设又减少了基因库中元素的数量，使计算量大大降低。之后，再利用“群体演化过程”，在保证了算法快速收敛的同时也注重搜索空间的全局性。最后，引入收敛准则。当满足收敛准则时，运算终止，输出优化结果。
本文中的假设不仅使运算简化，且符合实际情况。其中又大量引入真实数据，使模型更具实际意义。
问题的重述
走遍全中国
周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：
1．按地理位置（经纬度）设计最短路旅行方案；
2．如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；
要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；
4．对你的算法作复杂性、可行性及误差分析；
5．关于旅行商问题提出对你自己所采用的算法的理解及评价。
二、符号约定
Distance:距离
Si:票价
Li:里程
ppr:性价比
BestV：当前最优值
三、问题的分析
旅行商问题给出了一种逐个消去最小元素的方法，理论上这种方法可以运用于本问题，但在仔细研究过后，我们发现本问题因涉及大量真实情况，即最终结果由多个变量控制，且多个变量之间存在相互影响、真实性和取舍问题时，旅行商问题的解法就显得过于简单且理想化了。于是，我们提出了“计算机编程辅助数据处理”、“遗传算法”这两种解法。两种解法虽各有利弊，但都建立于真实数据之上，自然，得到的结果也更加接近真实，特别是“计算机辅助数据处理”。我们通过自行编辑的程序完成了对大量数据的处理，有通过合理的假设是问题易于解决却又不失其真实性。对于“权”的引用更是将数学建模思想与真实性紧密结合在一起，毕竟，数学建模最终是以解决实际问题为目的脱离了真实的数学建模只是研究者手中把玩的而已。
四、基本假设
1 周先生乘火车从某一城市向另一城市出发时，只以接壤省份城市作为其目的地。飞机目的地无限制，特殊城市（如拉萨）则以实际情况为准。
2 乘火车或飞机在城市之间移动的时间不计入旅行时间。（可视其为零）
3 货车与飞机均准点到达。
4 旅行途中不遭遇任何灾难或事故。
5 假定旅途中火车运行轨迹与城市间的直线距离成正比例。
五、模型的建立与求解
问题一
我觉得用流程图还不如自己去分析
现在我举个例子便知：
我假设有四个城市，北京，上海，天津，重庆，编号为0，1，2，3
北京 1088
1640 118
上海 953 天津
1600 重庆 2067
1.首先
以北京为起点，从北京到哪个城市路程最短呢？天津118, 定位天津。
以天津为起点，从天津到哪个城市路程最短呢？上海,953 定位上海。
以上海为起点，从上海到哪个城市路程最短呢？重庆,1600 定位重庆。
最后回到原点北京
Distance=118+953+1600+1640=4311
文件存储形式(只列举4个城市)
北京 上海 天津 重庆
北京 0 1088 118 1 640
上海 1088 0 953 1600
天津 118 953 0 2067
重庆 1640 1600 2067 0
贪心算法代码：
for(i=0;i
s[i]=0;
for(j=0;j
{
for(i=0;i
{
dingwei[i]=dist[number][i];
}
s[number]=1;
printf("%s->",getCityName(number));
min=MAX;
for(k=0;k
{
if(s[k]==0&&min>dingwei[k])
{
min=dingwei[k];
number=k;
}
if(u==M)
min=dingwei[n];
}
u++;
distance+=min;
//printf("距离为:%d\n",min);
}
printf("%s",getCityName(n));
printf("\n距离为:%d\n",distance);
数据结果
哈尔滨-长春-沈阳-天津-北京-太原-石家庄-济南-郑州-西安-成都-重庆-贵阳-长沙-武汉-合肥-南京-上海-杭州-南昌-福州-台北-香港-澳门-广州-海口-南宁-昆明-拉萨-乌鲁木齐-西宁-兰州-银川-呼和浩特-哈尔滨
问题二
方法同问题一相同，依然用贪心法编写程序，运行。
程序如下：
for(i=0;i
s[i]=0;
for(j=0;j
{
for(i=0;i
{
dingwei[i]=dist[number][i];
}
s[number]=1;
printf("%s->",getCityName(number));
min=MAX;
for(k=0;k
{
if(s[k]==0&&min>dingwei[k])
{
min=dingwei[k];
number=k;
}
if(u==M)
min=dingwei[n];
}
u++;
distance+=min;
//printf("距离为:%d\n",min);
}
printf("%s",getCityName(n));
printf("\n距离为:%d\n",distance);
数据结果：
哈尔滨-长春-沈阳-北京-天津-石家庄-太原-郑州-济南-南京-上海-杭州-合肥-武汉-长沙-南昌-福州-台北-香港-澳门-广州-海口-南宁-昆明-贵阳-重庆-西安-成都-拉萨-西宁-乌鲁木齐-兰州-银川-呼和浩特-哈尔滨
问题三
经综合考虑，决定采用回溯法
（TSP中的回溯算法）
算法描述
旅行售货员问题的解空间是一棵排列树。在递归算法中，当i=n时，当前扩展结点是排列树的叶结点的父结点。此时算法检测图G是否存在一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边。如果这两条边都存在，则找到一条旅行售货员回路，此时，算法还需判断这条回路的费用是否优于当前已找到的最优回路的距离V。如果是，则必须更新当前最优值bestV和当前最优解bestx。
回溯法核心代码：
void backtrack(int t,int** dist)
{
if(t>M-1)
{
v+=dist[0][x[M-1]];
if(v
{
bestV=v;
for(int i=0;i
bestX[i]=x[i];
}
inc++;
printf("第%d种遍历路线总距离:%d\n",inc,v);
v-=dist[0][x[M-1]];
return;
}
for(int i=t;i
{
swap(x,i,t);
v+=dist[x[t-1]][x[t]];
if(v
backtrack(t+1,dist);
v-=dist[x[t-1]][x[t]];
swap(x,i,t);
}
}
void swap(int a[],int i,int j)
{
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
数据输出结果：
哈尔滨-长春-沈阳-北京-天津-石家庄-太原-郑州-济南-南京-合肥-武汉-长沙-杭州-南昌-福州——台北——澳门——海口-广州-香港-南宁-贵阳-昆明-成都-西安-兰州-西宁-拉萨——重庆——乌鲁木齐——银川-呼和浩特——哈尔滨
复杂性分析
本题的复杂性主要体现在数据和编程两方面，本题的实际数据量可谓相当庞大，不仅处理起来较为困难，对于计算机计算能力的要求也会很高，权衡了数学建模的实际情况后，我们决定通过假设减少数据量，假设的提出对于建模最优解会产生一定影响，但却使建模更加接近实际情况。总的来说，假设 使建模的复杂度大大降低，并处于可接受范围内。对于编程来说，也不可不谓复杂且庞大，尤其是遗传算法的编程，好在遗传算法方面已形成了较为固定且可行的算法与程序，我们只需要稍作修改便可应用到本题，这使得本题的复杂度也大大降低。
可行性分析
通过程序的运行和最终结果的比较，我们可以说，本题的建模完全可行，且因为建模过程中参与计算的真实数据较多，我们又可以说，本建模完全可以应用到实际生活当中，并给予决策以辅助意见。可我们又想，真的会有人在旅行前以计算机运行出的不带任何“血色”的结果作为自己旅游路线吗？
误差分析
本题因涉及到众多真实情况，使得消除误差，甚至是稍微减少误差都变得异常的艰难。我们减少误差的方法是：在不对建模造成“灾难性影响”的前提下，尽可能多的引入真实数据，使建模在顺利进行的前提下，尽可能接近真实。这里所谓“灾难性影响”即是指在引入一类真实数据后，建模在数据规模、计算量（主要体现在运行时间上）等方面超出可承受范围，对于此情况，我们将用理想化假设的量代替真实量，建模虽在不同程度上偏离真实情况，但却可以成功运行。
本题误差主要由以下几个方面影响：
遗传算法解决TSP（即旅行问题），实质上是解决一个环形最短路径问题，但这里的“路径”实际上只是两点间一边的权值，这个权可以表述任何实际量，包括距离、价钱等。因此，本题应用遗传算法时，只需将这个权值赋予我们需要的意义即可。
因为遗传算法解决TSP问题已经形成了公认可行的方案，所以本题不再对于遗传算法进行过多阐述，本文只说明遗传算法是如何应用本题的。
计算过程结合了群体演化、交叉算子、局部启发式算子等方法，利用程序获得结果（由假设限制种群规模）。
收敛准则
连续 代不再出现更优染色体
优化解的染色体占种群个数达 比例以上。
当两准则均满足时，终止运算，输出优化结果和对应目标函数值。
采用群体演化能够保证搜索快速收敛，且注重全局性，即更加接近理想优化解。
由假设保存有希望成为最优化的边，提高了初始群体质量也提高了函数收敛速度。
小游你好:
爸爸已经决定了这次环游中国的路线。行程如下：
从哈尔滨出发后，我会乘火车一路南下。在福州乘飞机到台北，由台北乘飞机经由香港、澳门到达海口。这些城市坐飞机要比坐火车更加方便。在海口我会乘火车向西北进发。最终经由青藏铁路到达拉萨。在拉萨，因考虑到时间问题，我决定乘飞机由拉萨经过重庆、乌鲁木齐到达银川。由银川乘火车到达呼和浩特。由于呼和浩特到哈尔滨路程过远，我决定乘飞机回到哈尔滨。祝我一路顺风吧！
论最优路径——走遍全中国摘要.doc
