1

無向加重グラフ (たとえば 's' から 't' へ) でパスを見つけ、すべてのエッジの合計加重が固定数 (たとえば 'm') になるアルゴリズムを探しています。 .. 誰でも?

4

1 に答える 1

0

DFS やバックトラッキングなどを使用します。体重 m を超えて目標に達していない場合は、バックトラックします。2 つのノード間を行き来できるかどうかはわかりませんが、そうすると、その場でツリーを構築することはできず、スタックを構築する必要があります。

最初に最短経路を検索してからそれを長くする方がより速いアプローチになるだろうという直感がありますが、同じ感覚は、巡回セールスマンにとって貪欲なアルゴリズムが間違っているように、それは間違っている可能性があることを教えてくれます.

于 2013-01-24T21:07:16.763 に答える