c++ - 如何根据距离矩阵确定节点？

Question

假设我有:

A -> B 10

A -> C 5

A -> D 7.5

B -> C 12

B -> D 17

C -> D 5

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

    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。

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

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

#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;
}

Answer 1

解决问题的函数:

    /** 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;
            }
        }
    }
}

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

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 );
}

构建演示应用程序的代码是 available here .