0
Rubiks 큐브와 계산 이론의 관계에 대해 뭔가 쓰고 있습니다. 나는 신의 수와 최적의 해에 관해 이야기하는 일부 텍스트를 읽었지만, rub37 큐브를 최적으로 풀면 P 또는 NP인지 알 수 없다. 만약 그것이 P이라면 다항식 시간에 그것을 풀 수있는 알고리즘이 있는가?NP로 최적으로 분류 된 3x3x3 rubiks 큐브를 푸는 중입니까?
A
답변
2
3x3x3 루빅 큐브를 해결하는 것은 O (1)입니다. 루빅의 큐브는 거의 확실하게 NP 하드입니다. 그러나 이것에 대한 엄격한 증거가 있는지 확실하지 않습니다. 어쩌면 여기에서보기 시작하십시오 : https://cstheory.stackexchange.com/questions/783/is-optimally-solving-the-n × n × n-rubiks-cube-np-hard
+0
최적의 솔루션에 대해 이야기하고 있다고해도? 같은, 가능한 한 짧은 이동 수. –
+0
3x3x3 큐브의 경우 여전히 O (1)입니다. 각 구성에 대해 최적의 이동 표를 만들 수 있습니다 (3x3x3 큐브의 구성 수는 매우 큰 경우에도 O (1)입니다). 다시 말하지만, 임의 구성에서 NxNxN 큐브에 대한 최적의 이동을 찾는 것은 아마도 매우 어렵습니다. –
+0
큐브의 모든 구성을 최적으로 해결할 수있는 알고리즘이 있다는 것을 의미합니까? 또는이 두 가지 사이에 어떤 깨달음도 없습니까? –
3 × 1 × 5 루비크 큐브와 3 × 1 × 5 루비 큐브는 무엇입니까? – greybeard