Božji algoritam

S Vikipedije, slobodne enciklopedije

Božji algoritam je algoritam koji ima za cilj da reši određeni problem u najmanjem mogućem broju poteza. Može se reći i da je to teorijski algoritam, uvek specifičan za dati problem. To se prvenstveno odnosi na rešavanje Rubikove kocke, ali i na neke matematičke zagonetke.[1]

Ime je dobio od ideje da postoji sveznajuće biće koje u svakom trenutku zna da reši zagonetku na optimalan način, odnosno u najmanjem mogućem broju poteza ili koraka, počevši od bilo koje zadate konfiguracije.

Definicija[uredi | uredi izvor]

Pojam božjeg algoritma je isključivo primenljiv na zagonetke koje mogu imati konačan broj „konfiguracija“, i mali broj poteza koji se mogu primeniti na trenutne konfiguracije, koje će zatim dovesti do novh konfiguracija. Rešavanje zagonetke podrazumeva dostizanje specifično dizajnirane konačne konfiguracije (ili jedne iz kolekcije finalnih konfiguracija), primenjujući sekvencu pokreta, počevši od neke proizvoljne početne konfiguracije.

Primeri[uredi | uredi izvor]

Najpoznatije zagonetke koje se rešavaju po pomenutom principu su Rubikova kocka, Hanojske kule, i igra 15 pazli. Ovde spadaju i mnoge logičke zagonetke, poput problema misionara i kanibala. Sve se mogu prikazati matematički preko usmerenog grafa, pri čemu su konfiguracije temena a potezi grane.

Algoritam se može smatrati upotrebljivim za datu vrstu problema ako za ulaznu vrednost uzimaju proizvoljnu početnu konfiguraciju, a kao izlaznu vrednost daju sekvencu pokreta koja je dovela do finalne konfiguracije. Zagonetka mora biti rešiva iz te početne konfiguracije, inače se smatra nerešivom. Rešenje je optimalno ako je sekvenca pokreta što kraća. Samim tim, božji algoritam za datu zagonetku je algoritam koji je rešava i daje samo optimalna rešenja.

Neki pisci, poput Dejvida Džojnera, smatraju da, ako takav algoritam već nazivamo „božjim“, trebalo bi da bude i praktičan, tj. da ne zahteva prevelike količine memorije ili vremena; na primer, korišćenje ogromne tabele sa indeksima početnih konfiguracija bi dovelo do veoma brzih rešenja, ali bi to zahtevalo ogromnu količinu memorije. Dakle, optimalno rešenje predstavlja rešenje koje ne zahteva više poteza nego što je potrebno.

Umesto traženja potpunog rešenja, neko može isto tako da traži jedan pokret od inicijalne ali ne finalne konfiguracije, gde je traženi pokret prvi pokret nekog optimalnog rešenja. Algoritmi za jednopoteznu verziju problema mogu biti pretvoreni u algoritam originalnog problema tako što ćemo je konstantno pozivati dok primenjujemo svaki pokret u datoj trenutnoj konfiguraciji, dok ne stignemo do finalne.

Nasuprot tome, svaki algoritam koji rešava originalni problem može biti pretvoren u algoritam verzije jednog pokreta tako što skraćujemo proizvod do prvog pokreta. Igra 15 pazli se u najgorem slučaju može rešiti u 80 pokreta u slučaju da imamo samo jedno polje, ili u 43 poteza u slučaju da imamo više polja. U slučaju da generalizujemo problem na n slagalica, za problem nalaženja optimalnog rešenja kažemo da se može rešiti u [polinomijalno vreme | polinomijalnom vremenu]. Samim tim, malo je verovatno da božji algoritam za ovaj problem postoji.

Za hanojske kule, božji algoritam postoji za bilo koji dati broj diskova, međutim broj pokreta raste eksponencijalno sa porastom broja diskova.

