Dievo algoritmas

 

Dievo algoritmas - tai sąvoka, kilusi iš diskusijų apie Rubiko kubo sudėjimo būdus, tačiau gali būti pritaikoma kitiems kombinatoriniams galvosūkiams ir matematiniams žaidimams. Dievo algoritmas tinka bet kokiam praktiškam algoritmui, kurio sprendimas pagrįstas mažiausiu galimu pasukimų skaičiumi; tai idėja, reiškianti, kad visažinė būtybė žino optimalų sprendimą bet kokiai galimai konfigūracijai.

Sąvoka tinka galvosūkiams, turintiems baigtinį skaičių konfigūracijų, su pakankamai maža aibe gerai apibrėžtų "ėjimų", kurie gali būti pritaikomi, kad privestų prie naujos konfigūracijos. Išspręsti galvosūkį, reiškia, pasiekti specialiai nustatytą vadinamą "galutinę konfigūraciją", atliekant ėjimų seką, pradedant nuo sutartos pirminės pozicijos.

Kryptinis grafas
Kryptinis grafas

Keli gerai žinomi galvosūkiai, atitinkantys šį aprašymą yra mechaniniai galvosūkiai, tokie kaip Rubiko kubas, Hanojaus bokštai arba žaidimas-galvosūkis 15, taip pat daug loginių galvosūkių. Jie yra panašūs tuo, kad gali būti matematiškai sumodeliuoti kaip kryptinis grafas, kuriame konfigūracijos yra grafo viršūnės, o ėjimai - grafo lankai.

Sakoma, kad algoritmas išsprendžia galvosūkį, jei jis sutartai pradinei pozicijai pateikia ėjimų seką, kuria pasiekiama galutinė pozicija, jei galvosūkis yra išsprendžiamas iš tos pradinės konfigūracijos, arba praneša, kad galvosūkis neišsprendžiamas. Sprendimas yra optimalus, jei jis yra kiek įmanoma trumpas. Taigi Dievo algoritmas duotam galvosūkiui yra algoritmas, kuris išsprendžia galvosūkį ir pateikia tik optimalius sprendimus.

Kad būtų prasminga sąvoka "Dievo algoritmas", reikalaujama, kad algoritmas būtų praktiškas, t.y., nereikalautų didžiulio kiekio atminties arba laiko. Be šio reikalavimo, "Dievo algoritmas" egzistuoja visada. Paprasčiausias trivialus algoritmas yra tas, kuris iš esmės turi didžiulę iš anksto apskaičiuotą lentelę, indeksuotą pradinėmis konfigūracijomis, duodančią optimalų sprendimą kiekvienam įrašui.

Pavyzdžiai

Nėra žinoma, ar egzistuoja Dievo algoritmas Rubiko kubui. 2007 metų rugpjūtį, Daniel'is Kunkle ir Gene Cooperman'as panaudojo superkompiuterį, kad parodytų, jog kiekvienam sumaišytam kubui sudėti reikia ne daugiau kaip 26 pasukimų.

Žaidimui N, žaidimo 15 apibendrinimui, taip pat nežinoma, ar egzistuoja Dievo algoritmas.

15-puzzle-01.jpg
 Žaidimas 15-raktų pakabukas
 
Išspręstas žaidimas 15

Hanojaus bokštų galvosūkiui Dievo algoritmas egzistuoja bet kokiam duotam diskų skaičiui.

Trijų diskų Hanojaus bokštas
Keturių diskų Hanojaus bokštas
Parašyta: 2010-12-09
Autorius: Rubik.lt
Kategorija: Straipsnis
Komentarų (0)

Komentarai

Komentaras

Vardas:


El.paštas:


Kodas: kodas


Žinutė: