Hamiltonian Path Problem: 先史時代のウイルスから世界を救う

要約

この記事では、グラフ内のすべての点を正確に1回訪問する経路を見つける問題であるHamiltonian path problemに関連するパズルについて探求します。課題は、入り口以外の研究所全体の各部屋に放出された先史時代のウイルスを、汚染された各部屋の緊急自己破壊スイッチを引くことで破壊することです。ただし、スイッチが作動すると、その部屋に戻ることは不可能です。与えられたエンドポイントでは真のHamiltonian pathは不可能である理由を説明し、成功する経路を可能にする例外も明らかにします。

課題：先史時代のウイルスの破壊

研究チームは、永久凍土に保存された先史時代のウイルスを発見し、研究のために隔離しました。しかし、ウイルスは入り口以外の研究所全体の各部屋に放出され、破壊されない場合、致死性の空気感染症がまもなく発生します。今回の課題は、汚染された各部屋に入り、緊急自己破壊スイッチを引いてウイルスを破壊することです。研究所は、16室の4×4グリッドで構成され、北西隅に入り口、南東隅に出口があります。各部屋はエアロックによって隣接する部屋に接続されています。

Hamiltonian path problem

今回のパズルは、グラフ内のすべての点を正確に1回訪問する経路を見つける問題であるHamiltonian path problemに関連しています。Hamiltonian path problemは、グラフが大きい場合に特に困難であり、提案された解決策は容易に検証できますが、1つを見つけるか、存在するかどうかを決定するための信頼できる公式やショートカットはありません。このタイプの問題はNP完全と分類されます。

与えられたエンドポイントにおける真のHamiltonian pathの不可能性

研究所内では、与えられたエンドポイントでは真のHamiltonian pathは不可能です。部屋は各辺に偶数の部屋を持つグリッドを形成し、その構成を持つ任意のグリッドでは、対角線上の相反する隅は同じ色になります。したがって、グリッドを通るすべての経路は黒と白が交互に現れ、各辺に偶数の正方形を持つグリッドでは、対角線上の相反する隅は同じ色になります。したがって、黒で始まるHamiltonian pathは白で終わらなければならず、その逆も同様です。

例外

ただし、このルールには例外があり、成功する経路を可能にします。汚染された部屋でスイッチが作動すると、破壊され、再訪問することはできませんが、1つの部屋は汚染されていません-入り口です。これは、2つの部屋のいずれかを破壊した後に出口に戻ることができることを意味します。角部屋はエアロックの開口部から汚染されている可能性がありますが、2回目の訪問後に入り口を破壊することができるため、問題ありません。この帰路により、成功する経路の4つのオプションが得られ、入り口を最初に破壊した場合にも同様のオプションが得られます。