Божји алгоритам

Божји алгоритам је алгоритам који има за циљ да реши одређени проблем у најмањем могућем броју потеза. Може се рећи и да је то теоријски алгоритам, увек специфичан за дати проблем. То се првенствено односи на решавање Рубикове коцке, али и на неке математичке загонетке.^[1]

Име је добио од идеје да постоји свезнајуће биће које у сваком тренутку зна да реши загонетку на оптималан начин, односно у најмањем могућем броју потеза или корака, почевши од било које задате конфигурације.

Дефиниција уреди

Појам божјег алгоритма је искључиво применљив на загонетке које могу имати коначан број „конфигурација“, и мали број потеза који се могу применити на тренутне конфигурације, које ће затим довести до новх конфигурација. Решавање загонетке подразумева достизање специфично дизајниране коначне конфигурације (или једне из колекције финалних конфигурација), примењујући секвенцу покрета, почевши од неке произвољне почетне конфигурације.

Примери уреди

Најпознатије загонетке које се решавају по поменутом принципу су Рубикова коцка, Ханојске куле, и игра 15 пазли. Овде спадају и многе логичке загонетке, попут проблема мисионара и канибала. Све се могу приказати математички преко усмереног графа, при чему су конфигурације темена а потези гране.

Алгоритам се може сматрати употребљивим за дату врсту проблема ако за улазну вредност узимају произвољну почетну конфигурацију, а као излазну вредност дају секвенцу покрета која је довела до финалне конфигурације. Загонетка мора бити решива из те почетне конфигурације, иначе се сматра нерешивом. Решење је оптимално ако је секвенца покрета што краћа. Самим тим, божји алгоритам за дату загонетку је алгоритам који је решава и даје само оптимална решења.

Неки писци, попут Дејвида Џојнера, сматрају да, ако такав алгоритам већ називамо „божјим“, требало би да буде и практичан, тј. да не захтева превелике количине меморије или времена; на пример, коришћење огромне табеле са индексима почетних конфигурација би довело до веома брзих решења, али би то захтевало огромну количину меморије. Дакле, оптимално решење представља решење које не захтева више потеза него што је потребно.

Уместо тражења потпуног решења, неко може исто тако да тражи један покрет од иницијалне али не финалне конфигурације, где је тражени покрет први покрет неког оптималног решења. Алгоритми за једнопотезну верзију проблема могу бити претворени у алгоритам оригиналног проблема тако што ћемо је константно позивати док примењујемо сваки покрет у датој тренутној конфигурацији, док не стигнемо до финалне.

Насупрот томе, сваки алгоритам који решава оригинални проблем може бити претворен у алгоритам верзије једног покрета тако што скраћујемо производ до првог покрета. Игра 15 пазли се у најгорем случају може решити у 80 покрета у случају да имамо само једно поље, или у 43 потеза у случају да имамо више поља. У случају да генерализујемо проблем на н слагалица, за проблем налажења оптималног решења кажемо да се може решити у [полиномијално време | полиномијалном времену]. Самим тим, мало је вероватно да божји алгоритам за овај проблем постоји.

За ханојске куле, божји алгоритам постоји за било који дати број дискова, међутим број покрета расте експоненцијално са порастом броја дискова.

Алгоритам за проналажење оптималног решења Рубикове коцке објављен је 1997. године од стране Ричарда Корфа. Први пут када је покушано да се пронађе доња граница броја потеза било је 1981.године. Иако се од 1995. године зна да је 20 доња граница за број потеза за решење у најгорем случају, 2010. је уз помоћ обимних рачунарских прорачуна доказано да ниједна могућа почетна конфигурација не захтева више од 20 потеза, па можемо рећи да је 20 уствари горња граница. Овај број је познатији и као Божји број.^[2]

Нерешене игре уреди

