代码之家 › 专栏 › 技术社区 › Sandra K

如何根据距离矩阵确定节点?

graph c++

Sandra K · 技术社区 · 6 年前

假设我已经得到了:

A & GT;B 十

A & GT;C 五

a & gt;d 七点五

B & GT;C 十二

B&G.D 十七

C & gt;D 五

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

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

1 回复 | 直到 6 年前

ravenspoint 6 年前

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