-> Задачу желательно решить как можно быстрее на turbo prolog 2.0, лучше в виде dll на visual prolog 5.2.

Это обобщение знаменитой игры «15». Имеется поле размером NxN клеток, на котором расположено N^2-1 пронумерованных фишек. Требуется выстроить фишки в определенном порядке.

Как понятно полный перебор не идет! Для классических пятнашек у нас просто не хватит памяти.

Важный метод сокращения перебора - использование оценочных "эвристических" функций, позволяющих грубо оценить, насколько "хорошим" (или "плохим") является текущее состояние. Пример, шахмты, Го.

При наличии "идеальной" оценочной функции необходимость в переборе отпадает - мы просто выбираем из всех соседних вершин оптимальную.

Далеее приводятся примерный ход решения на swi-prolog.

1) С использованием "эвристической" функции:


Встроенный предикат checklist(Pred,List) применяет предикат ко всем элементам списка. Обычное его назначение - проверить, что все элементы удовлетворяют некоторому условию. Но в нашем случае мы не проверяем, а устанавливаем этот факт, присваивая значения оценки с помощью предиката hvalue.


Предикат join определяет последовательность обработки вершин. Определив его соответствующим образом, получим эвристический поиск в глубину, 

или в ширину

Встроенная процедура merge выполняет слияние упорядоченных списков и является составной частью сортировки слиянием. Таким образом, это просто более эффективный способ выполнить

Эти два метода известны под названиями "восхождение на гору" (hill climbing), и "сначала-лучший" (best-first search).

Данное решение достаточно быстрое, но решение получается далекое от оптимального.

2) Алгоритм A* 

Чтобы получить наилучшее решение, мы должны не просто выбирать самое многообещающее продолжение, но учитывать и уже пройденный путь. Удобнее это делать, если есть некоторая простая связь между оценочной функцией и длиной пути. Но наша функция как раз имеет такую связь. Она дает оценку длины пути от данного состояния к целевому. Причем эта оценка всегда занижена. А это означает, что мы можем изменить критерий упорядочивания вершин и выбирать ту из них, для которой сумма длины уже пройденного пути и оценки пути, который предстоит пройти, минимальна. Все, что нам осталось сделать - изменить процедуру оценки.



Новая версия программы находит действительно оптимальное решение за приемлемое время (за несколько минут). В литературе по искусственному интеллекту этот метод носит имя "Алгоритм A*". Иногда используют "взвешенный A*", когда какой либо составляющей придают больший вес.



В крайнем случае, когда Wh = 0 мы получим более громоздкую реализацию поиска в ширину. В другом крайнем случае, когда Wp = 0, получаем поиск "сначала лучший". Идея состоит в том, чтобы пожертвовать оптимальностью решения ради скорости.

3) Наличие оценочной функции позволяет организовать более интеллектуальное отсечение при поиске с ограничением на глубину. Мы можем отсекать ветви несколько раньше, как только оценка длины пути вместе с длиной уже пройденного пути превзойдет заданное ограничение. Поскольку эвристическая функция не переоценивает длину предстоящего пути, мы можем быть уверены, что отсекаемые ветви будут заведомо длиннее. Комбинируя эту идею с методом итерационного углубления, получим популярный "алгоритм IDA*" (Iterative Deepening A*). В отличие от DFID, ограничение на глубину при переходе к следующей итерации можно увеличивать большими шагами. Новое ограничение можно смело установить равным минимальной оценке всех отброшенных на предыдущей итерации вершин. Эту оценку мы будем передавать вместо флага.

 Вот примерноый ход решение на swi-prolog с использованием Алгоритм IDA* и оценочной "эвристической" функции:



где h, например, "эвристическая" функция - "манхэттенское" расстояние (|XX0|+|YY0|) от каждой фишки до ее законного места:



***3) Третье решение самое предпочтительное.***

M Guedda

Не забываем выделять код!

Это сообщение отредактировал(а) Guedda - 1.2.2007, 10:39

Кстати последня эвристическая функция дана для случая n=3.

Мда, видно придется решать самому, как обычно, за пару дней. Только вот бы еще их выделить 

Я, конечно, все понимаю - все заняты. Но может хоть кто-то знает ссылки, у кого-то есть исходники (можно игры в 8, лучше конечно 15). Просто очень критичная ситуация.
Я представляю логику, но нет не времени, не сил разбираться в Prolog, особенно VP (а в других средах и языках написать техническое задание не позволяет, я бы конечно с радостью лучше написал в c++ или на java).

Буду всем плагодарен, кто хоть чем-то поделится.

Хорошие поступки остаются в истории )

В книге братко есть описание процедур для головоломки "игра в восемь", предназначенные для использования программой поиска с предпочтением (которая приведена ниже) (Вот это бы все это переделать для пятнашек и на VP 5.2 или 6.3 в виде DLL):



Программа поиска с предпочтением:



Кто хоть чем-то поделится, буду очень благодарен.

Если у кого что-есть можете скидывать на:

[email protected]

Добавлено @ 08:46 
Взаранее всем спасибо!

Пятнашки были решены на Проложьем форуме года три назад. Зайдите на progz и поищите.

На да, там что-то есть. Но что-то не очень понятно на чем писалось, да и реализация далека от совершенства 
Мда...