Algorytm Boga

Algorytm Boga to pojęcie wywodzące się z dyskusji o sposobach układania kostki Rubika , które można jednak zastosować również do innych łamigłówek kombinatorycznych i gier matematycznych . Odnosi się do dowolnego algorytmu, który tworzy rozwiązanie o najmniejszej możliwej liczbie ruchów. Aluzja do Bóstwa opiera się na założeniu, że tylko wszechwiedząca znałaby optymalny krok z dowolnej konfiguracji.

Zakres

Definicja

Pojęcie to odnosi się do łamigłówek , które mogą zakładać skończoną liczbę „konfiguracji”, ze stosunkowo niewielkim, dobrze zdefiniowanym arsenałem „ruchów”, które mogą mieć zastosowanie do konfiguracji, a następnie prowadzić do nowej konfiguracji. Rozwiązanie zagadki oznacza osiągnięcie wyznaczonej „ostatecznej konfiguracji”, pojedynczej konfiguracji lub jednej ze zbioru konfiguracji. Aby rozwiązać zagadkę, stosuje się sekwencję ruchów, zaczynając od dowolnej konfiguracji początkowej.

Rozwiązanie

Algorytm można uznać za rozwiązujący taką łamigłówkę, jeśli na wejściu przyjmuje dowolną konfigurację początkową, a na wyjściu generuje sekwencję ruchów prowadzących do ostatecznej konfiguracji ( jeśli łamigłówkę można rozwiązać z tej początkowej konfiguracji, w przeciwnym razie sygnalizuje niemożność rozwiązanie). Rozwiązanie jest optymalne, jeśli sekwencja ruchów jest możliwie najkrótsza. Najwyższa wartość tego spośród wszystkich początkowych konfiguracji jest znana jako liczba Boga lub, bardziej formalnie, minimaks wartość. Zatem algorytm Boga dla danej zagadki jest algorytmem, który rozwiązuje tę zagadkę i daje tylko rozwiązania optymalne.

Niektórzy autorzy, tacy jak David Joyner, uważają, że aby algorytm był właściwie określany jako „algorytm Boży”, powinien być również praktyczny , co oznacza, że algorytm nie wymaga nadzwyczajnej ilości pamięci ani czasu. Na przykład użycie gigantycznej tabeli przeglądowej indeksowanej przez początkowe konfiguracje pozwoliłoby na bardzo szybkie znalezienie rozwiązań, ale wymagałoby nadzwyczajnej ilości pamięci.

Zamiast prosić o pełne rozwiązanie, można równoważnie poprosić o pojedynczy ruch z początkowej, ale nie ostatecznej konfiguracji, gdzie ruch jest pierwszym z jakiegoś optymalnego rozwiązania. Algorytm dla wersji problemu z pojedynczym ruchem można przekształcić w algorytm dla pierwotnego problemu, wywołując go wielokrotnie, stosując każdy ruch zgłoszony do bieżącej konfiguracji, aż do osiągnięcia ostatecznego; i odwrotnie, każdy algorytm dla pierwotnego problemu można przekształcić w algorytm dla wersji z jednym ruchem, obcinając jego dane wyjściowe do pierwszego ruchu.

Przykłady

Dobrze znane łamigłówki pasujące do tego opisu to łamigłówki mechaniczne, takie jak Kostka Rubika , Wieże Hanoi i łamigłówka 15 . Obejmuje również jednoosobową grę w pasjansa peg , a także wiele zagadek logicznych , takich jak problem misjonarzy i kanibali . Ich wspólną cechą jest to, że można je modelować matematycznie jako graf skierowany , w którym konfiguracje są wierzchołkami, a ruchy łukami.

Łamigłówki mechaniczne

n -Zagadki

Zagadkę Piętnaście można rozwiązać w 80 ruchach pojedynczych płytek lub w najgorszym przypadku w 43 ruchach wielu płytek. Dla uogólnienia n -puzzle, problem znalezienia optymalnego rozwiązania jest NP-trudny . Dlatego to, czy istnieje praktyczny algorytm Boga dla tego problemu, pozostaje nieznane, ale wydaje się mało prawdopodobne. ^{[ według kogo? ]}^{[ redakcja ]}

Wieże Hanoi

W przypadku układanki Wieże Hanoi algorytm Boga jest znany dla dowolnej liczby dysków. Liczba ruchów jest wykładnicza w liczbie dysków ( ${\ Displaystyle 2 ^ {n} -1}$ ) .

Kostka Rubika

Algorytm określający minimalną liczbę ruchów potrzebnych do ułożenia kostki Rubika został opublikowany w 1997 roku przez Richarda Korfa. Chociaż od 1995 roku wiadomo było, że 20 to dolna granica liczby ruchów rozwiązania w najgorszym przypadku, Tom Rokicki udowodnił w 2010 roku, że żadna konfiguracja nie wymaga więcej niż 20 ruchów. Zatem 20 to ostra górna granica długości rozwiązań optymalnych. Matematyk David Singmaster „pochopnie przypuszczał”, że liczba ta wynosi 20 w 1980 roku.

