箱の中のヘビ

グラフ理論とコンピュータサイエンスにおける「箱の中の蛇」問題は、ハイパーキューブの辺に沿った特定のパスを探す問題を扱います。このパスは 1 つの角から始まり、到達できる限り多くの角まで辺に沿って進みます。新しい角に到達した後、前の角とそのすべての隣接角は使用不可としてマークされている必要があります。パスは、使用不可としてマークされている角に到達してはなりません。

言い換えると、スネークとはハイパーキューブ内の接続されたオープン パスであり、パスに接続された各ノードは、ヘッド (開始) とテール (終了) を除いて、スネーク内にある 2 つの隣接ノードを持ちます。ヘッドとテールは、スネーク内でそれぞれ 1 つの隣接ノードのみを持ちます。スネークを生成するためのルールは、ハイパーキューブ内のノードが現在のノードに接続され、現在のノード以外のスネーク内で以前に訪問したノードの隣接ノードでない場合、そのノードを訪問できるというものです。

グラフ理論の用語では、これはハイパーキューブ内で可能な限り最長の誘導パスを見つけることと呼ばれ、誘導サブグラフ同型性の問題の特殊なケースとして考えることができます。ハイパーキューブ内の長い誘導サイクルを見つける同様の問題があり、coil-in-the-box問題と呼ばれます。

スネーク・イン・ザ・ボックス問題は、誤り訂正符号の理論に触発されて、カウツ (1958) によって初めて説明されました。スネークまたはコイル・イン・ザ・ボックス問題の解の頂点は、単一ビットの誤りを検出できるグレイ・コードとして使用できます。このようなコードは、電気工学、符号理論、およびコンピュータ・ネットワーク・トポロジーに応用されています。これらのアプリケーションでは、ハイパーキューブの特定の次元に対して可能な限り長いコードを考案することが重要です。コードが長いほど、その機能はより効果的になります。

次元数が増えると、最も長いスネークまたはコイルを見つけることは困難になり、検索空間は深刻な組み合わせ爆発に見舞われます。スネーク・イン・ザ・ボックス問題の上限と下限を決定するための手法には、離散数学とグラフ理論を使用した証明、検索空間の徹底的な検索、進化的手法を利用したヒューリスティック検索などがあります。

スネーク・イン・ザ・ボックス問題の最大長は1次元から8次元まで知られている。

1、2、4、7、13、26、50、98（OEISの配列A099155）。

その長さを超えると、最長のヘビの正確な長さは不明です。9次元から13次元まででこれまでに発見された最長の長さは、

190、370、712、1373、2687。

サイクル（箱の中のコイル問題）の場合、2次元未満の超立方体にはサイクルは存在できない。可能な最長サイクルの最大長は次の通りである。

0、4、6、8、14、26、48、96（OEISの配列A000937）。

その長さを超えると、最長周期の正確な長さは不明です。9次元から13次元まででこれまでに発見された最良の長さは、

188、366、692、1344、2594。

二重コイルは特殊なケースで、後半部分が前半部分の構造を繰り返すサイクルで、対称コイルとも呼ばれます。2次元から7次元まで、最長の二重コイルの長さは次のようになります。

4、6、8、14、26、46。

それ以外では、8次元から13次元まででこれまでに発見された最良の長さは

94、186、362、662、1222、2354。

蛇の問題と箱の中のコイルの問題の両方において、最大長はn次元の箱の場合2 ⁿに比例し、 nが大きくなるにつれて漸近し、 2 ^{n − 1}で上限が定められることが知られています。しかし、比例定数は不明ですが、現在知られている最良の値は 0.3 - 0.4 の範囲であることが観測されています。^[1]

