問題タブ [hungarian-algorithm]

このプロジェクトを NetBeans にインポートしたハンガリー システムのアプリケーションをチェックアウトしたかったのですが、次のようなエラーが発生しました。

同じサイトでファイルを検索してみましたが、見つけることができませんでした。

助けてください。

人々のリストと、この組み合わせがどれほど優れているかの評価を得ました。評価を最大化する必要があります。私はすでにハンガリーのアルゴリズムを見てきましたが、少し異なる問題を解決します。どうすればそのような問題を解決できますか?

私は Android 用の複数の顔トラッカーを構築しています。カルマン フィルターを使用しています。これには、追跡対象のオブジェクトを区別するために明らかにアルゴリズムが必要であり、現在、ハンガリーのアルゴリズムに興味があります。

アルゴリズムがどのように機能するかはわかりませんが、座標のある 2D 空間がある場合、入力行列を作成する方法がわかりません。フレーム内に 3 人の人物が検出されたとします。

次のフレームでは、新しい座標でまだ 3 人の人物が検出されていますが、前の画像でどれが Person1 で、どれが Person2 であったかなどを知りたいと思います。

今、マトリックスを構築する方法がよくわかりません。列は、次のように異なる人でなければなりません。

そして、値は現在の位置と最後に見つかった位置との間の距離ですか? ばかげているように見えるかもしれませんが、混乱しています。

助けてくれてありがとう。

Hungarian Algorithm の実装を見つけましたが、「スター付きゼロ」と「プライミング ゼロ」の意味について質問があります。これは、マークされたゼロを指すために使用されていると思いますが、よくわかりません。それが正しいか？

これはコードです: http://ccp.uchicago.edu/khetarpal/code/edit-distance/HungarianAlgorithm.java

ありがとう。

ハンガリーのアルゴリズムを実装しようとしていますが、ステップ 5で行き詰っています。基本的に、数値のn X n行列が与えられた場合、行列のゼロがカバーされるように、垂直線と水平線の最小数を見つけるにはどうすればよいですか?

誰かがこの質問をこれと重複しているとマークする前に、そこに記載されている解決策は正しくなく、他の誰かがそこに投稿されたコードのバグに遭遇しました。

私はコードを探しているのではなく、これらの線を描くことができるコンセプトを探しています...

編集: 単純な (しかし間違った) 貪欲なアルゴリズムを投稿しないでください: この入力が与えられた場合:

明らかに列 2 を選択します (0-indexed):

これで、2 つの「残りの」ゼロを持つ行 2 または列 1 を選択できます。col2 を選択すると、次のパスで間違ったソリューションになります。

正しい解決策は、4 行を使用することです。

たとえば、2 つの配列:

次のようなマップとして2つの配列を構築できる関数はありますか?

およびその他の3つ... 2つの配列が与えられた場合、返されるマップ番号はA33 = 6になるはずです.javascriptまたはpythonを使用すると、誰でもそれを実行できます。何か案は？

---

ウェブで検索したところ、これは割り当て問題であり、それを解決する方法はハンガリー法と呼ばれています。現在、javascript または python によるハンガリー語アルゴリズムの実装を探しています。

有向グラフに Christofides アルゴリズムを実装することは可能ですか?

無向グラフがあるとします。このグラフでは、すべての頂点が、グラフ内の他のすべての (それ自体ではなく) 両方向にエッジを持っています。ただし、エッジの重みは、必ずしも両方の方法で同じである必要はありません (非対称)。

たとえば、一方通行の道路がたくさんあるストリート マップを考えてみます。

ここで、すべての頂点を通る巡回セールスマン ツアーの近似値を見つけたいと考えています。

まず第一に、Christoffides アルゴリズムはそのような TSP に対して定義されていません。これは、最小スパニング ツリーが有向グラフに対して定義されていないためです。

それでも、エドモンズ アルゴリズムをルートとして、ツアーの開始点への最適な分岐を見つけることからアルゴリズムを開始します。

次に、分岐の最小完全一致を見つけて、それがオイラー グラフになるようにします。これはハンガリアン アルゴリズムで発生します。このアルゴリズムでは、最小の一致が検出されるため、分岐のすべての頂点のあとがきに同じ量のエッジが出てきます。

最後のステップでは、オイラー ツアーを見つけ、ショートカットを使用してツアーを最適化します。

質問があります：

1. アルゴリズムを正しく実装したい方法ですか、それとも間違っていて機能しませんか
2. それが機能する場合、tsp の最適解の 1.5 倍に制限されますか?