将点之间的距离转换为点
本文关键字：转换 距离 之间 | 更新日期: 2023-09-27 17:56:24
给定一个起点和一个距离，计算终点。我有一个与客户的矩阵，它是彼此之间的距离。（见链接jsfiddle）
矩阵：http://jsfiddle.net/j69kA/
如何根据中心点将其更正转换为坐标点 （X， Y） ？可以是 1。
1 2 3 4 5 6 7 8 9 10
1 0 24 15 27 19 16 11 33 28 30
2 24 0 28 32 29 17 20 20 27 30
3 15 28 0 19 22 12 22 29 29 15
4 27 32 19 0 29 23 13 31 20 28
5 19 29 22 29 0 24 25 17 22 23
6 16 17 12 23 24 0 22 23 21 12
7 11 20 22 13 25 22 0 28 23 19
8 33 20 29 31 17 23 28 0 28 22
9 28 27 29 20 22 21 23 28 0 25
10 30 30 15 28 23 12 19 22 25 0
不幸的是，
你想做的事情是不可能的。
为什么？
因为有不止一组点可以产生上面的距离矩阵。
为了证明这一点，假设你有一个点地图，其距离对应于该矩阵。
现在在 Y 轴上反映此地图。相对距离都不变=>不同的点图，相同的矩阵！
现在在 X 轴上反映此地图。相对距离都不变=>不同的点图，相同的矩阵！
现在将其旋转 90 度。同样，距离不变=>相同的矩阵！
你看到这里的模式了吗？
事实上，有无数个可能的 X，Y 点集可以生成您上面显示的距离矩阵。
简而言之，没有一对一的映射。这是多对一的。当你从一组点转到一个距离矩阵时，你会丢弃有价值的信息，之后你无法取回它。
如果你只是想得到点之间的最短路径（并且不关心坐标系），那么 Dijkstra 的算法就是你需要的。
在您的情况下，每个点之间都有直接距离，但可能想看看间接路径是否会更短。在这种情况下，以下控制台应用（刚刚编写且除数据外基本上未经测试）应执行所需的操作：
namespace DijkstraTest
{
class Node
{
public Node(int index)
{
distanceFromStart = -1;
this.index = index;
}
public int distanceFromStart;
public bool visited;
public Node parent;
public int index;
}
class Dijkstra
{
private int[,] distanceMatrix;
private int size;
public Dijkstra(int[,] distanceMatrix)
{
this.distanceMatrix = distanceMatrix;
size = distanceMatrix.GetLength(0);
if (distanceMatrix.Rank != 2 || (size != distanceMatrix.GetLength(1)))
throw new ArgumentException("Matrix must be 2-D and square!");
}
public List<Node> GetShortestPath(int startPos, int endPos)
{
var nodes = Enumerable.Range(0, size).Select(i => new Node(i)).ToList();
nodes[startPos].distanceFromStart = 0;
var endNode = nodes[endPos];
while (!endNode.visited)
{
var currentNode = nodes.Where(i => !i.visited && i.distanceFromStart != -1)
.OrderBy(i => i.distanceFromStart).First();
foreach (var neighbour in nodes
.Where(i => !i.visited && distanceMatrix[currentNode.index, i.index] != -1))
{
var thisDistance = currentNode.distanceFromStart +
distanceMatrix[currentNode.index, neighbour.index];
if (neighbour.distanceFromStart == -1 || neighbour.distanceFromStart > thisDistance)
{
neighbour.distanceFromStart = thisDistance;
neighbour.parent = currentNode;
}
}
currentNode.visited = true;
}
// build the results working back
var retVal = new List<Node> {endNode};
while (endNode.parent != null)
{
endNode = endNode.parent;
retVal.Add(endNode);
}
retVal.Reverse();
return retVal;
}
}
class Program
{
static int[,] DistanceMatrix = {{-1, 24, 15, 27, 19, 16, 11, 33, 28, 30},
{24, -1, 28, 32, 29, 17, 20, 20, 27, 30},
{15, 28, -1, 19, 22, 12, 22, 29, 29, 15},
{27, 32, 19, -1, 29, 23, 13, 31, 20, 28},
{19, 29, 22, 29, -1, 24, 25, 17, 22, 23},
{16, 17, 12, 23, 24, -1, 22, 23, 21, 12},
{11, 20, 22, 13, 25, 22, -1, 28, 23, 19},
{33, 20, 29, 31, 17, 23, 28, -1, 28, 22},
{28, 27, 29, 20, 22, 21, 23, 28, -1, 25},
{30, 30, 15, 28, 23, 12, 19, 22, 25, -1}};
static void Main(string[] args)
{
var dijkstra = new Dijkstra(DistanceMatrix);
for (int i = 0; i < 10; i++)
{
for (int j = i; j < 10; j++)
{
var path = dijkstra.GetShortestPath(i, j);
// print complex paths that are shorter than just going straight there...
if (path.Count > 2)
{
Console.Write("From {0} to {1}: ", i,j);
foreach (var item in path)
{
Console.Write(" {0} ", item.index);
}
Console.WriteLine(": Total distance: {0}, Direct distance: {1}",
path.Last().distanceFromStart, DistanceMatrix[i,j]);
}
}
}
}
}
它非常粗糙和准备好，但它似乎产生了合理的输出。使用距离矩阵，您将获得以下输出（间接路径比直接路径短）：
From 0 to 3: 0 6 3 : Total distance: 24, Direct distance: 27
From 0 to 9: 0 5 9 : Total distance: 28, Direct distance: 30
From 1 to 9: 1 5 9 : Total distance: 29, Direct distance: 30
它基于此处的维基百科文章，直接翻译成 C#。
要构建笛卡尔系统，您需要两个点 ->起点，目的地
矩阵仅包含两点之间的距离，不包含起点和目的地。
您需要将其转换为笛卡尔系统（使用 XY 平面）。
你说原点是1。
你会如何建议这个系统，因为它不可能是笛卡尔的，因为在这种情况下，你想要目的地点。
我建议使用极坐标系，两点之间的角度相等。
编辑：从 http://www.c-program-example.com/
用：
#include "stdio.h"
#define infinity 999
void dij(int n,int v,int cost[10][10],int dist[])
{
int i,u,count,w,flag[10],min;
for(i=1;i<=n;i++)
flag[i]=0,dist[i]=cost[v][i];
count=2;
while(count<=n)
{
min=99;
for(w=1;w<=n;w++)
if(dist[w]<min && !flag[w])
min=dist[w],u=w;
flag[u]=1;
count++;
for(w=1;w<=n;w++)
if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
dist[w]=dist[u]+cost[u][w];
}
}
void start()
{
int n,v,i,j,cost[10][10],dist[10];
printf("'n Enter the number of nodes:");
scanf("%d",&n);
printf("'n Enter the cost matrix:'n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=infinity;
}
printf("'n Enter the source matrix:");
scanf("%d",&v);
dij(n,v,cost,dist);
printf("'n Shortest path:'n");
for(i=1;i<=n;i++)
if(i!=v)
printf("%d->%d,cost=%d'n",v,i,dist[i]);
}