ハミルトニアンパス問題：致死性ウイルスから世界を救う

概要

この記事では、与えられたグラフの各点を正確に1回訪れるルートを見つける問題であるハミルトニアンパス問題に関連するパズルを探求します。このパズルは、研究のために分離された先史時代のウイルスが、現在16の部屋からなる4×4の複合体に収容されていることに関係しています。ウイルスを破壊するには、汚染された各部屋に入り、緊急自己破壊スイッチを引く必要があります。ただし、一度汚染された部屋に入ると、スイッチを作動させずに出ることはできず、スイッチを作動させた後に再び部屋に入ることはできません。このパズルがハミルトニアンパス問題にどのように関連しているか、そしてどのように解決するかを探求します。

ハミルトニアンパス問題

ハミルトニアンパス問題は、与えられたグラフの各点を正確に1回訪れるルートを見つける問題であり、19世紀のアイルランドの数学者ウィリアム・ローワン・ハミルトンにちなんで名付けられました。この問題の課題は、与えられたグラフにハミルトニアンパスがあるかどうかを決定することです。このタイプの問題は、グラフが十分に大きい場合には、NP完全と分類されており、悪名高く困難です。

先史時代のウイルスのパズル

この記事で探求しているパズルは、研究のために分離された先史時代のウイルスが、現在16の部屋からなる4×4の複合体に収容されていることに関係しています。現時点ではウイルスは収容されていますが、破壊しなければすぐに換気口が開き、致死性の空気感染症が発生します。ウイルスを破壊するには、汚染された各部屋に入り、緊急自己破壊スイッチを引く必要があります。ただし、一度汚染された部屋に入ると、スイッチを作動させずに出ることはできず、スイッチを作動させた後に再び部屋に入ることはできません。

パズルの解決方法

一見すると、すべての汚染された部屋を破壊して生き残ることは不可能に見えるかもしれません。しかし、このパズルを解決する方法があります。鍵となるのは、端点が与えられた場合、真のハミルトニアンパスは不可能であることです。部屋は各辺に偶数の部屋があるグリッドを形成しているため、対角線上に始まり終わるハミルトニアンパスは不可能です。

ただし、汚染されていない1つの部屋があります-入口です。これは、スイッチを引かずに一度出ることができ、2つの部屋のいずれかを破壊した後にそこに戻ることができることを意味します。角部屋はエアロックの開口部から汚染されている可能性がありますが、2回目の訪問後に入口を破壊することができます。この帰り道は、成功するルートの4つのオプションを与え、この部屋を最初に破壊した場合には同様のオプションがあります。