首先,庆贺一下自己解决了(看懂了传说中的niubility的旅行商问题)
其次,马上要看到著名的贪心算法问题了!心中无比的激动。
旅行商问题描述:平面上n个点,确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的(在多项式时间内可以求出)
J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始,严格地从左到右直至最右点,然后严格地从右到左直至出发点。下图(b)显示了同样的7个点的最短双调路线。在这种情况下,多项式的算法是可能的。事实上,存在确定的最优双调路线的O(n*n)时间的算法。
PS:在一个单位栅格上显示的平面上的七个点。 a)最短闭合路线,长度大约是24.89。这个路线不是双调的。b)相同点的集合上的最短双调闭合路线。长度大约是25.58。
解答思路:采用动态规划思想
1),首先给七个点按从左到右编号(如图所示)
2),定义一个数组:double m[8][8]; //最短路径长度
和一个求两点距离的方法:double d(Del x[],int i,int j)
3),m[i][j]存的是编号 i 点与 编号 j 点的最短距离。首先声明的是:m[i][j]=m[j][i];
所以,m矩阵是一个对称矩阵。即 i 点与 j 点的距离跟j点与i点的矩阵相等。所以这里我们只需要求下三角矩阵m就可以。
4),
对于任意一个点i来说,有两种连接方法,一种是如图(a)所示,i与i-1相连;另一种呢是如图(b),i与i-1不相连。(这里思想的关键)
5),由以上思路得递归公式:(i>j 求的是下三角)
(i==j时): m[i][j]=m[i][j-1]+d[i][j-1] 等于0
(i>j+1时):m[i][j]= m[i-1][j]+d[i-1][i] 通过已经求出的 上一个调节点 i-1
(i=j+1时):m[i][j]=min(1<=k<j)(m[k][j]+d[k][i]) //选择直接相连 还是不相连
//直接相连 m[i][j]=0+d[i][j];
//否则:m[i][j]=m[k][j]+d[k][i]; 通过某一个 最小代价的中间
//调节点来连接
6),求下三角时,i-1 编号的节点 是关键节点。
7),源码如下:
#include <stdio.h>
#include <math.h>
#define MAX 65535
double m[8][8]; //最短路径长度
/ /其中的 i j 分别代表七个点的编号
typedef struct{
double x,y; //横纵坐标
}Del;
double d(Del x[],int i,int j)
{
//计算两点之间距离,如果i,j都大于0返回两点距离,否则返回0
if(i>0&&j>0)
return sqrt((x[i].x-x[j].x)*(x[i].x-x[j].x)+(x[i].y-x[j].y)*(x[i].y-x[j].y));
else
return 0;
}
void Short_Way(Del x[]) //传递进来的 坐标数组
{
//求最短路径长度
int i,j,k;
double w;
for(j=0;j<=7;j++)
m[0][j]=0;
for(i=0;i<=7;i++)
m[i][0]=0;
for(i=1;i<=7;i++) //从左向右
{
for(j=1;j<=i;j++) //从下向上 注意 j<=i
{
if(i==j)
m[i][j]=m[i][j-1]+d(x,i,j-1); //m[i][j]依赖已经求出来的 m[i][j-1]
//初始化时 m[1][1]=0; 因为 = m[1][0]+d(x,1,0)
if(i>j+1)
m[i][j]=m[i-1][j]+d(x,i-1,j); //m[i][j]依赖已经求出来的 m[i-1][j] ??
if(i==j+1)
{
m[i][j]=MAX;
if(j==1) //i=2
m[i][j]=d(x,j,i);
for(k=1;k<j;k++) //计算 是相邻两点 近 还是 经过其他点后 近
{
w=m[k][j]+d(x,k,i);
if(w<m[i][j])
m[i][j]=w;
}
}
m[j][i]=m[i][j]; //对称到 上三角
}
}
}
int main(){
Del x[8];
x[1].x=0.0;
x[1].y=6.0;
x[2].x=1.0;
x[2].y=0.0;
x[3].x=2.0;
x[3].y=3.0;
x[4].x=5.0;
x[4].y=4.0;
x[5].x=6.0;
x[5].y=1.0;
x[6].x=7.0;
x[6].y=5.0;
x[7].x=8.0;
x[7].y=2.0;
Short_Way(x);
printf("%f",m[7][7]);
return 0;
}
分享到:
相关推荐
算法导论15-1思考题:双调欧几里得旅行商问题,时间复杂度O(N^2)
实现3-12双调旅行售货员问题.cpp
最短双调 TSP 回路是欧氏旅行售货员问题的特殊情况。平面上 n 个点的双调 TSP 回路是从最左点开始,严格地由左至右直到最右点,然后严格地由右至左直至最左点,且连接每一个点恰好一次的一条闭合回路。
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
能够使用C++语言编写出一个程序,这个程序能够实现一个功能,就是在网络 上找一条从 点出发,经过 各一次最后返回 的最短路线和最短路程。就是要求解决一个TSP问题。
双调排序的详解,还是比较容易看懂的,可用于cuda并行算法(png)
Bitonic旅行路线问题是欧几里得旅行商问题的简化,这种旅行路线从最左边开始,严格地由左至右到最右边的点,然后再严格的由右至左回到开始点,求最短的路径长度。
双调排序算法Verilog代码,包括仿真结果,适用于FPGA设计中对数值的排序,排序耗费硬件复杂度和时间复杂度随着排序序列中数值个数的上升而上升
bitonic双调排序算法,包括c代码和verilog实现 也可以到我的github页面下载 https://github.com/tishi43/bitonic_my https://github.com/tishi43/bitonic_verilog
是自己做实习作业时候的代码 希望可以给初学的朋友起到点参考作用
CPU串行的BitonicSort双调排序
大数据-算法
基于C++实现的双调排序算法
双调夜行船秋思定PPT课件.pptx
双调折桂令叹世PPT课件.pptx
大数据-算法
讨论了根据给定的双调和函数可以确定一个双解析函数的重要性质(类似于解析函数所具有的性质)。还讨论了双调和函数的Dirichlet问题和变形的Dirichlet问题,并得到了相应的可解性定理。对于双解析函数的Dirichlet...
针对具有微小缺失或破损的图像修复问题,基于变分和偏微分方程理论基础提出一种TV双调和偏微分方程图像修复方法。该模型在Sobolev对偶分布空间H-1(Ω)上考虑一个变分问题,它的Euler-Lagrange方程是一个与多孔介质...
针对采煤机调高系统一旦出现故障,采煤机必须停机检修,影响煤矿生产效率的问题,设计了采煤机双调高系统。主要介绍了采煤机双调高系统的组成及工作原理,通过该系统的应用,降低了液压系统的故障率,提高采煤机开机率。