• アボット、HL; カチャルスキー、M. (1988)、「箱の中のヘビ問題について」、組合せ理論ジャーナル、シリーズ B、45 : 13–24、doi : 10.1016/0095-8956(88)90051-2
• Abbot, HL; Katchalski, M. (1991)、「スネーク・イン・ザ・ボックス・コードの構築について」、Utilitas Mathematica  [fr]、40 : 97–116
• アリソン、デイビッド、パウルスマ、ダニエル (2016)、「箱の中の蛇問題に対する新しい境界」、arXiv : 1603.05119、Bibcode :2016arXiv160305119A
• Bitterman, DS (2004)、「Snake-In-The-Box 問題に対する新しい下限値: Prolog 遺伝的アルゴリズムとヒューリスティック検索アプローチ」(PDF) (修士論文)、ジョージア大学コンピュータサイエンス学部
• Blaum, Mario; Etzion, Tuvi (2002)、ディスクドライブのサーボフィールド内のトラックを確実に識別するためのスネークインザボックスコードの使用、米国特許 6,496,312
• Casella, DA; Potter, WD (2005)、「進化的手法を用いたヘビとコイルの探索」、2005 IEEE 進化的計算会議 (CEC2005)、第 3 巻、pp. 2499–2504
• Casella, DA (2005)、「Snake-in-the-Box 問題と Coil-in-the-Box 問題の新たな下限値」(PDF) (修士論文)、ジョージア大学コンピュータサイエンス学部
• Danzer, L.; Klee, V. (1967)、「箱の中のヘビの長さ」、Journal of Combinatorial Theory、2 (3): 258–265、doi : 10.1016/S0021-9800(67)80026-7
• Davies, DW (1965)、「 Nキューブ内の最長の「分離された」パスとループ」、IEEE Transactions on Electronic Computers、EC-14 (2): 261、doi :10.1109/PGEC.1965.264259
• デイマー、クヌート（1985）、「ヘビの長さの新しい上限」、コンビナトリカ、5（2）：109–120、doi：10.1007 / BF02579373、S2CID  30303683
• Diaz-Gomez, PA; Hougen, DF (2006)、「箱の中のヘビ問題: 数学的推測と遺伝的アルゴリズムによるアプローチ」、第 8 回遺伝的および進化的計算に関する会議の議事録、米国ワシントン州シアトル、pp. 1409–1410、doi :10.1145/1143997.1144219、S2CID  19239490{{citation}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク)
• ダグラス、ロバート J. (1969)、「 dキューブにおける均等拡散回路の長さの上限」、組み合わせ理論ジャーナル、7 (3): 206–214、doi : 10.1016/S0021-9800(69)80013-X
• Evdokimov、AA (1969)、「単位n次元立方体におけるチェーンの最大長」、Matematicheskie Zametki、6 : 309–319
• Kautz, William H. (1958 年 6 月)、「単位距離エラーチェックコード」、IRE Transactions on Electronic Computers、EC-7 (2): 179–180、doi :10.1109/TEC.1958.5222529、S2CID  26649532
• Kim, S.; Neuhoff, DL (2000)、「堅牢な量子化器インデックス割り当てとしての Snake-in-the-box コード」、IEEE 国際情報理論シンポジウムの議事録、p. 402、doi :10.1109/ISIT.2000.866700、ISBN 0-7803-5857-0、S2CID  122798425
• Kinny, D. (2012)、「Snake-In-The-Box 問題への新しいアプローチ」、第 20 回ヨーロッパ人工知能会議の議事録、ECAI-2012、pp. 462–467
• Kinny, D. (2012)、「スネークとコイルのモンテカルロ探索」、人工知能の多分野にわたる動向に関する第 6 回国際 WS の議事録、MIWAI-2012、pp. 271–283
• Klee, V. (1970)、「 d次元の蛇の最大長さはいくらか?」、アメリカ数学月刊誌、77 (1): 63–65、doi :10.2307/2316860、JSTOR  2316860
• Kochut, KJ (1996)、「次元 7 の Snake-in-the-box コード」、Journal of Combinatorial Mathematics and Combinatorial Computing、20 : 175–185
• Lukito, A.; van Zanten, AJ (2001)、「スネーク・イン・ザ・ボックス・コードの新しい非漸近的上限」、Journal of Combinatorial Mathematics and Combinatorial Computing、39 : 147–156
• パターソン、ケネス G.; トゥリアニ、ジョナサン (1998)、「いくつかの新しい回路コード」、IEEE Transactions on Information Theory、44 (3): 1305–1309、doi :10.1109/18.669420
• Potter, WD; Robinson, RW; Miller, JA; Kochut, KJ; Redys, DZ (1994)、「遺伝的アルゴリズムを使用したボックス内のスネークコードの検索」、人工知能とエキスパートシステムの産業およびエンジニアリングアプリケーションに関する第 7 回国際会議の議事録、テキサス州オースティン、米国、pp. 421–426{{citation}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク)
• Snevily, HS (1994)、「箱の中の蛇問題: 新しい上限」、離散数学、133 (1–3): 307–314、doi : 10.1016/0012-365X(94)90039-6
• Solov'eva, FI (1987)、「 n次元単位立方体のサイクルの長さの上限」、Metody Diskretnogo Analiza (ロシア語)、45 : 71–76, 96–97
• Tuohy, DR; Potter, WD; Casella, DA (2007)、「進化型プルーニング モデルによる Snake-in-the-Box コードの検索」、2007 年遺伝的および進化的手法に関する国際会議 (GEM'2007) の議事録、米国ネバダ州ラスベガス、pp. 3–9{{citation}}: CS1 メンテナンス: 場所が見つかりません 発行者 (リンク)
• Wojciechowski, J. (1989)、「スネーク・イン・ザ・ボックス・コードの新しい下限値」、Combinatorica、9 (1): 91–99、doi :10.1007/BF02122688、S2CID  9450370
• 楊元盛、孫芳、韓宋（2000）「箱の中の蛇問題に対する後方探索アルゴリズム」、大連理工大学誌、40（5）：509-511
• ゼモール、ジル（1997）、「箱の中の蛇のサイズの上限」、コンビナトリカ、17（2）：287–298、doi：10.1007/BF01200911、S2CID  1287549
• Zinovik, I.; Kroening, D.; Chebiryak, Y. (2008)、「SAT ソルバーによる網羅的探索によるバイナリ組み合わせグレーコードの計算」、IEEE Transactions on Information Theory、54 (4): 1819–1823、doi :10.1109/TIT.2008.917695、hdl : 20.500.11850/11304、S2CID  2854180

• キニー、デイビッド（2012）、Snake-in-the-Box 研究ページ（京都大学）
• ワイスシュタイン、エリック W.、「スネーク」、MathWorld