За неке врло познате игре са веома лимитираним сетом једноставних правила и потеза никада није пронађен божји алгоритам. Примери су шах и го, јапанска игра. Обе ове игре имају особину да се приликом сваког потеза убрзано повећава број позиција. Укупни број свих могућих позиција, отприлике 10154 за шах и 10180 за го (на табли 19x19) је превелики да би се добило решење коришћењем тренутне рачунске технологије. Сходно томе, одређивање божјег алгоритма за ове игре није могуће. Иако су одређени рачунари направљени тако да могу да победе у шаху чак и најбоље играче, они не рачунају игру од самог почетка до краја. Рачунар Дееп Блуе рачуна само 11 потеза унапред, што смањује простор за претрагу на 1017. Након овога, он оцењује сваку позицију за предност према правилима изведеним из људске игре и искуства.

Чак и ова стратегија није могућа за го. Поред тога што постоји изузетно више позиција за оцену, нико до сад није успешно изградио сет једноставних правила за оцењивање снаге Го играча као што је урађено за шах. Алгоритми процене су склони да праве елементарне грешке, тако да, чак и за лимитирани поглед унапред са ограниченим циљем да се пронађе најснажнија привремена позиција, божји алгоритам није могућ за Го.

Референце уреди

^ Паул Антхонy Јонес, Једбургх Јустице анд Кентисх Фире: Тхе Оригинс оф Енглисх ин Тен Пхрасес анд Еxпрессионс, Хацхетте УК, 2014 ISBN 9781472116222.
^ Јонатхан Филдес (11. 8. 2010). „Рубик'с Цубе qуест фор спеедy солутион цомес то ан енд”. ББЦ Неwс.

Литература уреди

Баум, Ериц Б., Wхат ис Тхоугхт?, МИТ Пресс, 2004 ISBN 9780262025485.
Давис, Даррyл Н.; Цхалаби, Т.; Бербанк-Греен, Б., "Артифициал-лифе, агентс анд Го", ин Мохаммадиан, Масоуд, Неw Фронтиерс ин Цомпутатионал Интеллигенце анд итс Апплицатионс, пп. 125–139, ИОС Пресс, 2000 ISBN 9789051994766.
Фрасер, Робер (ед); Ханнах, W. (ед), Тхе Драугхт Плаyерс' Wееклy Магазине, вол. 2, Гласгоw: Ј Х Беррy, 1885.
Давид Јоyнер (2002). Адвентурес ин Гроуп Тхеорy. Јохнс Хопкинс Университy Пресс. ИСБН 0-8018-6947-1.
Мооре, Цристопхер; Мертенс, Степхан, Тхе Натуре оф Цомпутатион, Оxфорд Университy Пресс, 2011 ISBN 9780191620805.
Ротхенберг, Гади, Цаталyсис, Год'с Алгоритхм, анд тхе Греен Демон, Амстердам Университy Пресс, 2009 ISBN 9789056295899.
Јонатхан Сцхаеффер, Неил Бурцх, Yнгви Бјöрнссон, Акихиро Кисхимото, Мартин Мüллер, Роберт Лаке, Паул Лу, Стеве Сутпхен, "Цхецкерс ис солвед", Сциенце, вол. 317, но. 58444, пп. 1518–1522, 14 Септембер 2007.
Сингмастер, Давид, Нотес он Рубик'с Магиц Цубе, Пенгуин, 1981 ISBN 978-0-907395-00-3.
Сингмастер, Давид, "Тхе едуцатионал валуе оф тхе Хунгариан 'Магиц Цубе'", Процеедингс оф тхе Фоуртх Интернатионал Цонгресс он Матхематицал Едуцатион, хелд ин Беркелеy, Цалфорниа, 10–16 Аугуст 1980, пп. 307–312, Биркхаусер Бостон Инц, 1983 ISBN 978-0-8176-3082-9.

Спољашње везе уреди

[1] Паул Антхонy Јонес, Једбургх Јустице анд Кентисх Фире: Тхе Оригинс оф Енглисх ин Тен Пхрасес анд Еxпрессионс, Хацхетте УК, 2014 ISBN 9781472116222.

[2] Јонатхан Филдес (11. 8. 2010). „Рубик'с Цубе qуест фор спеедy солутион цомес то ан енд”. ББЦ Неwс.

[1]

[2]