Задача 2 от брой 11/2005 - ПОДАРЪК - Анализ

Ивелина Захариева

В програмата са използвани два алгоритъма, работещи последователно.

Първият алгоритъм реализира тривиалния, "човешки", начин на мислене: най-напред се нарежда първият ред (числата от 1 до 5). Започва се от числото 1, като се използват предварително дефинирани ходове за преместването му в различни посоки (нагоре, надолу, по диагонал и т.н.). Тръгва се от начална позиция, в която празното поле е отдясно на числото, която ще се мести. За последните две числа (4 и 5) е нужен друг алгоритъм: първо се поставя числото 4 в края на реда, след това числото 5 под него и с предварително дефинирана последователност от ходове двете числа се нареждат на местата им.

След първия ред се подрежда първият стълб (числата 6, 11, 16 и 22), като се използва същият алгоритъм, само че всички ходове са "транспонирани". С това задачата се свежда от поле с размер 5 × 5 елемента до поле с размер 4 × 4 елемента. За него се повтарят същите действия, при което полето намалява до 3 × 3 и накрая до 2 × 2 елемента. За нареждането на последните елементи (числата 19, 20 и 24) са описани необходимите ходове в зависимост от изходната конфигурация (12 възможни състояния).

Този алгоритъм работи бързо (за по-малко от 1s) и успешно за всички решими начални състояния. Намереното решение обаче, макар и логично и разбираемо, е дълго – средно 280-300 хода. То се пуска в началото на програмата за да гарантира успешно решение. На практика в нито един от използваните тестове крайното решение не е резултат от работата на този алгоритъм.

Вторият алгоритъм реализира т. нар. Iterative deepening A* процедура за търсене на оптималното решение. Празното квадратче в условието се мести във всички възможни посоки (максимум 4, ако то не е в края на полето). От всяка от получените комбинации се получават всички възможни нови комбинации при местенето на празното квадратче с един ход. При това за всяка от комбинациите се запомня пътят, по който е получена и се оценява доколко тя е далеч от решението. За критерии се използва Манхатъновото разстояние, т. е. сумата от абсолютните стойности на разликите между текущите и крайните координати за всяко число. Ако в някоя от получените комбинации Манхатъновото разстояние стане равно на 0, то това е решение на задачата и пътят, по който е намерено, се записва в изходния файл.

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

В този алгоритъм са въведени две оптимизации. Едната от тях е свързана с проверка на това дали някоя от получените комбинации вече не е разглеждана на същия или някой от предишните ходове. Ако това е така то тя се пренебрегва. Това е важно, защото от две еднакви комбинации се получават също еднакви дъщерни комбинации. В крайна сметка първите 5000, имащи най-малко Манхатъново разстояние ще са всъщност само няколко различни комбинации с голям  брой техни копия. За тази проверка се създава хеш-таблица, подобно на използваната от Веселин Георгиев за първа задача от тази година.

Втората оптимизация е свързана с използването на Манхатъновото разстояние. При него не се отчитат случаите, в които две числа, например 1 и 2 се намират на реда (или стълба), на който трябва да бъдат, но са с разменени позиции: например 2, 1. Манхатъновото разстояние за тези числа може да е само 2 (като минимален брой ходове за да си разменят местата), но всъщност не е възможно разместването им да стане само с два хода. В най-добрия случай са необходими още два допълнителни хода: едното от числата трябва да мине на втория ред, "да заобиколи" първото и след това да се върне на реда си. В програмата за отчитане на отдалечеността на дадена комбинация от крайното решение е използвана сумата от Манхатъновото разстояние и броя на числата, участващи в такива разменени двойки (ако ги има).

Автор: Ивелина Захариева

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.