O（N ^ 2）最短路径算法-Java 学习之路

问题表明我们有一组带有坐标的点，我们必须找到始终在（0,0）到达目的地的最短路径，然后再返回到（0,0）只传递一次所有中间点 .

第一行上的输入看起来是中间点的数量，第二行是目的地的坐标，然后是所有中间点的坐标 . 没有中间点具有相同的x坐标，并且每个中间点的x坐标小于目标的x坐标 .

我在编程语言C中实现了这个问题，但问题是我无法理解它 . 我已经逐步完成了它，但我无法理解它的作用 .

#include <fstream>
#include <cmath>
#include <algorithm>
#include <limits>

using namespace std;

const double inf = numeric_limits<double>::max(); // an infinite number

double dist [205][205] = {0};    
double res  [205][205] = {0};
int N (0);


struct point {
  double x,y;
  point(int a,int b):x(a),y(b){} 
   point(){}
}points[205];  //struct to store inbetween points

inline const bool operator < ( const point &a, const point &b ){
  return a.x < b.x;
}

int main()
{

ifstream in  ("evripos.in");
ofstream out ("evripos.out");

in>>N;
N+=2;

int t1,t2;

points[0]= point(0,0);

// stores all points 
for(int i=1;i<N;++i){
  in>>t1>>t2;
  points[i]=point(t1,t2);
}               

in.close();
sort(points,points+N); // sorts all points according to their x coordinate

// creates a 2 dimensional array of the distances between all points
// called dist
for(int i=0;i<N;++i)
  for(int j=0;j<N;++j){
    dist [i][j]= sqrt( pow(points[i].x-points[j].x,2) + pow(points[i].y-points[j].y,2));;
    res[i][j]=inf;
  }                

// computes the result, using a 2 dimensional array called res
res[0][0]=0;
for(int i=0;i<N;++i)
  for(int j=0;j<N;++j){
   res[i+1][i]   = min (res[i+1][i],   res[i][j] + dist[j][i+1]);
   res[i+1][j]   = min (res[i+1][j],   res[i][j] + dist[i][i+1]);
   res[i+1][i+1] = min (res[i+1][i+1], res[i][j] + dist[i][i+1] + dist[i+1][j]);  
  }     

out<<round(res[N-1][N-1])<<endl;       //stores the end result
out.close();
}

我发现这是一个动态编程问题，据我所知，整个逻辑就在这里

res[0][0]=0;
for(int i=0;i<N;++i)
  for(int j=0;j<N;++j){
   res[i+1][i]  = min (res[i+1][i],   res[i][j] + dist[j][i+1]);
   res[i+1][j]  = min (res[i+1][j],   res[i][j] + dist[i][i+1]);
   res[i+1][i+1]= min (res[i+1][i+1], res[i][j] + dist[i][i+1] + dist[i+1][j]);  
  }

这背后的逻辑究竟是什么？动态编程如何解决这个问题？

1 回答

2
这是Bitonic tour问题 . 你有一个城市列表，从0到N-1，你需要从城市0开始，经过每个城市一次到达N-1，从N-1回到0 .

为了解决这个问题，我们需要 change the way we look at it . 想象一下，没有一个，但 two people starting from city 0 ，他们每个人永远不会在同一个城市（0和N-1除外），他们都试图到达城市N-1 . 因此，如果我们添加Person one和Person 2所采用的路径，我们就可以得到原始问题的答案 .

所以，我们有 int [][]res ， res[i][j] 表示第一人的最小总距离在城市 i ，第二人在城市 j . 我们观察到这一行
```
res[i+1][i]      = min (res[i+1][i],   res[i][j] + dist[j][i+1]);
```
表示从城市 j 开始的人员2将转到城市 i + 1 . 请注意 i + 1 ，而不是 i ，这将避免两个人在同一个城市时的情况 . （另请注意 i 和 j 的作用可以互换）

同样
```
res[i+1][j]    = min (res[i+1][j],   res[i][j] + dist[i][i+1]);
```
意味着从 i 开始的人员去城市 i + 1 .

最后，假设目的地位于 i + 1 ，我们有
```
res[i+1][i+1]= min (res[i+1][i+1], res[i][j] + dist[i][i+1] + dist[i+1][j]);
```
Note ：顺便说一下，我们在外部 for 循环中将索引从 i 增加到 i + 1 ，我们也保证在到达城市 i + 1 之前已经到达了所有从0到i的城市（由一个或两个人） .

所以，问题的答案将在 res[N-1][N-1]

希望有所帮助！
回复于 2024-05-15T07:33:26+08:00

O（N ^ 2）最短路径算法

1 回答

相关问题