問題タブ [hungarian-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
algorithm - 最も近いオブジェクトを見つけるアルゴリズム
青いオブジェクトを赤いオブジェクトに距離でマッピングする必要があります。各オブジェクトの中心は既知です。黄色と緑色のオブジェクトが表示されている場合は、ヒントです。これらは、どの赤いオブジェクトがより重要であるかを判断するのに役立ちます。
たとえば、次の図に示す状況では:
- 緑と黄色のオブジェクトはどちらも赤のオブジェクトに非常に近いため、一番下の青のオブジェクトは一番右下の赤のオブジェクトにマップする必要があります。
- 右の青いオブジェクトは、右上の赤いオブジェクトに近いため、マップする必要があります。
単純な解決策がありますが、「????」の代わりに何をすべきかよくわかりません。下
何か提案はありますか？
一種の疑似コードでの私の素朴な解決策:
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 に報酬を追加する必要がありますか?