1

青いオブジェクトを赤いオブジェクトに距離でマッピングする必要があります。各オブジェクトの中心は既知です。黄色と緑色のオブジェクトが表示されている場合は、ヒントです。これらは、どの赤いオブジェクトがより重要であるかを判断するのに役立ちます。

たとえば、次の図に示す状況では:

  • 緑と黄色のオブジェクトはどちらも赤のオブジェクトに非常に近いため、一番下の青のオブジェクトは一番右下の赤のオブジェクトにマップする必要があります。
  • 右の青いオブジェクトは、右上の赤いオブジェクトに近いため、マップする必要があります。


ここに画像の説明を入力

単純な解決策がありますが、「????」の代わりに何をすべきかよくわかりません。下

何か提案はありますか？

一種の疑似コードでの私の素朴な解決策:

for each BLUE:
   find group P=(YELLOW_BLUE, GREEN_BLUE and RED_BLUE) when each object in P is the closest to BLUE
   vector<RED> redCandidates
   for each O in P:
       if O is YELLOW OR O is GREEN
          find closest RED to O 
          insert RED to redCandidates

   if size of redCandidates is 0 -> return RED_BLUE
   else if size of redCandidates is 1 -> return redCandidates[0] since hint has more weight to the decision
   else if size of redCandidates is > 1 -> ????

UPDATE1 @ldogによって提案された最小コスト フローの問題
を調べ た後、ハンガリー語アルゴリズムを使用することにしました。各青いノードが各赤いノードに接続され、エッジの重みが青と赤の間の距離である二部グラフを作成しました。 ここで、グラフを解く前に、黄色/緑が赤に近いエ​​ッジに報酬を適用する必要があります。その方法がよくわかりません。 青 1 と赤 4 の間の距離が D_1_4 = 10 で、黄色のヒント 11 と赤 4 の間の距離が D_4_11 = 3 であるとしましょう。したがって、D_1_4 > D_4_11 であるため、エッジ 1_4 に報酬を追加するだけでよいでしょうか? または、ノード 4 に入る各エッジ、つまりエッジ 1_4、2_4、および 3_4 に報酬を追加する必要がありますか?ここに画像の説明を入力

4

1 に答える 1