турне Softcraft рицарски

От тук можете да изтеглите цялата статия в PDF формат (215 KB)
Следователно - програма, използвана в експериментите (5 KB)

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

Решение на любопитен въпрос,
който изглежда не е обект на
никое научно изследване.
Ойлер

За един от най-интересните секции включват програмни задачи от областта на изкуствения интелект, в който решението е намерен от "проба и грешка" [1,2]. В този случай, има бюст в намирането на решения, продължителността на който може да бъде намалена чрез използването на различни евристики - методи за оптимизация.

Клас на алгоритми, която позволява да се реши тези проблеми, по английска литература, наречена "връщане назад алгоритми" ( "алгоритми с връщане"). Тези алгоритми се използват в случаите, когато не повече подходящи "насочени" методи [3].

Ние разглеждаме един от най-важните проблеми в този клас - обиколка рицарски [3-5]. Това е да се намери отклонение от размера на борда М Н коня движещия се по правилата на шахмата. Ако съществува байпас, всяко поле се посещава само веднъж (извършва N * M-1 стъпки). Нека да анализираме техники за оптимизация, и опознаването на работата на един повтарящ се, рекурсивни автомат и програми.

методи за оптимизация

Обмислете следните техники за оптимизация:

определяне на клетка, която е невъзможно байпас (оптимизация 1);
идентифициране на заключени клетки (оптимизация 2);
правила Varnsdorf приложения (оптимизация 3);
използване на различни масиви конски ходове (оптимизация 4).

1. Определяне на клетки заобикаляйки на което не може да бъде

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

Това условие се проверява чрез следната функция:

Въпреки това, това правило не обхваща всички клетки за които няма байпас. По този начин, в продължение на 3 * 7 дъски, в допълнение към тези клетки, за които даден правило също невъзможно байпас на клетки (2,4).

2. Идентификация на заключени клетки

Ако по време на следващата клетка се формира, което може да се въведе, но там, където не може да излезе, а след това подобен ход не е позволено, с изключение на предпоследния кръг. Този метод за оптимизация може значително да се намали броят на данни, включително, когато се използва във връзка с правило Varnsdorf.

Развитието на този метод е да се определят групи блокирани клетки, свързани един с друг, но откъснати от останалата част на дъската. В разглежданите приложения определени групи от две блокирани клетки, което значително намалява броя на връща за малки дъски, и когато се използва във връзка с правило Varnsdorf - и за по-голям (например, размер 100 х 100 клетки).

3. Прилагане на правилата на Varnsdorf

Сред многото евристичен методи [5], използвани за търсене правило намаляване Varnsdorf е най-просто. В съответствие с коня при обхождането на табла трябва да бъдат всеки път да се сложи на терена, от което той може да направи най-малък брой на ударите на областта все още не е изтекъл. Ако има няколко области, можете да изберете някоя от тях, което обаче може да се направи кон в застой, и да поиска връщане на [5]. Имайте предвид, че най-доброто правило Varnsdorf работи за ъгловите полета.

4. Използването на различни масиви конски ходове

конни ходове могат да бъдат определени, например, като следващата масива:

Всеки елемент определя един възможен курс кон и се състои от промяна на координатите му на борда, когато постигането на напредък. Чрез използване на различни масиви за движенията на коня върне брой може да варира. Програмата използва пет евристично избрани масиви, съдържащи възможните кон се движи в различна последователност. Също така се посочи максималният брой на възвръщаемост (GOOD_RET), и когато тя е достигната, търсене път започва отново с помощта на друг масив. При търсене на байпас с последния набор е ограничен до броя на възвръщаемост MAX_RET. Ако споделянето на всички предложени методи за оптимизация, GOOD_RET като стойност на един, а след това дъските в близост до площада, може да се изгради кръга без нито една замяна на всички клетки, от които има отклонение. Байпас без връщане на всяка от клетките не могат да получат "продълговати" дъски (например, 14 х 3) и за големи плоскости, като дъски 100 х 100 клетки.

повтарящ софтуер

изчерпателно търсене

Идеята на един повтарящ се алгоритъм за програмата е, както следва:

