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

Радослав Герганов

Задачата за намиране на най-кратко решение на поставеният проблем е NP трудна.

Един от известните начини за подреждане на пъзела е с използване на евристични алгоритми. Можем да използваме следната евристика – намираме сумата от Manhattan разстоянията за всяка плочка, която не си е на мястото до мястото и в наредената конфигурация. Manhattan разстояние дефинираме така:

|x1-x2| + |y1-y2|, където (x1,y1) и (x2,y2) са съответно координатите на плочката в "разбърканата" и в наредената конфигурация.

Лесно се вижда, че тази оценка никога не надвишава броят ходове, които са необходими, за да се подреди пъзела. Следователно, ако използваме алгоритъма A* с тази евристика ще намираме винаги оптимални решения, т.е. с минимален брой ходове. Проблемът, който възниква е, че времевата сложност на А* е пропорционална на генерираните състояния, които растат експоненциално заедно с броя ходове, необходими за оптималното решение. Това ни навежда на мисълта да направим компромис с оптималността на решението и да търсим неоптимални решения, които могат да се намерят за даденото времево ограничение. В моето решение използвам едно обобщение на алгоритъма А*, с което се постига точно такъв компромис. Алгоритъмът се нарича Weighted A* и използва следната функция за оценка, за дадено състояние n:

f(n) = g(n) + W * h(n), където:

g(n) = броят ходове, направени за достигане на състоянието

h(n) = евристичната оценка дадена по-горе

W >= 1 коефициент (цяло число)

Когато W=1 получаваме стандартният алгоритъм А*. Ако W > 1 функцията за оценка f може да надхвърля минималният брой ходове водещи до решение и следователно намерените по този начин решения ще са неоптимални. Идеята на коефициентът W е да се даде по-голяма тежест на евристичната оценка h, отколкото на g. Това води до намиране на решения с по-малко на брой генерирани състояния, с цената на по-дълго решение. Може да се докаже, че броят ходове на така намереното решение няма да надхвърля с повече от W пъти броят на ходовете в оптималното решение.

В моето решение пускам няколко пъти Weighted A* със стойности на W съответно 10, 5, 4, 3, 2, 1 и при достигане на времевото ограничение записвам последното намерено решение в изходният файл.

Автор: Радослав Герганов

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

Supported by Musala Soft Ltd.

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