Snake-in-the-box とは

グラフ理論とコンピュータ科学における蛇の問題は、ハイパーキューブの端に沿って特定の種類の経路を見つけることを扱っています。このパスは1つのコーナーから始まり、到達可能な限り多くのコーナーにエッジに沿って移動します。それが新しいコーナーに到着した後、前のコーナーとそのすべての隣人は使用不能としてマークされなければならない。パスは、使用できないとマークされた後、角に移動してはなりません。
言い換えれば、スネークはハイパーキューブ内の接続されたオープンパスであり、ヘッド(開始)とテール(フィニッシュ)を除いて、パス内の各ノードはスネークにも正確に2つのネイバーを持っています。頭と尾はそれぞれヘビ​​の隣に1人しかいません。スネークを生成するルールは、ハイパーキューブ内のノードが現在のノードに接続されていて、現在のノード以外のスネーク内の以前に訪問したノードのネイバーでない場合にアクセスできることです。
グラフ理論の用語では、これは超立方体内で可能な最長誘導経路を見つけることと呼ばれ、誘導された部分グラフ同型写像問題の特殊なケースと見ることができる。コイル内の問題と呼ばれる、超立方体の長い誘導サイクルを見出すのと同様の問題があります。
蛇の問題はKautz(1958)によって最初に記述され、誤り訂正符号の理論によって動機づけられました。ボックスの問題にあるヘビやコイルの解の頂点は、シングルビットエラーを検出できるグレーコードとして使用できます。このようなコードは、電気工学、コーディング理論、およびコンピュータネットワークトポロジーに応用されています。これらのアプリケーションでは、ハイパーキューブの特定のディメンションで可能な限り長いコードを考案することが重要です。コードが長ければ長いほど、その機能はより効果的です。
ディメンジョン数が増え、検索スペースが重大な組み合わせの爆発に苦しんでいるので、最も長いヘビやコイルを見つけることは難しくなります。スネーク・イン・ザ・ボックス問題の上限と下限を決定するいくつかの技法には、離散数学とグラフ理論を用いた証明、探索空間の徹底的な探索、進化的手法を用いたヒューリスティック探索が含まれる。