如何根据距离矩阵确定节点? [英] How to determine nodes based on distances matrix?

问题描述

说我有一个给定的:

A-> B 10

A-> C 5

A-> D 7.5

B-> C 12

B-> D 17

C-> D 5

然后，我收到未排序的输入，如下所示:

Then, I receive an unsorted input, something like below:

    K   L   M   N
K   0   10  12  17
L   10  0   5  7.5
M   12  5   0   5
N   17  7.5 5   0

我必须确定(对于任何类型的输入-任何顺序)哪个节点(K，L，M和N)实际上是A，B，C和D.

I have to determine(for any sort of input - of any order) which node (K, L, M & N) is actually the A, the B, the C and the D.

对于上面的示例输入，这里的情况是A is L，B is K，C is M& D is N.

For the above example input, the case here is that A is L, B is K, C is M & D is N.

所以我已经开始了一些事情，但是我仍然不确定如何继续.下面为我​​提供了std :: map，其中输入的哪一行是给定的行.但是，即使我知道这种组合的存在，我也不知道如何知道未知数(城市的顺序).有人可以帮助我对输入进行排序以使其与给定的匹配吗?

So I have started something, but I am still not sure how to continue. The below provides me with a std::map of which row of the input, is the row of the given. But then, I am not sure how to know the unknown (order of cities) even when I know that combination exists. Can someone help me sort the input to match the given?

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

bool checkForSimilar(vector<double> Vec1, vector<double> Vec2)
{
   std::sort(Vec1.begin(), Vec1.end());
   std::sort(Vec2.begin(), Vec2.end());

   return std::equal(Vec1.begin(), Vec1.end(), Vec1.begin(), Vec2.end());
}

int main()
{
   vector<vector<double>> GivenDistances = {  // A   B   C   D
                                          /*A*/ {0,  10, 5,  7.5},
                                          /*B*/ {10, 0,  12, 17 },
                                          /*C*/ {5,  12, 0,  5  },
                                          /*D*/ {7.5,17, 5,  0  }};

   vector<vector<double>> InputDistances = {  // K   L   M   N
                                          /*K*/{ 0,  10, 12, 17 },
                                          /*L*/{ 10, 0,  5,  7.5},
                                          /*M*/{ 12, 5,  0,  5  },
                                          /*N*/{ 17, 7.5,5,  0  }};

   std::map<int, int> RowMatches;
   for (int i = 0; i < InputDistances.size(); i++)
   {
      for (int j = 0; j < InputDistances[i].size(); j++)
      {
         // check if current row is any combination if GivenDistances
         if (checkForSimilar(InputDistances[i], GivenDistances[j]))
         {
            RowMatches[i] = j;
         }
      }
   }

   // How to order then them??


   int pause; 
   cin >> pause;
   return 0;
}

推荐答案

解决问题的函数:

    /** Solve problem posed in https://stackoverflow.com/q/52046650/16582

    Search for a permuted column in the input matrix
    which matches each given column

    @param[out] assign  the first node assignment which creates a match
    @param[in]  distance  the distances between nodes, given and input

    Mean time to find match ( milliseconds )

    <pre>
    Cities      Search1      Search2
    10            20           0.01
    100           ???          4
    </pre2>

    */

void Find(
    cNodeAssign& assign,
    cNodeDistance& distance )
{
    raven::set::cRunWatch R("Search");

    assign.Clear();

    // loop over rows in given distances
    for( int given = 0; given < distance.Size(); given++ )
    {
        // loop over rows in input distances
        for( int input = 0; input < distance.Size(); input++ )
        {
            // check if the input row has already been assigned
            if( assign.Find( input ) )
                continue;

            // check if row and column are permutations of each other
            if( distance.IsPermutation( given, input ))
            {
                // found a match
                assign.Add( input );

                // no need to search further for this row
                break;
            }
        }
    }
}

演示该功能并执行时间分析的主要代码

The main code to demo the function and perform time profiling

int main()
{
    cout << "Original Problem:\n";
    vector<vector<double>> GivenDistances =    // A   B   C   D
    {
        /*A*/ {0,  10, 5,  7.5},
        /*B*/ {10, 0,  12, 17 },
        /*C*/ {5,  12, 0,  5  },
        /*D*/ {7.5,17, 5,  0  }
    };

    vector<vector<double>> InputDistances =    // K   L   M   N
    {
        /*K*/{ 0,  10, 12, 17 },
        /*L*/{ 10, 0,  5,  7.5},
        /*M*/{ 12, 5,  0,  5  },
        /*N*/{ 17, 7.5,5,  0  }
    };

    cNodeDistance dop( GivenDistances, InputDistances );
    cNodeAssign assign( dop.Size() );

    dop.Display();
    Find( assign, dop );
    assign.Display();

    Demo( 4 );

    Demo( 10 );

    Timer( 10 );

    Timer( 100 );
}

用于构建演示应用程序的代码是在此处可用.

The code to build the demo application is available here.

这篇关于如何根据距离矩阵确定节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！