Nierozwiązane gry

W niektórych dobrze znanych grach z bardzo ograniczonym zestawem prostych, dobrze zdefiniowanych zasad i ruchów nigdy nie określono algorytmu ich Boga dla zwycięskiej strategii. Przykładami są gry planszowe szachy i Go . Obie te gry mają szybko rosnącą liczbę pozycji z każdym ruchem. Całkowita liczba wszystkich możliwych pozycji, około 10 ¹⁵⁴ w szachach i 10 ¹⁸⁰ (na planszy 19×19) w Go, jest o wiele za duża, aby umożliwić rozwiązanie siłowe przy obecnej technologii komputerowej (porównaj teraz rozwiązane, z wielkim trudem , Kostka Rubika tylko około 4,3 × 10 ¹⁹ pozycji). W związku z tym brutalne określenie algorytmu Boga dla tych gier nie jest możliwe. Chociaż zbudowano komputery szachowe, które są w stanie pokonać nawet najlepszych ludzkich graczy, nie kalkulują one gry do samego końca. Deep Blue szukał tylko 11 ruchów do przodu (licząc ruch każdego gracza jako dwa ruchy), zmniejszając pole wyszukiwania do zaledwie 10 ¹⁷ . Następnie oceniał każdą pozycję pod kątem przewagi zgodnie z zasadami wywodzącymi się z ludzkiej gry i doświadczenia.

Nawet ta strategia nie jest możliwa w Go. Poza koniecznością oceny znacznie większej liczby pozycji, nikomu jak dotąd nie udało się skonstruować zestawu prostych reguł oceny siły pozycji Go, tak jak to miało miejsce w przypadku szachów. Algorytmy oceny są podatne na popełnianie elementarnych błędów, więc nawet przy ograniczonym spojrzeniu w przyszłość z celem ograniczonym do znalezienia najsilniejszej tymczasowej pozycji, Boży algorytm nie był możliwy dla Go.

Z drugiej strony warcaby (warcaby), z powierzchownymi podobieństwami do szachów, od dawna podejrzewa się o to, że są „rozgrywane” przez doświadczonych praktyków. W 2007 Schaeffer i in. udowodnił to, obliczając bazę danych wszystkich pozycji z dziesięcioma lub mniej elementami. Tak więc Schaeffer ma Boży algorytm dla wszystkich końcowych partii warcabów i wykorzystał go do udowodnienia, że wszystkie doskonale rozegrane partie warcabów zakończą się remisem. Jednak warcaby z zaledwie 5 × 10 ²⁰ pozycji, a jeszcze mniej, 3,9 × 10 ¹³ , w bazie danych Schaeffera, jest znacznie łatwiejszym problemem do złamania i jest tego samego rzędu co kostka Rubika.

Wielkość zbioru pozycji układanki nie przesądza całkowicie o tym, czy Boży algorytm jest możliwy. Rozwiązana już łamigłówka Wieża Hanoi może składać się z dowolnej liczby elementów, a liczba pozycji rośnie wykładniczo jako ${\ displaystyle 3 ^ {n}}$ . Niemniej jednak algorytm rozwiązania ma zastosowanie do problemu o dowolnej wielkości, z czasem działania ${\ Displaystyle O (2 ^ {n})}$ .

Zobacz też

Notatki

Baum Eric B., Czym jest myśl? , MIT Press, 2004 ISBN 0262025485 .
Davis, Darryl N.; Chalabi, T.; Berbank-Green, B., „Sztuczne życie, agenci i Go”, w Mohammadian, Masoud, New Frontiers in Computational Intelligence and its Applications , s. 125–139, IOS Press, 2000 ISBN 9051994761 .
Fraser, Rober (red.); Hannah, W. (red.), Tygodniowy magazyn graczy Draft , obj. 2, Glasgow: JH Berry, 1885.
Joyner, David (2002). Przygody w teorii grup . Wydawnictwo Uniwersytetu Johnsa Hopkinsa. ISBN 0-8018-6947-1 .
Moore, Cristopher; Mertens, Stephan, Natura obliczeń , Oxford University Press, 2011 ISBN 0191620807 .
Rothenberg, Gadi, Catalysis, God's Algorithm, and the Green Demon , Amsterdam University Press, 2009 ISBN 9056295896 .
Schaeffer, Jonathan; Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, „Warcaby rozwiązano” , Science , tom. 317, nr. 58444, s. 1518–1522, 14 września 2007 r.
Singmaster, David, Uwagi na temat magicznej kostki Rubika , Penguin, 1981 ISBN 0-907395-00-7 .
Singmaster, David, „Wartość edukacyjna węgierskiej„ magicznej kostki ”, Proceedings of the Fourth International Congress on Mathematical Education , która odbyła się w Berkeley w Kalifornii, 10–16 sierpnia 1980, s. 307–312, Birkhauser Boston Inc, 1983 ISBN 978-0-8176-3082-9 .