Алгоритми за обратно проследяване

Особено интригуваща област на програмирането са така нареченитепроблеми с изкуствения интелект.Тук имаме работа с алгоритми, които търсят решение не според дадени правила за изчисление, а чрезпроба и грешка.Обикновено процесът на проба и грешка е разделен на отделни задачи (техника „Разделяй и владей” ). Често тези проблеми са най-естествено изразени чрез рекурсия и изискват изследване на краен брой подпроблеми. Като цяло, целият процес може да се формализира като процес на търсене, който изгражда (и изрязва) дърво от подзадачи. При много проблеми такова дърво на търсене расте много бързо, растежът зависи от параметрите на проблема и често е експоненциален. Съответно цената на търсенето също се увеличава. Понякога, използвайки някои евристики, дървото за търсене може да бъде намалено и по този начин да се намалят изчислителните разходи до разумни граници.

Въз основа на принципа, че задачата на изкуствения интелект е разделена на подзадачи, ще демонстрираме използването на рекурсия в този случай. Нека започнем с демонстриране на основните методи, използвайки добре познат пример -проблемът с хода на коня.

Дадена е дъска с размерn´n, т.е. съдържащn2 полета. Първо, на полето се поставя кон с координатиx0,y0 — фигура, която се движи според обичайните шахматни правила. Задачата е да се намери последователност от ходове (ако съществува), в която конят посещава всички полета на дъската точно веднъж (заобикаля дъската), т.е. трябва да изчислитеn2 - 1 хода.

Очевиден начин за опростяване на задачата за заобикаляне наn2 полета е решаването на по-проста, а именно или извършване на следващото движение, или доказване, че не е възможно движение. Затова нека започнем с определяне на алгоритъма за извършване на следващия ход. Първата версия изглежда така:

НАЧАЛОинициализиране на избор на ход;

REPEATизбор на следващия кандидат от списъка с ходове;

АКОпасваТОГАВА

АКОдъската е празнаТОГАВА

АКОнеуспехТОГАВАунищожаване на предишен ход

ДОуспехИЛИбез повече кандидати

За по-подробно описание на алгоритъма трябва да изберете някакво представяне на данните. Платката, най-просто, може да бъде представена като матрица, нека я наречем h. Освен това въвеждаме тип за индексиране на стойности:

TYPE индекс = ARRAY [1..n, 1..n] OF INTEGER; (25)

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

Сега трябва да изберете подходящите опции. Те трябва да определят началните условия за следващия ход и резултата (ако ходът е направен). В първия случай е достатъчно да посочите координатите на полето (x,y), откъдето следва хода, и числотоi, указващо номера на хода (за фиксиране). Резултатът изисква булев параметър; ако е "вярно", значи преместването е било възможно.

Освен това условиетодъската е празнаможе да бъде пренаписано катоi2 . Ако въведем още две локални променливиuиvза възможен ход, определен в съответствие с правилата на „скока“ на коня, тогава предикатътfitsможе да бъде представен като логическа връзка на условията, че новото поле е в рамките на дъската (1 £u£nи 1 £v£n) и все още не е посетен (huv=0). Коригирането на валиден ход се извършва с присвояванетоhuv:=i, а отмяната сhuv:= 0. Ако въведете локална променливаq1 иизползвайте го като резултатен параметър в рекурсивни извиквания на този алгоритъм, тогаваq1 може да бъде заменено суспех.В съответствие с това получаваме следната процедура:

PROCEDURE Try(i: INTEGER; x, y: index; VAR q: BOOLEAN);

VAR u, v: ЦЯЛО ЧИСЛО; q1: БОЛЕВ;

НАЧАЛОиницииране на избор на ход;(27)

REPEAT- координати на следващия ход,

определено от правилата на шаха;

ELSE WriteLn('няма път');

Не трябва да се пренебрегва и още един детайл. Променливатаhuvсъществува само ако иu, иvлежат в диапазона на индекса 1…n. Следователно изразът в (27), заместен с, съвпада сот (24), има смисъл само ако първите му четири компонента са верни. Ето защо е важно компонентътhuv= 0 да е последният. В табл. Таблица 1 дава решения за три начални позиции: и заn= 5 и заn= 6.

Таблица 1. Три възможни хода на коня

проследяване

Характерно свойство на такива алгоритми (алгоритми с обратно проследяване) е, че те предприемат стъпки към общо решение, но всички те са фиксирани (записани) по такъв начин, че по-късно човек може да се върне назад, като по този начин отхвърля стъпки, които водят до задънена улица, а не до общо решение. Този процес се наричаbacktrackingилиrollback(backtracking). Ако приемем, че броят на потенциалните стъпки е краен, тогава от алгоритъм (24) можем да изведем универсална схема:

НАЧАЛОиницииране на избор на кандидат;

REPEATизбор на следващия кандидат;

АКОпасваТОГАВА ЗАПОЧНЕТЕвписването му;

АКОрешението е непълноТОГАВА ЗАПОЧНЕТЕ Опитайте; (28)

IFотказTHEN BEGINизтриване на записEND

ДОуспехИЛИняма повече кандидати

В реални програми може да има други опции, получени от схема (28). Често, например, има конструкция с явен параметър за нивото, когато е посочена дълбочината на рекурсия. Това води до прости условия за прекратяване. Освен това, ако на всяка стъпка броят на пътищата, които трябва да бъдат изследвани, е фиксиран (нека бъде равен наm), тогава може да се приложи още една производна схема (тя трябва да бъде достъпна с помощта на оператора Try(1):

PROCUDURE Try(i : INTEGER);

REPEAT k := k+1;избор на k-тия кандидат;

АКОпасваТОГАВА ЗАПОЧНЕТЕвписването му;