経路制限に関するグラフ検索の問題

Question

私は最も収益性の高いルートを計算したいと思います。これは、セールスマンの問題であると思います。
私は訪問できるノードのセットと、ノードに到達するためにノードとポイント間を移動するためのコストを計算する関数を持っています。目標は、コストを最小限に抑えながら固定された既知のスコアに到達することです。

このコストと報酬は固定ではなく、以前に訪問したノードによって異なります。
開始ノードは固定です。

ノードのアクセス方法にはいくつかの制限があります。一部の簡略化した例としては、ノードCは、訪問DまたはEを訪問することができるされた後

• ノードBは、
• 後に訪問することができます。少なくとも1つの訪問は必須で、両方を訪問することは許可されています。
• Zのみ、ノードはもはや報酬ポイントが
• 特定のノードは、（おそらく必要があります）が複数回訪問することができるであろうAM少なくとも5つの他のノードが
• 50いったんノードが訪問されている訪問された後に訪問することができ

現在、私はこれを解決する唯一の二つの方法を考えることができます。
a）の遺伝的アルゴリズム、フィットネス機能があるため、生成されたルート
b）のグラフを通るダイクストラ検索のコスト/利益を計算すると開始ノードは固定されていますが、larノードの数がおそらく実現可能なメモリではない。

グラフを通じて最適なルートを決定する他の方法はありますか？それは完璧である必要はありませんが、エラーが許容される限り、近似されたパスは完璧です。
TSPソルバーはオプションですか？

Answer 1

この非常に奇妙なバリエーションとパス依存性を使って、実際に検索しているのはグラフそのものではなく、ルートであるツリーからなるパスのスペースです。あなたが言うように問題が一般的であれば、 "ツリーのパス"を直接検索するよりも、最良の価値と対応するパスを保存するよりも、優れたことはできません。そのようなパス依存性がないように変換できれば、おそらくそうするべきです。

もしあなたができなければ、記憶されなければならない多くの一時的な経路があるので、長さの順に経路を返す幅優先ですが、メモリ使用量が高いという犠牲を払っています。深さ優先検索では、単一のパス（一連の再帰呼び出しとして完全に行うことができます）を保存するだけで済みますが、自然な停止ポイントはなく、パスサイズの上限がないと実際に終了することは保証されません。

幸運にも、ステップが増えるたびにコストが単調に増加する場合は、代わりにコストで注文できます。最初のものはあなたが望むものです。幅広い探索は、パスを探索してキューに入れることで時々実行されます。これをコストに基づいて優先度キューに変更すると、今や正式にはUniform-cost searchと呼ばれる「コスト先行検索」が行われます。

がパスに追加してを減らすことができる場合は、検索を行うためにA *検索を変更することはできますが、早期に停止できるという保証はありません。