汕头网站制作全过程,内网安装wordpress,两学一做网站网址大全,wordpress汉化主题原题链接#xff1a;https://www.luogu.com.cn/problem/P1523
题目背景
欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解#xff0c;但是有…原题链接https://www.luogu.com.cn/problem/P1523
题目背景
欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解但是有办法在多项式时间内求出一个较优解。
为了简化问题而且保证能在多项式时间内求出最优解J.L.Bentley 提出了一种叫做 bitonic tour 的哈密尔顿环游。它的要求是任意两点 (a,b) 之间的相互到达的代价 dist(a,b)dist(b,a) 且任意两点之间可以相互到达并且环游的路线只能是从最西端单向到最东端再单项返回最西端并且是一个哈密尔顿回路。
题目描述
本题为著名的 NPC 难题的简化版本。
现在笛卡尔平面上有 (n≤1000) 个点每个点的坐标为(x,y)x,y且为整数任意两点之间相互到达的代价为这两点的欧几里德距离现要你编程求出最短 bitonic tour。
输入格式
第一行一个整数 n。
接下来 n 行每行两个整数 x,y表示某个点的坐标。
输入中保证没有重复的两点保证最西端和最东端都只有一个点。
输出格式
一行即最短回路的长度保留 2位小数。
输入输出样例
输入 #1
7
0 6
1 0
2 3
5 4
6 1
7 5
8 2输出 #1
25.58说明/提示
题目来源
《算法导论第二版》 15-1
解题思路 这个题目是npc问题的简化版也就是旅行商问题的简化版 简化之后很像P1006 [NOIP2008 提高组] 传纸条 这俩个题目的解题思想非常的像但是又不完全相同因为传纸条这个题目走的过程中间俩个人是允许走同一个点的只是效益只计算一次但是这个题目俩个人不允许走同一个点首先我们利用类似传纸条这题的思想对题目进行类似转换对于本题我们同样可以将来回走变为俩个人一起从西边的点走到东边的点这样就将原问题转换为了有俩个人从最西边的点都走到最东边的点并且中间的每个点走且只走一次这样我们就可以根据传纸条这题的思想来设计状态了注意走的过程中由于不能走同样的点所以走的过程中必然一个在前一个在后我们还需要对于所有点按照横坐标从小到达排序。 状态定义 定义f[i][j]表示后面那个人走到i这个点前面那个人走到j这个点并且ij并且1~j之间的所有点都走过一次了的最短距离。 初始化 由于必须从西往东依次走过每一个点我们最开始一定后面那个人在1号点前面那个人在2号点所以初始化为f[1][2]d[1][2] 状态转移 当前i在后面,j在前面1~j之间的所有点都已经走过了接下来要走的点是j1,那么存在俩种情况 (1)让j走到j1,i暂时不动 (2)让i走到j1,j暂时不动,会导致i走到j前面为了保证前后性我们交换i,j的位置 j走到j1,i暂时不动 f[i][j 1] min(f[i][j 1], f[i][j] d[j][j 1]); i走到j1,j暂时不动并且需要交换ij位置原本i变为j1j还是j现在交换变为i变为jj变为j1,交换位置才能保证前面那个仍然在前面后面那个也仍然在后面。 f[j][j 1] min(f[j][j 1], f[i][j] d[i][j 1]); 最终答案 最后一步一定是前面那个人已经到达了n号点后面那个人可以在中间的任意一个点后面那个人还没有到达终点然后后面那个人走到n号点(终点)所以答案就是所有的min(f[i][n]d[i][n])(1in) 时间复杂度第一维枚举后面那个人当前所在点时间为O(n)第二维枚举前面那个人当前所在点时间为O(n)最终时间复杂度为O(n^2)n1000最终时间就是1e6这个时间复杂度是肯定可以过的。 空间复杂度俩个数组都是二维空间复杂度为O(n^2)。 cpp代码如下
#include cstdio
#include cstring
#include iostream
#include algorithm
#include cmathusing namespace std;const int N 1010;int n;
struct points
{double x, y;
} a[N]; // 存储所有点的坐标
double f[N][N], d[N][N];double get_distance(points u, points v) // 计算俩点之间的距离
{double dx u.x - v.x, dy u.y - v.y;return sqrt(dx * dx dy * dy);
}
int main()
{cin n;for (int i 1; i n; i)scanf(%lf%lf, a[i].x, a[i].y);// 按照横坐标从小到达排序sort(a 1, a 1 n, [](points A, points B){ return A.x B.x; });// 初始化距离数组d和dp数组ffor (int i 1; i n; i)for (int j 1; j n; j){d[i][j] d[j][i] get_distance(a[i], a[j]);f[i][j] 1e30;}// 初始时走在后面的那个人在1号点走在前面的那个人在2号点由于必须是从习往东一次走每个点所以最开始俩人必然在1,2号点f[1][2] d[1][2];for (int i 1; i n; i)for (int j i 1; j n; j) // 前面那个人要在后面那个人前面所以这里从i1开始枚举{/*当前i在后面,j在前面1~j之间的所有点都已经走过了接下来要走的点是j1,那么存在俩种情况(1)让j走到j1,i暂时不动(2)让i走到j1,j暂时不动*/// j走到j1,i暂时不动f[i][j 1] min(f[i][j 1], f[i][j] d[j][j 1]);// i走到j1,j暂时不动f[j][j 1] min(f[j][j 1], f[i][j] d[i][j 1]);}/*最后一步一定是前面那个人已经到达了n号点后面那个人可以在中间的任意一个点后面那个人还没有到达终点然后后面那个人走到n号点(终点)所以答案就是所有的min(f[i][n]d[i][n]) (1in)*/double ans 1e30;for (int i 1; i n; i)ans min(ans, f[i][n] d[i][n]);printf(%.2lf\n, ans);return 0;
}
