uva 1347 - Tour(双调欧几里得旅行商问题） - 推酷
uva 1347 - Tour(双调欧几里得旅行商问题）
题目大意：给出n个点，确定一条
连接各点的最短闭合旅程的问题。
解题思路：dp[i][j]表示说从i联通到1，再从1联通到j的距离。
dp[i][j] = dp[i-1][j] + dis(i,i-1);
dp[i][i-1] = min (dp[i][i-1], dp[i-1][j] + dis(i, j));
#include &stdio.h&
#include &string.h&
#include &math.h&
#include &algorithm&
const int N = 105;
const double INF = 0x3f3f3f3f3f3f3f3f;
double x[N], y[N], dp[N][N];
inline double dis (int a, int b) {
return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));
void init () {
for (int i = 1; i &= i++)
scanf(&%lf%lf&, &x[i], &y[i]);
memset(dp, 0, sizeof(dp));
dp[2][1] = dis(1, 2);
double solve () {
for (int i = 3; i &= i++) {
dp[i][i-1] = INF;
for (int j = 1; j & i-1; j++) {
dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j));
dp[i][j] = dp[i-1][j] + dis(i, i-1);
double ans = INF;
for (int i = 1; i & i++)
ans = min(ans, dp[n][i] + dis(n, i));
int main () {
while (scanf(&%d&, &n) == 1) {
printf(&%.2lf\n&, solve ());
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致　　欧几里得旅行商问题 是对平面上给定的n个点确定一条连接各点的最短闭合旅程的问题。图a给出了7个点问题的解，这个问题的一般形式是NP完全的,故其解需要多于多项式的时间。
　　J.K.Bentley建议通过只考虑双调旅程来简化问题，这种旅程即为从最左点开始，严格从左到最右点，再严格地从最右点回到最左点。图b显示了同样的7个点的问题的最短双调路线，在这种情况下，多项式的时间的算法是有可能的。
　　描述一个确定最优双调路线的O（n^2）时间的算法。可以假设任何两点的x坐标都不相同。
　　读了很多遍这个题，也看了网上好几篇关于这个问题的博客，有很多一部分是错误的却没有更正，于是自己实践整理了一份这个问题的解法。首先最大的疑惑在于理解什么叫做双调（Bitonic），读了很多解释的词条大概了解了双调的用处，我所理解的双调在这道题之中的思路就是将整个闭合的路线一个点展开，因为题中要求的是从左端向右端扫描，再从右端扫描回来。那么不妨将最左端的点作为出发点开始进行计算（从右端完全一致，不再赘述）。
　　我们需要一个辅助的矩阵a[iLen+1][iLen+1]，和所有动态规划问题一样矩阵的大小都是问题的规模+1，整个的计算过程是从左端到右端，也就是我们计算的最短路经从左端向右端生长的过程，辅助矩阵a[i][j]指的是p[i]到p[1]和p[1]到p[i-1]&共通&的最短路径，计算过程只利用矩阵的下三角部分，所以使前一个索引小与后一个索引。首先，将iLen个点存储到一个结构体/类数组之中，用来存放所有的点的坐标，记作数组p，p1,p2之间的距离记作dist（p1,p2）。
核心思想：
1）（前提）当我们计算第i个点或者将它并入最短路径的时候，前1.2.3...i-1个点已经形成了一条最短路径。
2）若要计算a[i][j]，新加入的点p[j]的选择分支有三种，也就是路线规划&生长&情况有且只有三种：
　　（一）当j-1〉i时，根据第（1）条我们需要做的就是在辅助矩阵中已经形成的子最短路径加上新增的边（按定义必然是先添加在更长的那半部分路线）
　　　　　就有 a[i][j]=a[i][j-1]+dist(j-1,j);
　　（二）当j-1=i时，就是一次总结前面的子最短路径生成更长的新子最短路径的时候。
　　　　　表示为 a[i][j]=min{(a[k][j-1]+dist(k,j)) , (a[k-1][j-1])+dist(k-1,j)....}////k为遍历值
&　& （三）当j=i 时，将整个图形封闭起来需要最后的两条边，实质上是（二）过程的一个分支
　　　　　即& a[i][j]=min{(a[k][j-1]+dist(k,j)+dist(j-1.j)).....}/////////k为遍历值
#include&iostream&
#include&vector&
#include&cstdlib&
#include&cmath&
#define MAX_VALUE 99999
class Point{
Point(double px=0,double py=0)
:x(px),y(py){}////////Constructor & Default to be Zero
double dist(Point p1,Point p2){
return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
int main(){
const int iLen=7;
Point p[iLen+1];//// Pointer List
p[1]=Point(0,6);
p[2]=Point(1,0);
p[3]=Point(2,3);
p[4]=Point(5,4);
p[5]=Point(6,1);
p[6]=Point(7,5);
p[7]=Point(8,2);
//////////////To minimize the time of Debugging
We get parameters initialize
double a[iLen+1][iLen+1]={}; ////null-filled
for(int j=3;j&=iLj++){
for(int i=1;i&=j-2;i++){
a[i][j]=a[i][j-1]+dist(p[j-1],p[j]);
a[j-1][j]=MAX_VALUE;
for(int i=1;i&=j-2;i++){
a[j-1][j]=(a[i][j-1]+dist(p[i],p[j]))&a[j-1][j]?(a[i][j-1]+dist(p[i],p[j])):a[j-1][j];
double dMin=MAX_VALUE;
for(int i=2;i&=iLen-1;i++){
double tmp=a[i][iLen]+dist(p[i],p[iLen])+dist(p[iLen-1],p[iLen]);
if(tmp&dMin)dMin=
///////////dMin records the answer
std::cout&&dMin&&std::
阅读(...) 评论()您的位置： &
求解旅行商问题的一个有效算法
优质期刊推荐6351人阅读
算法导论（81）
一、题目&二、思考先做以下定义：对所有点按x坐标排序，从0开始依次为每个点编号，令（1）两条路径分别为A和B，且起点都是点0，方向严格向右（2）A[i]表示路径A的一种状态，起点为点0，终点为点i，方向严格向右，0&=i&n（3）B[j]表示路径B的一种状态，起点为点0，终点为点i，方向严格向右，0&=j&n（4）d[i][j]为点i与点j之间的距离（5）s[i][j]为满足以下条件的A[i]和B[j]的路径和的最小长度:a)A[i]和B[j]包含了所有的0-max(i,j)中的点；b)A[i]和B[j]中没有重复了点（除了点0，或i=j时的点i）经过以上定义，题目可以化简为求s[n-1][n-1]的值。&推导过程画图就可以得出。程序不复杂，根据以上公式对照写出&三、代码
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：762683次
积分：12003
积分：12003
排名：第918名
原创：363篇
转载：34篇
译文：20篇
评论：664条
阅读：8356
文章：27篇
阅读：124973
(4)(11)(10)(10)(9)(10)(3)(13)(10)(8)(5)(5)(5)(3)(1)(4)(1)(2)(3)(1)(4)(1)(1)(2)(1)(2)(4)(1)(3)(3)(4)(18)(37)(22)(21)(32)(16)(3)(12)(67)(49)1292人阅读
动态规划-非递归求解（21）
Disk Schedule
Time Limit:
MS (Java/Others)&&& Memory Limit:
K (Java/Others)
Total Submission(s): 1463&&& Accepted Submission(s): 189
Problem Description
有很多从磁盘读取数据的需求，包括顺序读取、随机读取。为了提高效率，需要人为安排磁盘读取。然而，在现实中，这种做法很复杂。我们考虑一个相对简单的场景。磁盘有许多轨道，每个轨道有许多扇区，用于存储数据。当我们想在特定扇区来读取数据时，磁头需要跳转到特定的轨道、具体扇区进行读取操作。为了简单，我们假设磁头可以在某个轨道顺时针或逆时针匀速旋转，旋转一周的时间是360个单位时间。磁头也可以随意移动到某个轨道进行读取，每跳转到一个相邻轨道的时间为400个单位时间，跳转前后磁头所在扇区位置不变。一次读取数据的时间为10个单位时间，读取前后磁头所在的扇区位置不变。磁头同时只能做一件事：跳转轨道，旋转或读取。现在，需要在磁盘读取一组数据，假设每个轨道至多有一个读取请求，这个读取的扇区是轨道上分布在
0到359内的一个整数点扇区，即轨道的某个360等分点。磁头的起始点在0轨道0扇区，此时没有数据读取。在完成所有读取后，磁头需要回到0轨道0扇区的始点位置。请问完成给定的读取所需的最小时间。
输入的第一行包含一个整数M（0&M&=100），表示测试数据的组数。对于每组测试数据，第一行包含一个整数N（0&N&=1000），表示要读取的数据的数量。之后每行包含两个整数T和S（0&T&=1000，0&= S&360），表示每个数据的磁道和扇区，磁道是按升序排列，并且没有重复。
对于每组测试数据，输出一个整数，表示完成全部读取所需的时间。
Sample Input
Sample Output
&&&& 本题背景可以转化为旅行商问题，刚接触算法就知道旅行商问题是NP问题。所以一直想有没有贪心思想可以找到某个贪心策略，简化问题，尝试写了一些对比公式，最终还是错了。就在网上搜了搜旅行商问题，结果看到双调欧几里得旅行商问题。这里双调是指二维坐标的其中一维是单调的，于是问题简化了很多，可以尝试动态规划。题目旋转一周的时间是360个单位时间，跳转到一个相邻轨道的时间为400个单位时间，暗示换轨道比旋转一周更花时间，所以得知最好顺着归到依次读取。类比二维坐标系：&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&& 上图&中a是最短旅行商路线，但不是双调的；b是最短双调旅行商路线。
求解过程：
（1）首先将各点按照x坐标从小到大排列，时间复杂度为O(nlgn)。
（2）寻找子结构：定义从Pi到Pj的路径为：从Pi开始，从右到左一直到P1，然后从左到右一直到Pj。在这个路径上，会经过P1到Pmax(i,j)之间的所有点且只经过一次。在定义dp(i,j)为满足这一条件的最短路径。我们只考虑i&=j的情况。同时，定义dist(i,j)为点Pi到Pj之间的直线距离。
（3）最优解：我们需要求的是dp(n,n)。关于子问题dp(i,j)的求解，分三种情况：
&&&& A、当j & i - 1时，dp(i,j) = dp(i-1,j) + dist(i - 1,i)。由定义可知，点Pi-1一定在路径Pi-Pj上，而且又由于j&i-1,因此Pi的左边的相邻点一定是Pi-1.因此可以得出上述等式。
&&&& B、当j = i - 1时，与Pi左相邻的那个点可能是P1到Pi-1总的任何一个。因此需要递归求出最小的那个路径：dp(i,j) = dp(i,i-1) = min{dp(k,j) + dist(i,k)},其中1 &= k &= j。
&&&& C、当j=i时，路径上最后相连的两个点可能是P1-Pi、P2-Pi...Pi-1-Pi。因此有：dp(i,i) = min{dp(i,1)+dist(1,i),...,dp(i,i-1)+dist(i-1,i)}。
&& 在此声明，上述算法思想转自这篇博客，在此表示感谢！
&&&& 可能比较难理解，下面谈谈我的理解。dp(i,j)表示从i到1再从1出发到j且经过其中的所有点，假设i&j。可以理解为2个人，一个跑得快用i表示，另一个跑得慢用j表示。达到i可能是跑得快的，如图a；也可能是跑得慢的，如图b .
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& &
&&&&&& &对于a,有dp(i,j)=dp(i-1,j)+dist(i-1,i);
&&&&& 对于b,求dp(i,i-1)。即从j直接跳到i，此时慢的、快的互换角色，即i,j互换，枚举j的位置，即dp(i,j)=dp(i,i-1)=min(dp(i,i-1),dp(i-1,k)+dist(k,i));
贴段代码：
#include&iostream&
#include&cstdio&
#include&cstring&
#include&cmath&
const int INF=100*;
const int MAXN=1000+10;
struct point
point vert[MAXN];
int res[MAXN][MAXN];
int dis(int i,int j)
int t=abs(vert[i].x-vert[j].x)*400;
int x1,x2;
if(vert[i].y&vert[j].y)
x1=vert[i].y;
x2=vert[j].y;
x1=vert[j].y;
x2=vert[i].y;
int l=x2-x1;
int r=360-x2+x1;
return (l&r?l:r)+t;
int min(int a,int b)
return a & b ? a :
int work(int n)
int s,Min=INF;
res[2][1]=dis(2,1);
for(i=2;i&=n;i++)
for(j=1;j&i;j++)
res[i][j]=min(res[i][j],res[i-1][j]+dis(i-1,i));
res[i][i-1]=min(res[i][i-1],res[i-1][j]+dis(j,i));
for(i=1;i&n;i++)
s=dis(i,n);
if(Min & res[n][i] + s) Min = res[n][i] +
int main()
int i,j,n,
while(cas--)
scanf(&%d&,&n);
vert[1].x=0;
vert[1].y=0;
for(i=2;i&=n+1;i++)
scanf(&%d%d&,&vert[i].x,&vert[i].y);
for(i=1;i&=n+1;i++)
for(j=1;j&=n+1;j++) res[i][j]=INF;
printf(&%d\n&,work(n+1)+n*10);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：298206次
积分：7747
积分：7747
排名：第2121名
原创：473篇
转载：54篇
评论：97条
姓名：XuJin
专业：计算机科学与技术
工作：帝都码农
专注：算法、 数据结构
github：/XuJin1992
(2)(1)(4)(8)(1)(1)(4)(3)(4)(1)(1)(4)(1)(1)(6)(11)(11)(5)(2)(5)(3)(19)(30)(3)(7)(12)(58)(1)(1)(38)(109)(63)(37)(73)}