신의 알고리즘

God's algorithm

신의 알고리즘은 루빅스 큐브 [1]퍼즐을 푸는 방법에 대한 논의에서 유래한 개념이지만, 다른 조합 퍼즐이나 [2]수학 게임에도 적용될 수 있습니다.가장 적은 수의 이동으로 솔루션을 생성하는 알고리즘을 말합니다.신에 대한 암시는 오직 전지전능한 존재만이 주어진 구성에서 최적의 단계를 알 수 있다는 가정에 기초한다.

범위

정의.

이 개념은 한정된 수의 "구성"을 가정할 수 있는 퍼즐에 적용되며, 구성에 적용할 수 있는 "이동"은 비교적 작고 명확하게 정의되어 있으며, 이후 새로운 구성으로 이어질 수 있습니다.퍼즐을 푸는 것은 지정된 "최종 구성", 단일 구성 또는 구성 집합 중 하나에 도달하는 것을 의미합니다.퍼즐을 풀기 위해 임의의 초기 구성부터 일련의 이동이 적용됩니다.

솔루션

알고리즘은 임의의 초기 구성을 입력으로 받아들이고 최종 구성으로 이어지는 일련의 움직임을 출력으로 생성하는 경우(초기 구성에서 퍼즐이 해결 불가능을 나타내는 경우) 이러한 퍼즐을 해결하는 것을 고려할 수 있습니다.이동 시퀀스가 가능한 한 짧으면 솔루션이 최적입니다.이 카운트는 신의 수,[3] 또는 더 공식적으로 미니맥스 [4]값으로 알려져 있습니다.주어진 퍼즐에 대한 신의 알고리즘은 퍼즐을 풀고 최적의 해법만을 만들어내는 알고리즘이다.

데이비드 조이너와 같은 일부 작가는 알고리즘이 "신의 알고리즘"이라고 적절하게 언급되기 위해서는 알고리즘에 엄청난 양의 메모리나 시간이 필요하지 않음을 의미하기 때문에 실용적이어야 한다고 생각합니다.예를 들어 초기 구성으로 인덱싱된 거대한 룩업 테이블을 사용하면 솔루션을 매우 빠르게 찾을 수 있지만 엄청난 양의 [5]메모리가 필요합니다.

완전한 솔루션을 요구하는 것이 아니라, 최종 구성이 아닌 초기 구성에서 한 번의 이동을 요구할 수 있습니다. 이 경우 최적의 솔루션 중 첫 번째가 이행입니다.문제의 싱글 무브 버전의 알고리즘은 현재 구성에 보고된 각 동작을 적용하면서 최종적인 것에 도달할 때까지 반복하여 호출함으로써 원래 문제의 알고리즘으로 변환할 수 있습니다.반대로 원래 문제의 알고리즘은 tr에 의해 싱글 무브 버전의 알고리즘으로 변환할 수 있습니다.첫 번째 동작에서 출력을 제거합니다.

예

이 설명에 맞는 잘 알려진 퍼즐은 루빅스 큐브, 하노이의 탑, 그리고 15개의 퍼즐과 같은 기계 퍼즐이다.페그 솔리테어 1인 게임과 선교사 문제, 식인종 문제 등 많은 논리 퍼즐도 다룹니다.이들에는 수학적으로 유향 그래프로 모델링할 수 있다는 공통점이 있습니다.여기서 구성은 정점이고는 호를 이동합니다.

기계 퍼즐

n-퍼즐

15개의 퍼즐은 최악의 경우 80개의 싱글타일[6] 이동 또는 43개의 멀티타일[7] 이동으로 풀 수 있습니다.n-퍼즐의 일반화를 위해 최적의 솔루션을 찾는 문제는 NP-hard이다.[8]그러므로, 이 문제에 대한 실용적인 신의 알고리즘이 존재하는지 여부는 알려지지 않았지만,[according to whom?][editorializing] 가능성이 희박해 보인다.

하노이의 타워

