ハミルトニアン・パス問題と先史時代のウイルスパズル: 世界を救う挑戦

概要

この先史時代のウイルスパズルのシナリオでは、研究チームが大流行を引き起こす可能性のある致死性のウイルスを発見します。このウイルスは、入り口以外の4×4の施設のすべての部屋に感染しています。プレイヤーの使命は、緊急自己破壊スイッチを引いて、すべての汚染された部屋でウイルスを破壊することです。与えられたグラフに対して正確に一度だけすべての点を訪れ、特定の点で始まり終わる経路を持つハミルトニアン・パスを決定するための信頼できる式やショートカットがないため、このパズルはハミルトニアン・パス問題に新たな要素を加えています。目標は、汚染されていない唯一の部屋である入り口を利用して、すべての部屋でウイルスを成功裏に破壊し、どの部屋も残さずにクリアすることです。

はじめに

仮想のシナリオでは、先史時代のウイルスが4×4の施設のすべての部屋に感染し、プレイヤーの課題は、各汚染された部屋でウイルスを破壊することです。ただし、スイッチが作動すると部屋は破壊され、その部屋に再度入ることはできません。プレイヤーは、緊急自己破壊スイッチを使用して、すべての汚染された部屋でウイルスを破壊するために成功する経路を見つけ、どの部屋も残さずにクリアする必要があります。このシナリオでの挑戦は、ウィリアム・ローワン・ハミルトンにちなんで名付けられたグラフ理論の問題であるハミルトニアン・パス問題に関連しています。

ハミルトニアン・パス問題とは何か？

ハミルトニアン・パス問題は、与えられたグラフにハミルトニアン・パスが存在するかどうかを決定する問題であり、ハミルトニアン・パスは、それぞれの点を正確に一度訪れる経路を指します。グラフ内のすべての点を再訪することなく訪れる最も効率的な経路を見つけることを目的としています。この問題はNP完全と分類されており、提案された解決策はすぐに検証できますが、それを見つけるための信頼できる式やショートカットはありません。先史時代のウイルスパズルは、スタート地点に戻ることを目的としているため、ハミルトニアン・パス問題にさらに難易度を加えています。

先史時代のウイルスパズルでは真のハミルトニアン・パスは機能しないのはなぜか？

真のハミルトニアン・パス、すべての点を再訪することなくグラフ内のすべての点を訪れる経路は、先史時代のウイルスパズルでは機能しません。なぜなら、すべての偶数辺のグリッド、つまりチェッカーボードグリッドのようなグリッドでは、スタート地点と終了地点が対角線上にあるため、黒いマスから始まるハミルトニアン・パスは白いマスで終わり、白いマスから始まるハミルトニアン・パスは黒いマスで終わることになります。偶数のマスが各辺にある場合、対角線上の反対側の角は同じ色であるため、対角線上にあるスタート地点と終了地点のハミルトニアン・パスは不可能です。

すべての部屋でウイルスを破壊するために成功する経路を許す例外はあるか？

先史時代のウイルスパズルとハミルトニアン・パス問題がもたらす難しさにもかかわらず、このジレンマから抜け出す方法があります。パズルのルールは、汚染されていない部屋である入り口を、2つの特定の部屋のいずれかを破壊した後に一度だけ出て、戻ることができることを定めています。角の部屋がエアロックの開口部で汚染された可能性があるとしても、2回目の訪問後に入り口を破壊することがで