Как определить узлы на основе матрицы расстояний?

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 is L, B is K, C is M & D is 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 );
}

Код для создания демонстрационного приложения: доступен здесь .