5

ハミルトン サイクルを実装する Java ソース コードを考え出さなければならないこのプロジェクトがあります。私はグーグルで検索しましたが、少なくともハミルトニアンサイクルとは何か、開始頂点を除くすべての頂点を一度だけ通過するパスは最後の頂点でもあるため、わかりました（間違っている場合は教えてください）。問題は、それを実装する方法がわからないことです。基本的に、私の質問は次のとおりです。

  1. ハミルトニアン サイクルをどこでどのように実装しますか?
  2. ハミルトニアン サイクルのアプリケーションは何ですか (なぜそれが重要なのかを理解するのに役立ちます)
4

4 に答える 4

3
  1. ハミルトニアン サイクルを実装するのではなく、見つけます(または、与えられたグラフに何も存在しないことがわかります)。これは NP 完全問題であるため、これはおそらく効率的な解決策ではないことを意味するため、単純なバックトラッキングアルゴリズムを実装するだけです。サイクルを探しているので、どのノードから開始するかは問題ではありません。
  2. ハミルトニアン サイクルは、暗号化でゼロ知識証明に使用できます。これがまだ単なる研究なのか、それとも暗号プロトコルで積極的に使用されているのかはわかりません。
于 2011-03-18T12:47:28.377 に答える
0

最も簡単な方法は、1つのノードから開始して「タグ付け」し、次に到達可能な「タグなし」ノードを選択して「タグ付け」し、次のいずれかになるまで続行することです。

  • 開始ノードに到達すると、ハミルトン閉路が見つかります。すべてのノードに対してサイクルを繰り返し、そのグラフ内のすべてのハミルトンサイクルを見つけます。
  • 別の「タグなし」ノードを選択することはできません。つまり、その開始ノードにはハミルトン閉路がありません（ただし、とにかくハミルトンパスが見つかりました）。

そのアルゴリズムはいくつかの方法で最適化することができますが、私はあなたにそれを任せます。あなたが見つけたどんな解決策もNP完全です。

それらの使用法については、グラフ理論とAIクラス（これは特定の旅行者の問題であり、各エッジのコストが1）でしか見られず、実際の使用法については教えてくれませんでした。

于 2011-03-18T13:07:05.977 に答える
0

これは宿題ですか？その場合は、そのようにタグ付けしてください。

再帰を使用できれば（グラフが大きくなりすぎた場合はそうではありません）、簡単に実装できます。あなたがすることは、引数としてグラフをとる関数を書くことです（これにはさまざまな表現があります）、関数はグラフが開始点のみで構成されているかどうかをチェックします。まだグラフにあり、グラフからノードNを引いたものを引数として与える各ノードN。

于 2011-03-18T12:48:05.073 に答える
0

(B) 実用化

  • 電話システムの最も効率的なスイッチング ネットワークの決定
  • 最適なバスルート、郵便ルート、メーターチェックルート
于 2012-02-27T16:23:12.517 に答える