次の問題を解決したい：
実行する必要がある都市とそれらの間のジョブを含む DAG があります。仕事は、定義された制限を積載できるトラック用です。トラックの積載量が多いほど、ツアーはより良いものになります。何かをロードするためのジョブもあれば、定義されたものをロードするためのジョブもあります。都市 a から都市 b までは、たとえ仕事がなくても、いつでも車で行くことができます。最後の制限は、トラックのホームがあるため、常に都市 a で開始して a に戻る必要があることです:)
最初に考えたのは、ダイクストラの最短経路アルゴリズムです。それを最長パスの計算に簡単に変えることができました。私の問題は、これらのアルゴリズムはすべて、頂点 a から b への最短または最長のパスを計算するためのものですが、a から a に戻る必要があることです。
私の心にいくつかのキックがありますか？
ご意見ありがとうございます！
マルコ
このナップザックと巡回セールスマンのクレイジーな組み合わせは、確かにNP 困難です。
最適なジョブ スケジュールでエージェントをロードしたいとき、グラフ内のすべての頂点を通るルートを構築したいとき、または「最長パス*」を探す必要があると感じたとき、ほとんどどこでも、 NP 完全またはNP 困難な問題に遭遇します。
つまり、問題に対する既知の高速で正確な解、つまり多項式時間で実行される解が存在しないことを意味します。
そのため、特定の条件に基づいて近似を作成し、最適ではないアルゴリズムを実装する必要があります。どのくらいのタイムロスが許容されますか? トラックが運転できる追加のパターンはありますか? グラフについて詳しく知っていますか? これらの質問に答えれば、顧客を満足させる非厳密なヒューリスティックを見つけることができます。
*はい、最長パスの検索は思ったほど簡単ではありません。グラフが非循環的でない場合、最長経路問題は NP 完全です。
すべてをやり遂げるための最小の方法を見つけようとしていますか? これは、最大フロー/最小カットの問題を思い出させます。次の方法で、最良の答えを概算できる場合があります。
endノードに接続します。aとの間の最大フローを見つけますend。aます。今行ったことを反映するようにグラフを更新します。すべての作業が完了するまで繰り返します。アイデアは、すべての旅行で最大の成果を得るということです。1回目以降の各旅行は効率が低下し、効率が低下しますが、それは予想されることです.
注:これは、DAG がある場合にのみ機能します。巡回セールスマンも DAG では NP 完全ではなく、グラフ上のすべてのノードに到達することさえ不可能になる可能性があります。問題を読み直すと、都市に戻ることができるため、DAG がないようです。それはa本当ですか?
巡回セールスマン問題の動的計画法アルゴリズムを調整して、必要なことを行うことができます。
古典的なアプローチでは、すべての都市から最適な機能を最大化したいと言われていますが、各ステップで帰国の可能性も考慮することができます。
Pavel が述べたように、この問題は明らかに NP 困難です。トラックに積み込める都市の数やオブジェクトの最大数に上限はありますか?
PS: 最善の解決策 (最大の利益 - 処理時間の点で現実的ではない可能性があります) が必要ですか、それとも近似値を受け入れますか?
これは輸送の問題ではありませんか？
トラックの数と開始点に応じて、制限を満たすために偽の輸送を追加したり、コストを追加したりできます。
トラックの制限についてもお尋ねします。