Евристични програмиране, aideus

По времето на появата на компютрите, разпръснати данни на психология, етнология, психологията на животните, педагогика и методология на науката показва, че разузнаването е удобен както за способността за решаване на проблеми (проблем), както и решенията на процеса (мислене) се осъществява под формата на търсене на низ от действия, които да започнете ситуация (за състоянието на проблема), ще бъдат преведени до крайното положение (отговор). Започвайки с определено ниво на развитие на живите организми, твърде много действия от реалното им изпълнение се заменя с "виртуален" груба сила "сгънат" действие. В математиката, по това време, за да се стриктно описание на правилните аргументи се формализира концепцията на алгоритъма се разположи в зависимост от последователността на въвеждане на данни и описва решението на проблема в общи линии. Компютри са били създадени като устройството автоматично изпълнява алгоритми, т.е.. Е. За да реши проблемите, представени в символична форма. Въпреки това, основният въпрос остава: как да намерите алгоритмите или най-малко линейна верига от последователни действия? Поради NP-пълнота, или дори unsolvability общ проблем за намиране на пълен списък на всички варианти, в много случаи е невъзможно.

Според Поля, човек е в състояние по някакъв начин да се преодолее този проблем с помощта на евристични методи - методи, които улесняват решаването на проблеми. Но възможно ли е да се програмира евристичен? И ако е възможно, в каква форма трябва да се направи? Учените се опитват да отговорят на тези въпроси е довело до 1950-60-те години до появата на първата парадигма на изкуствен интелект, наречен "евристичен програмиране." В полето AI от самото й начало, има много различни области на научни изследвания, но това е евристичен програмиране може да бъде описан като първи опит да се създаде наистина обща теория на изкуствения интелект.

Евристичното програмиране проблем изкуствен интелект често учи по примера на интелектуални игри като пулове, шах, т. Г. От една страна, "Вселена" на всяка игрална маса се дава малък набор от много прости правила, които са лесни за програмата. От друга страна, по време на игра, като шах, със сигурност, че е необходимо да се мисли. Задачи доказват математически теореми и задачи за планиране са широко изследвани в евристичен програмиране, но те се нуждаят от допълнителни знания домейн (например, за да се обясни на човешките права на играта на шах е много по-лесно, отколкото на правилата за интеграция) и са по-малко демонстративен и по-сложни за изпълнение. Нека се опитаме да погледнем първо мислех проблема за проста игра.

Следните съображения могат да изглеждат тривиални се дължи на факта, че по-добре познати и по-сложни методи. Но си представите себе си на мястото на пионерите, които абсолютно нищо все още не е известна и тя не можеше да се заеме с готови решения. Това ще ви помогне да разберете по-добре причините и развитието на областта на евристичен програмиране и изкуствен интелект изследвания като цяло. Наистина, сред обичайните готови решения може да бъде повече случайни и не са оптимални и затова е добра идея да се преразгледа стари резултати в по-широкия контекст на съвременните идеи.

Нека нашата задача е да научи компютър, за да играят на интелектуална игра - "кръстчета и нули" на 3 × 3. Как бихте се реши този проблем?

Първото желание е да се уточни изрично, което се движи, за да направите компютъра. И двете начинаещи обикновено продължават по този начин, тъй като изглежда най-лесно и контролирани. Нека компютърът играе кръстовете. След това можете да изрично да се посочи, че първата крачка е направена в центъра на терена. На следващо място, обаче, отговор на компютъра трябва да зависи от своя страна на играча.

Означаваме квадратите на борда на "шахматна дъска" стил: от А1 до С3. Тогава тази игра алгоритъм (с помощта на C ++ синтаксис) ще изглежда

Този алгоритъм е подобна на системата, просто рефлекс. Но къде се движи, записани в нашата програма? За да сте сигурни, че определен курс на нашите резултати, за да спечели, трябва да се покажат всички възможни ходове на врага. Това може да се представи като дърво на игри, известен също като дървото на опции за не-игрови задачи. Следващата фигура показва пример фрагмент дърво за игра "кръстчета и нули" в поле 3 × 3. Коренът на това дърво е празна дъска, и клонове, заминаващи от тях съответстват на възможните ударите на първия играч. Тези отрасли са в новото състояние на света на играта, от всяка от които също са с изглед към клоните, съответстващи на допустимите ходове на втория играч, и така нататък. В случай на не-игрови задачи в корена на дървото на опции може да бъде, например, реши уравнението, а клоните му ще бъдат съвместими с позволените операции за превръщането на този израз.

В действителност, такова дърво описва пространството на състоянието - набор от условия, които могат да бъдат някои от тях, като например в света на игрите с възможните преходи между държави. За някои проблеми, това пространство може да бъде определена като изрично са изброени всички възможни състоянията и преходите между тях, но по-често се дава безусловно - под формата на правила (игри, интеграция и др ...). Въз основа на правилата може да се организира процедура генеративен изрично изграждане на дърво от опции.

Ние използваме тази процедура, за да се изгради една игра, дърво, и да намерят в него отговаря, че би довело

към победата, или, ако не е възможно, за да наравно. Тях ние се вписват в нашата програма. Възможно ли е компютърна програма, която играе в "тик-так-палеца", тя построен дървото на възможности въз основа на известни процедурата по генериране? Естествено, по-елегантен (от показания по-горе) и алгоритъмът ще трябва да притежавате игра за изграждане на дървото и да изберете най-добрия курс, както и ние.

За да се извърши това строителство без съхраняване в паметта на допълнително копие на игралното поле (както в по-общия случай - моделът на света) е проблематично. Да предположим, че област [3] [3] - спомагателен масив от 3 х 3, стойността на който клетката е настроен на "-" ако съответната клетка не е заета, и "X" и "О", ако има "напречно" и "пръст" съответно. След процедурата по генериране може да се запише в следния вид:

Ако предварително определени всички стойности на поле решетка, както на празни ( "-"), и след това да изпълните тази процедура tree_ търсене ( "Х"), в хода на своята работа в масив от област ще се превърне всички възможни комбинации на нулите за местоположение и кръстове.

Нека да има check_game процедура, която прави оценка на положението на борда, връщане на "X" или "Информация", ако 3 на ред, било представено на съответния играч "-", ако това не е така. ние можем променил статуса си, за да ни листа дърво (някой да спечели или да рисувате).

А сега да разгледаме дърво възли, непосредствено преди листата. Ако поне един от листата води до печеливши играчи, по време на което съответства на текущия възел, а след това на възел също е победител. Възелът ще се губи, само ако всички листа, в която той води, са като изгубени. По този начин, можете да маркирате всички възли, които предшестват листата, и да продължи да се разпространява тази информация до корена.

Тя е по-удобно да се представят печалбата компютър като "1" изготвя "0", и загубата на компютъра като "-1". След това, за да се определи мястото за състоянието на компютъра, разбира се, ще трябва да се вземе максимума, както и за напредъка на врага - най-малко във всички възли на детето. Тази процедура възли оценки за състоянието, показани на следващата фигура, се нарича Минимакс процедура. Вграждане на процедурата за генериране на процедура Минимакс не е трудно.

Трябва да се отбележи наличието на теорията на игрите, толкова по-общото понятие - Наш равновесие, съответстващо на тези стратегии на играчи, от които нито един от тях не е изгодно да се отклонява, ако тя не прави на другите играчи.

Ако процедурата по генериране е известен и като се използва процедурата по Минимакс за да се определи най-добрият курс, какъв е проблемът? Както вече многократно отбелязано по-горе, проблемът - в NP-пълнотата. С други думи, пълната версия на дървото може да получи много голям: често броят на възли нараства експоненциално с дълбочината на дървото, тъй като всеки възел води до редица нови единици, всяка от които, от своя страна, отново води до редица нови единици. Така например, размерът на дървото на парчета е 10 ^ 40, за шах - 10 ^ 120, и за първи и доста невъобразим брой - 10 ^ 400. По ирония на съдбата, често е да се подчертае, че степента на тези числа се каже за основния им превъзходство на броя на атоми или елементарни частици във Вселената, не е напълно оправдано чрез сравняване на броя на обектите, а броят на комбинациите от състояния на обектите. Все пак, това сравнение става оправдано, когато става въпрос за класически системи с масов паралелизъм: дори ако всеки атом във Вселената ще бъде отделен процесор, свирене 10,100 комбинации в секунда, на цялата вселена за всички времена, изтекло от Големия взрив, не е достатъчно, за да да играе перфектен мач от втория.

опции дървесни видове, посочени имплицитно чрез правилата на играта, е един вид невидима за програмата. Тъй като плъх да проучи реалната лабиринта, ще трябва да прекарат известно време в проучване на всяка вилица, последвано от продължаване на пътя не се вижда, и програмата трябва да прекарат известно време (изчислителни ресурси), за да проучат възможности за дървото и да намерят пътя към победата.

Въпреки очевидната елементарни играта "Тик-так-Toe" дори на 3 х 3 за едно дете, което не е запознат с това, изисква значителни умствени усилия. Тази игра изисква търсене на варианти на дълбочина 4-5, което е близо до сложността на намирането на центъра на задачите на сегментите с помощта на владетел и компас. Въпреки това, "мислене", след като "тик-так-палеца" на 3 х 3, ние ще знаем решението (на пътя в опцията "лабиринт"), и играта ще загуби интерес. За "възрастни" интелектуални игри такива ограничения не е особен, защото цялото място за търсене в тях не може да се разглежда през целия живот на човек и дори по време на целия период на съществуване на цивилизацията.

Какво можете да направите, ако цялото дърво се генерира не може да бъде? Какви са причините за избор на курс? Евристичното програмиране, областта терминът "евристични методи" е определен като устройство, което ви позволява да се намалят в опциите за сортиране необещаващо клонове на дървото, така че е много по-конкретно определение от двете евристични техники, улесняващи решаването на проблема.

А евристичен вече имплицитно, използван при изготвянето на дървото игра за "Морски шах". Тя показва всички начални позиции на играта, а не едно в друго чрез въртене и огледало. С други думи, на евристики използват симетрия. Колко версии на играта, ако не се вземат предвид симетрията? Техният брой - не повече от факториела на броя 9. Използването на симетрии този брой е намален със заповед. Въпреки това, относителната печалба за големи области е много по-малък, тъй като вече след няколко удара симетрична продължаване престанат да съществуват.

Симетрията е много общ евристични методи, но не и прекалено силни, защото симетрията на ситуацията на игра (дори и ако има такъв) е много къса скоро.

Човек може да си представите по-сложно (и частни) евристичен: колкото по-печеливш ход, който потенциално може да се използва в по-голям брой конструкции на три поредни. На този основен евристични методи за "кръст" е най-печелившата ход към центъра, тъй като тя може да участва в четири различни конструкции. След това има пасажи в ъглите - за тях, броят на конструкции е три. За премества от стените на този номер само две. Ясно е, че това не е достатъчно, тъй като евристичен игнорира възможностите на врага (например, завърши своята комбинация).

Това е естественото желание да се направи оценка на рентабилността на напредъка количествено. Въз основа на такова количествено определяне могат да се режат на порциите клонове във всеки възел на дървото за това. И, наистина, в заданието на евристични евристични методи за програмиране под формата на (статично) функция се оценява най-често срещаните.