点到点之间的距离转换

Question

给定起点和距离，计算目标点。我有一个矩阵与客户，这是彼此之间的距离。(见链接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

Answer 1

不幸的是，你想要做的事情是不可能的。

为什么？

因为有不止一组点会产生上面的距离矩阵。

为了证明这一点，假设你有一个点的地图，它的距离对应于这个矩阵。

现在在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#。

Answer 2

要构建笛卡尔系统，您需要两点->原点，目的地

矩阵只包含两点之间的距离，而不包含起源和目的地的距离。

您需要将其转换为笛卡尔系统(使用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]);
}