하노이 타워 퍼즐의 경우 주어진 디스크 수에 대해 신의 알고리즘이 알려져 있습니다.이동 수는 디스크 수(- { 2[9]로 기하급수적입니다.

루빅스 큐브

주요 기사:Rubik's Cube에 최적인 솔루션

Rubik's Cube를 해결하기 위한 최소 이동 수를 결정하는 알고리즘은 Richard Korf에 [10]의해 1997년에 발표되었다.1995년 이후 최악의 경우 솔루션의 이동 수가 20개보다 낮다는 사실이 알려졌지만 Tom Rockicki는 2010년 어떤 구성도 20개 이상의 이동을 [11]필요로 하지 않는다는 것을 증명했습니다.따라서 20은 최적 솔루션의 길이에 대한 명확한 상한입니다.수학자 데이비드 싱마스터는 1980년에 [4]이 숫자를 20으로 "대략적으로 추측"했다.

미해결 게임

매우 제한된 규칙과 움직임을 가진 잘 알려진 몇몇 게임들은 그럼에도 불구하고 승리 전략을 위한 신의 알고리즘이 결정되지 않았다.예를 들면 체스나 [12]바둑이 있다.두 게임 모두 매 동작마다 포지션 수가 빠르게 증가하고 있다.체스의 경우 약 10개, [14]바둑의180 경우 약[13] 10개154 등 가능한 모든 포지션의 수는 현재의 컴퓨팅 테크놀로지로 무리한 솔루션을 구현하기에는 너무 큽니다(현재 해결된 Rubik's Cube는 약 4.3×10개의19[15] 포지션에 불과합니다).따라서 이들 게임에 대한 신의 알고리즘의 무차별적인 결정은 불가능하다.체스 컴퓨터는 아무리 뛰어난 인간 선수라도 이길 수 있는 것이 만들어졌지만 끝까지 게임을 계산하지는 않는다.예를 들어 Deep Blue는 11개만 먼저 검색하여(각 플레이어의 한 수를 2개로 계산) 검색 공간을 [16]10개로17 줄였습니다.이후 인간의 놀이와 경험에서 도출된 규칙에 따라 각 포지션의 장점을 평가했다.

바둑에서는 이 전략도 불가능하다.평가해야 할 포지션이 매우 많을 뿐만 아니라, 지금까지 아무도 [17]체스처럼 바둑 포지션의 강도를 평가하는 간단한 규칙을 성공적으로 구축하지 못했다.평가 알고리즘은 기본적인 실수를[18] 하기 쉽기 때문에 가장 강력한 중간 포지션을 찾는다는 목표를 가지고 제한적으로 앞을 보더라도 바둑에는 신의 알고리즘이 불가능했다.

반면에, 체스와 표면적으로 유사한 드로트([19]체커)는 오랫동안 체스의 전문가들에 의해 "실행되고" 있다는 의심을 받아왔다.2007년 Schaeffer 등은 10개 이하의 모든 위치에 대한 데이터베이스를 계산하여 이러한 사실을 입증했다.따라서 셰퍼는 드래프트의 모든 엔드게임에 신의 알고리즘을 가지고 있으며, 이것을 사용하여 완벽하게 플레이된 드래프트의 모든 게임이 [20]무승부로 끝난다는 것을 증명한다.그러나 섀퍼의 데이터베이스에서 [22]5×10의20[21] 위치만 있고 심지어 더 적은13 3.9×10의 드래프트는 크래킹하기 훨씬 쉬운 문제이며 루빅의 큐브와 같은 순서이다.

퍼즐의 위치 집합의 크기가 신의 알고리즘이 가능한지를 완전히 결정하지는 않는다.이미 해결된 하노이 타워 퍼즐은 임의의 조각 수를 가질 수 있으며, 위치 는 3n으로 기하급수적으로 증가하지만,이 솔루션 알고리즘은 (O([23]의 실행 시간으로 모든 크기 문제에 적용할 수 있습니다.

「 」를 참조해 주세요.

메모들

  1. ^ Paul Anthony Jones, Jedburg Justice 및 Kentish Fire: 영국 Hachette, 2014년 10개의 문구와 표현에서 영어의 기원 ISBN1472116224.
  2. ^ 예를 들어,Ernö Rubik, Tamas Varga, Gerzson Kéri, György Marx 및 Tamas Vecerdy(1987, 옥스포드 대학 출판부, ISBN 0-19-853202-4), 페이지 20.7:... 피라믹스는 매직 큐브보다 훨씬 단순하다...Nicholas Hammond는 신의 알고리즘이 기껏해야 21개의 움직임이라는 것을 보여 주었다.[최근에 세 사람이 신의 알고리즘을 찾았다]최대 이동 수는 15개입니다(4개의 정점 이동 포함).]"
  3. ^ Jonathan Fildes (August 11, 2010). "Rubik's Cube quest for speedy solution comes to an end". BBC News.
  4. ^ a b 싱마스터, 311, 1980년
  5. ^ 조이너, 149페이지
  6. ^ A. Brüngger, A. Marzetta, K.후쿠다와 J. 니에버겔트, 병렬 검색 벤치 ZRAM 및 그 응용 프로그램, 운영 연구 연보 90(1999), 페이지 45-63.
  7. ^ Norskog, Bruce; Davidson, Morley (December 8, 2010). "The Fifteen Puzzle can be solved in 43 moves". Domain of the Cube Forum. Retrieved March 15, 2022.
  8. ^ 다니엘 래트너, 맨프레드 K 워무스(1986년)."15-퍼즐의 N × N 확장에 대한 최단 해법을 찾는 것은 어렵다."AAAI-86 절차에서.인공지능에 관한 전국회의, 1986. 페이지 168~172.
  9. ^ Rueda, Carlos (August 2000). "An optimal solution to the Towers of Hanoi Puzzle". Universidad Autónoma de Manizales [Autonomous University of Manizales]. Manizales, Colombia. Archived from the original on 2004-06-05. Retrieved March 15, 2022.
  10. ^ Richard E. Korf, "패턴 데이터베이스를 사용하여 Rubik's Cube에 대한 최적의 솔루션 찾기", Proc. Natl. Conf. 인공 지능(AAAI-97), 로드아일랜드 프로비던스, 1997년 7월, 페이지 700-705.
  11. ^ Rokicki, Tomas; Kociemba, Herbert; Davidson, Morley; Dethridge, John (2010). "God's Number is 20". Cube20.org. Retrieved March 15, 2022.
  12. ^ 로텐버그, 페이지 11
  13. ^ 바움, 187페이지
  14. ^ 바움, 199페이지
  15. ^ 싱마스터, 1981년
  16. ^ 바움, 188페이지
  17. ^ 바움, 197페이지
    • 모함마디안, 11페이지
  18. ^ 바움, 197페이지
  19. ^ 프레이저 & 한나, 197페이지
  20. ^ 무어와 메르텐스, 1.3장, "신과 체스를 두는 것"
  21. ^ 셰퍼 외, 페이지 1518
  22. ^ Moore & Mertens, 1장 '메모'
  23. ^ 루에다

레퍼런스

  • Baum, Eric B., What is Think?, MIT Press, 2004 ISBN 0262025485.
  • 데이비스, Darryl N.; Charabi, T.; Berbank-Green, B., Mahamadian, Masoud, New Frontiers in Computational Intelligence and 그 응용 프로그램, 페이지 125-139, IOS Press, 2000 BBN51961.
  • 프레이저, 로버(ed), 한나, W.(ed), 드래프트 플레이어스 위클리 매거진, 제2권, 글래스고: J H 베리, 1885.
  • Joyner, David (2002). Adventures in Group Theory. Johns Hopkins University Press. ISBN 0-8018-6947-1.
  • 무어, 크리스토퍼, 머텐스, 스테판, 계산의 본질, 옥스포드 대학 출판부, 2011 ISBN 0191620807.
  • Rodenberg, Gadi, Catalysis, God's Algorithm, Green Demon, Amsterdam University Press, 2009 ISBN 9056295896.
  • 셰퍼, 조나단; 닐 버치, Yngvi Björnsson, 키시모토 아키히로, 마틴 뮐러, 로버트 레이크, 폴 루, 스티브 수트펜, "체커는 해결되었다", 과학, 317, No.58444, 페이지 15.18–1522, 2007년 9월 14일.
  • Singmaster, David, Notes on Rubik's Magic Cube, Penguin, 1981 ISBN 0-907395-00-7.
  • Singmaster, David, "헝가리 '매직 큐브'의 교육적 가치", 1980년 8월 10-16일 캘리포니아 버클리, 307-312페이지, Birkhauser Boston Inc., 1983년 978-817-682.