при всяка стъпка фрагмент търси пътеки, започващи от текущата клетка или включва вече завършена;
когато постигането на напредък от масива на възможните ходове следващия елемент се изтегля, което води до незаета клетка намира на борда;
Ако разбира се, не е възможно, тогава има връщане към предишната клетка (премахване на пътуване);
пътя за търсене се счита за успешно, когато броят на настоящия напредък ще бъде равен на броя на клетките на дъската. Ако клетки от първичния чрез всички възможни ходове, пътят не съществува.

По-долу е структурата на функцията, която изпълнява за:

Брой използва за инсулт всяко изпълнение на ударите се съхранява в масива, размерът на която се избира в зависимост от размера на дъската.

Описаните алгоритъм се изпълнява за опциите и да се намери решение, ако има такова. Не решение води до пълно изброяване на всички възможности.

За да илюстрираме възвръщаемостта изпълнение в таблицата. 1 показва прекосява протокол размер борда на 3 до 4 клетки с координати (2,4). В края на протокола показва получената пътя на прекосява.

Таблица 1. Протокол размер прекосява борда 3 в 4 на клетката (2,4)

За класически размер шахматна дъска 8 от 8 със следните резултати:

за оптимизации 1 и 2, в повечето клетки над максималния брой на връщане (MAX_RET). Минималният брой на възвръщаемост в клетката (5,5) - 2502;
оптимизации за 1 и 3 във всички клетки, с изключение на (4,1) и (6,4), се връща на нула. В тези клетки, 9 и 79 се връща, съответно;
За да се оптимизира 1-3 в връщането клетки (6,4) Три. Останалите клетки се връща на нула;
1-4 оптимизации за всички клетки се връща на нула. Така в клетката (6,4) от втория масив от възможни движения се използва.

За плоскости с размери 9 от 9 до клетки от които има байпас, се постига без връщане обратно към оптимизации 1-3 (1-4, разбира се, също).

За размера на борда на 50 до 50 със следните резултати:

1-3 за оптимизация в повечето клетки, липса на и броя на данни при останалата част от клетките варира от единица за стойности над граничната стойност;
1-4 оптимизации за всички клетки се връща на нула.

За размера на борда на 77-77, за клетките, от които заобикалят там са получени следните резултати:

1-3 за оптимизация в повечето клетки, липса на и броя на данни при останалата част от клетките варира от единица за стойности над граничната стойност;
1-4 оптимизации за всички клетки се връща на нула.

За размера на дъската 100 до 100 със следните резултати:

1-3 за оптимизация в повечето клетки, липса на и броя на данни при останалата част от клетките варира от единица за стойности над граничната стойност;
1-4 оптимизации за всички клетки, с изключение на клетки (94.24) и (94,79), връща нула.

Както е отбелязано по-горе, се считат оптимизационни методи за не-квадратни плоскости не са толкова ефективни. Получените за размера на борда на 14-3 Резултатите са показани в таблица. 4.

Таблица 4. Резултатите за програмния съвет 14 3

рекурсивни програма

Най-добре известно решение за заобикаляне на проблема с кон - рекурсивен [2]. повтаря, функциите, структурата има следния вид:

В тази програма могат да се използват всички видове оптимизации, както е описано по-горе.

Free-рязане програма

Ако първите две програми за справяне с този проблем са доста традиционни [2], клоунът за тези, които не са от значение.

Имайте предвид, че програмата за автомати могат да бъдат официално конструирана, както е описано по-горе итеративна програма с използване на метода, описан в [7]. Свободна рязане програма може да бъде конструирана и официално даден рекурсивен програма използва предложен в [8] метод.

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

Фиг. 1. Схема на връзките на машината за турне рицар

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

Фиг. 2. Преход графика машина за турне рицар

Опростена текст функция, която изпълнява тази машина, е както следва:

заключение

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

Този труд е финансиран от Фондация Българска за фундаментални изследвания при отпускане на безвъзмездна помощ №02-07-90114 "Развитие на автомати технология за програмиране".

литература

Н. Вирт Алгоритми + структури от данни = програми. Mir: Мир, 1985.

М. Gardner Математически роман. Мир, 1974.

Онази Е. шах и математика. М. Наука, 1983.

Shamgunov Никита Nazimovich - трикратен шампион на Урал Програмиране, двукратен световен шампионат финалист за ACM програмиране, завършил студент SPbGITMO (ТУ) на.