Algoritam za pronalaženje optimalnog rešenja Rubikove kocke objavljen je 1997. godine od strane Ričarda Korfa. Prvi put kada je pokušano da se pronađe donja granica broja poteza bilo je 1981.godine. Iako se od 1995. godine zna da je 20 donja granica za broj poteza za rešenje u najgorem slučaju, 2010. je uz pomoć obimnih računarskih proračuna dokazano da nijedna moguća početna konfiguracija ne zahteva više od 20 poteza, pa možemo reći da je 20 ustvari gornja granica. Ovaj broj je poznatiji i kao Božji broj.[2]

Nerešene igre[uredi | uredi izvor]

Za neke vrlo poznate igre sa veoma limitiranim setom jednostavnih pravila i poteza nikada nije pronađen božji algoritam. Primeri su šah i go, japanska igra. Obe ove igre imaju osobinu da se prilikom svakog poteza ubrzano povećava broj pozicija. Ukupni broj svih mogućih pozicija, otprilike 10154 za šah i 10180 za go (na tabli 19x19) je preveliki da bi se dobilo rešenje korišćenjem trenutne računske tehnologije. Shodno tome, određivanje božjeg algoritma za ove igre nije moguće. Iako su određeni računari napravljeni tako da mogu da pobede u šahu čak i najbolje igrače, oni ne računaju igru od samog početka do kraja. Računar Deep Blue računa samo 11 poteza unapred, što smanjuje prostor za pretragu na 1017. Nakon ovoga, on ocenjuje svaku poziciju za prednost prema pravilima izvedenim iz ljudske igre i iskustva.

Čak i ova strategija nije moguća za go. Pored toga što postoji izuzetno više pozicija za ocenu, niko do sad nije uspešno izgradio set jednostavnih pravila za ocenjivanje snage Go igrača kao što je urađeno za šah. Algoritmi procene su skloni da prave elementarne greške, tako da, čak i za limitirani pogled unapred sa ograničenim ciljem da se pronađe najsnažnija privremena pozicija, božji algoritam nije moguć za Go.

Reference[uredi | uredi izvor]

  1. ^ Paul Anthony Jones, Jedburgh Justice and Kentish Fire: The Origins of English in Ten Phrases and Expressions, Hachette UK, 2014 ISBN 9781472116222.
  2. ^ Jonathan Fildes (11. 8. 2010). „Rubik's Cube quest for speedy solution comes to an end”. BBC News. 

Literatura[uredi | uredi izvor]

  • Baum, Eric B., What is Thought?, MIT Press, 2004 ISBN 9780262025485.
  • Davis, Darryl N.; Chalabi, T.; Berbank-Green, B., "Artificial-life, agents and Go", in Mohammadian, Masoud, New Frontiers in Computational Intelligence and its Applications, pp. 125–139, IOS Press, 2000 ISBN 9789051994766.
  • Fraser, Rober (ed); Hannah, W. (ed), The Draught Players' Weekly Magazine, vol. 2, Glasgow: J H Berry, 1885.
  • David Joyner (2002). Adventures in Group Theory. Johns Hopkins University Press. ISBN 0-8018-6947-1. 
  • Moore, Cristopher; Mertens, Stephan, The Nature of Computation, Oxford University Press, 2011 ISBN 9780191620805.
  • Rothenberg, Gadi, Catalysis, God's Algorithm, and the Green Demon, Amsterdam University Press, 2009 ISBN 9789056295899.
  • Jonathan Schaeffer, Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, Steve Sutphen, "Checkers is solved", Science, vol. 317, no. 58444, pp. 1518–1522, 14 September 2007.
  • Singmaster, David, Notes on Rubik's Magic Cube, Penguin, 1981 ISBN 978-0-907395-00-3.
  • Singmaster, David, "The educational value of the Hungarian 'Magic Cube'", Proceedings of the Fourth International Congress on Mathematical Education, held in Berkeley, Calfornia, 10–16 August 1980, pp. 307–312, Birkhauser Boston Inc, 1983 ISBN 978-0-8176-3082-9.

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Božji_algoritam&oldid=27673041”