DFSまたはGreedy BFSを使用して解決策を解決しましたか？

Question

私はこのような問題を抱えています：会社は4つの異なる場所（A B C D）に4つのタクシーを持っています。 4人（W X Y Z）は、タクシーが必要な会社に電話します。私は、タクシーが1人で行くことができ、各タクシーがその目的地と人の目的地の間に価値を割り当てていることを知って、タクシーが彼らの人々に到着できる最速の方法を見つける必要があります。

私はAW-BX-CY-DZやAX-BW-CY-DZなどの可能な組み合わせをすべてツリーに構築することを考えていましたが、それぞれの最小コストを見つけましたが、 DFSまたは貪欲なBFSのアプローチ。これがどのように機能するか考えてみましょうか？私はそれを想像することはできません。

DFS/GBFSを使用してこれを解決する方法についてのアイデアがほしいだけです。使用する最小距離を探しているので、どうすればいいか、検索が終了するか分かりません。

Answer 1

これはassignment problemのインスタンスで、加重二部グラフ。この種の問題を解決するために使用される最も一般的なアルゴリズムはHungarian Algorithmで、これをO（n^3）で解決します。それを実装するPythonモジュール - munkresがあります。

しかし、実際にDFS/BFSを使用する場合は、考えられるすべてのソリューションを作成し、DFS/BFSを使用してソリューションスペースを検索するという単純なアルゴリズムが考えられますが、非常に最適ではありません。