問題タブ [hamiltonian-cycle]

ドアを 2 回使用せずに部屋のセットを通るルートを見つける必要がある、古典的な「ケーニヒスベルクの 7 つの橋」パズルの変形であるパズルがいくつかあります。

これは、解決策のない例です。

...そして、ここでわかるように、解決策 があるわずかに変更されたパズルです。

この種の問題を解決するためのプログラムによるアプローチに興味があります。部屋とドアの特定の構成に解決策がないことを判断する方法はいくつかありますが、解決するために訪問するドアのリストを計算することに興味があります。パズル。問題を表示する 1 つの方法は、その構成をグラフに変換し、ハミルトニアンを解くことです。ただし、この種の問題は、「Uターン」が禁止されているという制約があるため、洗練されていないロジックに取り組む必要があります。

問題を示すために、数分で解決策をハックしました。これは、「部屋」をグループに入れる力ずくのソリューションであり、同じ部屋の 1 つの「ドア」から別の「ドア」に移動できないという不変条件が追加されています (U ターンを行う必要があるため)。

次の「トリック」に頼らない、この問題を表現するためのより良い抽象化が必要だと思います。

1. パスがその部屋から来たばかりのときに、有効な選択肢として同じ部屋のドアを削除するための追加のロジックがあります。

2. 入力ルームの構成と同型ではないグラフを生成します。

3. U ターンの制約を満たさないすべての構成をフィルタリングします。(#1 のバリアント)

この種の問題に取り組んでいる既存の文献はありますか? もしそうなら、その結論は何ですか? ルームの問題は、最もよく知られているグラフ アルゴリズムで採用されている方法と根本的に矛盾しているため、この特別なロジックが必要になるのでしょうか? グラフへの変換以外のより良い解決策がある場合は、それについても聞きたいです。

動作する既存のコードは次のとおりです。グループは最初の問題を表し、コメントアウトされたグループは後者の問題を表します。

ドアには次のようにラベルが付けられています。

ファイルからグラフの定義を読み取り、ハミルトニアンサイクル（1つだけ）を検索し、見つかった場合は画面に出力するCのプログラムがあります。問題は、30 個以上の頂点を持つグラフでサイクルを見つけようとすると、プログラムがクラッシュすることです (30 個の頂点の場合、サイクルの終わりが (異なる飽和度で) クラッシュし、より多くの頂点が即座にクラッシュすることがあります)。デバッグしようとすると、free() 関数で停止し、SIGTRAP シグナルが表示されます。それを修正するにはどうすればよいですか？これが私のコードです：

「グラフ理論入門」のコースで試験の準備をしているときに、この質問に出くわしました。誰かがそのような質問にアプローチするための方法論を提供してくれれば幸いです（頂点の数とハミルトニアンまたはユークリッドパスを指定し、グラフの構造を尋ねる場合）。