問題タブ [hamiltonian-cycle]

正しい方向へのアドバイス/ガイダンスを探しています。

私の要件は、ソリューションを解決するのではなく、グラフを生成することです。

ハミルトニアン サイクルが 1 つだけのグラフ (NxN グリッド) を生成するアルゴリズムを実装しようとしています。1 つの固有のソリューションだけが重要であることに注意してください。グラフはノードの NxN グリッドになり、各ノードは上、右、下、左の 4 つの隣接ノードのみを持ちます。ノードにアクセスできるのは 1 回だけです。これとは別に、いくつかの特別なノードが存在する場合があります。

1. デッドノード、つまりエッジ接続がない
2. 入口ノードと出口ノードが固定されています。つまり、入口ノードと出口ノードはすでに定義されており、他のノードは指定されたノードに接続できません。それはすることができます。隣接ノード ｂ．ストレートノード

いくつかの例：

私のアプローチ:

*n グリッドを使用して、グラフ上にランダムなデッド ノードを配置することから始めます。この後、ランダムな特殊ノードを配置します。次に、グリッド全体を横断する dfs 検索を実行して、特別なノード基準を満たし、すべてのノード (開始ノードを除く) を 1 回だけ訪問し、開始ノードで終了する有効なサイクルが存在することを確認します。これにより、完全なループになります。

私の質問:

ここで私が求めているのは、グラフに有効なサイクルが 1 つしかないことを確認するにはどうすればよいかということです。有効なハミルトニアン サイクルの数が 1 に減少するまで、サイクルごとにデッド ノードと特別なノードを追加することで、レベルを再帰的に反復することができます。これは私が実装しようと計画しているものです。

この問題にどのようにアプローチするのが理想的ですか?

私は独自の調査を行いましたが、私の要求に対する適切な解決策を見つけることができませんでした.

問題は、私はその負荷を費やす必要があるトラックを持っていることです（ゴミとしましょう）。正のエッジまたは負のエッジになることができる都市（ノード）とエッジ（ウェイ）があります。トラックは道を進んでいますが、選択した道 (エッジ) によっては、緩んだり、より多くの (無駄) を取得する必要がある場合があります。正のエッジを選択した場合は、選択したウェイ値とまったく同じ量の無駄を失います。およびその逆。

したがって、トラックの運転手は一定量のステップを踏む必要があり（エッジの値に関係なく、すべてのステップに一定の時間がかかります）、ドライバーは自宅（起点ノード）に戻る時間が限られています（時間は指定されたパラメーターになります）

したがって、このグラフにはノードがあり、一方向のエッジがあり、このエッジは負または正の値を持つことができ、グラフにはドライバーが使用できるループと使用できないループがあります。また、ノードは異なるエッジでお互いを指すことができます。(A から B へのエッジの値は 5 です) (B から A へのエッジの値は -3 などです..)

そのため、可能な限り最短の時間で最大負荷を使用するための最良の方法をドライバーに提供したいと考えています。

では、問題はこれです。

私が欲しいのは、実際のコードに注意してください。

指定できる問題の名前がわかっている場合は、どういたしまして。独自のアルゴリズムを疑似コードまたは単なる言葉で共有したい場合。こちらもどうぞ。同様の問題が尋ねられると思われるリンクを共有したい場合。こちらもどうぞ。

そして、それが解決できないと思うなら。あなたの考えやそれを証明するリンクを共有してください。

前もって感謝します。

巡回セールスマンの問題を航空運賃で解決しようとしているので、主なアイデアは、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 次元グラフとして表示することもできます。では、主な問題は、これらの日付をどのように処理するかです。

私が要点に到達したことを願っています。

事前に感謝します。