0

ゲーム Final Fantasy XIII-3 では、プレイヤーにいくつかのパズルが提示されます。導入された最初のパズルはTile Trialと呼ばれ、プレイヤーにタイルのグリッドを提示し、その中にはクリスタルが付いているものもあります。目標は、すべてのクリスタルを回収して出口に到達することですが、各タイルを 1 回しか踏まないでください。

http://arxiv.org/pdf/1203.1633v1.pdfの著者は、特定のケースがハミルトンサイクルに還元できるため、この問題は NP 困難であると述べています。彼は特定のパズルを開発したため、これは単純な仮定であることがわかりました。これは、ゲームのルールには合っていますが、たまたまハミルトニアン サイクルを含んでいるだけです。

一般的なケースを見ると、パズルの各タイルをグラフの頂点としてモデル化できます。2 つのタイルが隣接している場合、頂点には別の頂点へのエッジがあります。問題は、結晶を持つすべての頂点を横断し、どの頂点にも 2 回以上アクセスしないようにしながら、開始タイルから終了タイルまでのパスを見つけることです。

これは、都市のサブセットのみを訪問する必要がある TSP (巡回セールスマン問題) に還元できると思います。n都市の通常の TSP 問題を想定します。ただし、この特定の問題では、 n 個の都市すべてを訪れる必要はなく、m<=nである特定のサブセット m のみを訪問する必要があります。mではなくnにある都市を訪れる必要はありませんが、たとえばパスm1->m2がm1->n1->m2よりも大きい場合は、訪問する必要があります。

しかし、この「単純な」TSP 問題はまだ NP 困難ですか? リダクションとして使用できる、より優れた NP 困難な問題を知っている人はいますか?

4

1 に答える 1

2

この問題を TSP に還元しても、何も興味深いことにはなりません。では、お見せします。

問題 を考えてみましょうSUMS-TO-TWELVE。これは、特定の数のセットを合計すると 12 になるかどうかを判断する問題です。これを次のように TSP に縮小することにしました: ノードのチェーンで構成されたグラフを作成します。入力セットの数と同じ数のエッジがあり、各エッジのコストは入力セットの対応する数に等しくなります。最後に、最初のノードから最後のノードまで、コストがゼロのエッジを追加します。TSP の解のコストが 12 の場合、シーケンスは合格SUMS-TO-TWELVEです。

これは、数を足して 12 になるかどうかを確認する非常にばかげた方法です。SUMS-TO-TWELVEそれが難しいことは証明していませんが、簡単であること、または少なくともNP問題と同じくらい簡単であることを証明しました-つまり、「NPで」あることを証明しました。しかし、問題が NP にあることを証明するためにリダクションを使用する傾向はありません。なぜなら、非決定論的なチューリング マシンで問題を解決するアルゴリズムを与える方が簡単だからです。

そのため、いくつかのエキゾチックな問題を取り上げ、3SAT や TSP などを減らした論文をよく目にします。エキゾチックな問題を別のものに還元する論文はめったに見ません。それは有用なことではありません。

于 2015-11-10T17:42:59.493 に答える