定理: 一般化されたスーパーマリオブラザーズにおいて、ステージのスタートからゴールまで辿り着くことが可能かどうか判定するのはNP完全問題である。 つまりステージをランダム生成したスーパーマリオブラザーズがゴールできるか判定するには計算量がすごく大きくなる(もしくは解けない)ことを示しただけ こういう話題を親しみやすい例で示してくれるのはありがたいが、適当なことを書くのはやめていただきたい
フォロー
コタク・ジャパンチャンネル
(ID:15805468)
定理: 一般化されたスーパーマリオブラザーズにおいて、ステージのスタートからゴールまで辿り着くことが可能かどうか判定するのはNP完全問題である。
つまりステージをランダム生成したスーパーマリオブラザーズがゴールできるか判定するには計算量がすごく大きくなる(もしくは解けない)ことを示しただけ
こういう話題を親しみやすい例で示してくれるのはありがたいが、適当なことを書くのはやめていただきたい