NPとして最適に分類された3x3x3 rubiks立方体を解いていますか？

私は3x3x3ルービックキューブと計算理論の関係について何か書いています。私は神の数と最適解について話しているテキストを読んだことがあるが、rub37キューブを最適に解くことがPかNPなら、それはPなら多項式時間で解くアルゴリズムがあるのだろうか？NPとして最適に分類された3x3x3 rubiks立方体を解いていますか？

出典

2016-10-18 Felipe Chabatura

3×1×5のルービックの立方体とは何でしょうか？ – greybeard

3x3x3ルービックの立方体を解くことはO（1）です。ルービックのキューブはほぼ確実にNP困難ですが、厳密な証明があるかどうかはわかりません。たぶんここから探し始めます：https://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-n×n×n-rubiks-cube-np-hard

出典

2016-10-18 13:37:05

最適なソリューションについて話していても、可能な限り、最短の移動数である。 –

3x3x3のキューブではまだO（1）です。各構成に対して最適な移動のルックアップテーブルを作成することができます（3x3x3キューブの構成数は、非常に大きな数値であってもO（1）です）。ここでも、任意の構成でNxNxNキューブの最適な動きを見つけることは、おそらく非常に困難です。 –

キューブのすべての構成を最適に解決できるアルゴリズムがあることを意味しますか？またはこれらの2つの事の間に何の実現もありませんか？ –

NPとして最適に分類された3x3x3 rubiks立方体を解いていますか？

答えて

関連する問題