巡回セールスマンの問題を航空運賃で解決しようとしているので、主なアイデアは、1 つの空港から開始し、すべての空港を 1 回だけ訪問して元に戻ることです。
例: LAX から開始して、LV、CA、NY にアクセスし、LAX を終了します。
これは、空港をノードとして、ルートをエッジとして、価格をエッジの重みとして表すことができる古典的なグラフの問題です。
これは最も簡単な部分ですが、私を本当に混乱させるのは、ユーザーが旅行を希望する日付です。たとえば、ユーザーが旅行したい日付を選択できるオプションを提供したいと考えています。たとえば、01 から始まり 15 で終了します。たとえば、出力は次のようになります。
01 - LAX - LV;
04 - LV - CA;
08 - CA - NY;
15 - NY - LAX
したがって、エッジに追加の属性を配置できることは理解していますが、問題は、アルゴリズムがグラフをトラバースする方法をどのように区別するかです。たとえば、すでに過去にある最小の重みを持つエッジを選択しないなどです。
したがって、CA から 2 つのエッジが出ていることがわかります (エッジの形式は DD であることに注意してください - 価格、01 - 20 は日付の最初を意味し、コストは 20 です)。ノードが存在します。
また、3 次元がユーザーの旅行日である 3 次元グラフとして表示することもできます。では、主な問題は、これらの日付をどのように処理するかです。
私が要点に到達したことを願っています。
事前に感謝します。