Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
無向加重グラフ (たとえば 's' から 't' へ) でパスを見つけ、すべてのエッジの合計加重が固定数 (たとえば 'm') になるアルゴリズムを探しています。 .. 誰でも?
DFS やバックトラッキングなどを使用します。体重 m を超えて目標に達していない場合は、バックトラックします。2 つのノード間を行き来できるかどうかはわかりませんが、そうすると、その場でツリーを構築することはできず、スタックを構築する必要があります。
最初に最短経路を検索してからそれを長くする方がより速いアプローチになるだろうという直感がありますが、同じ感覚は、巡回セールスマンにとって貪欲なアルゴリズムが間違っているように、それは間違っている可能性があることを教えてくれます.