Игра в пятнадцать

1.

Игра в пятнадцать
Задача 1.17. «Игра в восемь
фишек»
Аверич Владимир
5132701/20001

2.

Что такое игра в пятнадцать?
их ещё называют «Пятнашками»
Пятнашки - игра из жанра
комбинаторных.
В
ней
игроку дается поле 4 на 4,
на котором расположены 15
квадратиков с числами от 1
до 15 и еще один пустой
слот.
Задача
игрока
сдвигать
квадратики
с
числами на этот пустой слот
до тех пор, пока числа не
окажутся выстроенными в
нужном порядке.

3.

Манхэттенское расстояние
Манхеттенское
расстояние
(Расстояние
городских кварталов) —
, введённая
.
Согласно этой метрике,
между двумя точками
равно сумме модулей разностей их координат.
метрика
Германом Минковским
расстояние
Сумма
манхэттенских
расстояний
между
костяшками и позициями, в которых они находятся
в
решённой
головоломке
«Пятнашки»,
используется в качестве эвристической функции
для поиска оптимального решения
Манхэттенское—Расстояние между двумя точками,
измеренное вдоль осей, расположенных под
прямым углом друг к другу (городские кварталы);
рассчитывается
суммированием
абсолютных
разностей между координатами х и у.
Таким образом в метрике городских кварталов
длины красной, жёлтой и синей линий равны
между собой (12). В геометрии Евклида зелёная
линия имеет длину 6√2 ≈ 8,49 и представляет
собой единственный кратчайший путь.

4.

Эвристика. Что это?
Эвристика - это оценка расстояния
от данного состояния к целевому.
Если
эвристика
совпадает
с
истинным значением, то поиск
идёт
сразу
в
оптимальном
направлении, раскрывая только
состояния на кратчайшем пути и
непосредственных к нему соседях.
Когда
эвристика
занижена
(меньше истинного расстояния),
начинает преобладать поиск в
ширину и алгоритм раскрывает
большое число узлов. При этом
гарантируется
(если
хватит
времени и памяти) нахождение
оптимального решения. Наконец,
если эвристика завышена (больше
истинного
расстояния),
поиск
может ускорится, но решение не
обязательно будет оптимальным
(найден будет не кратчайший
путь).

5.

Алгоритм решения
Эвристика
Алгоритмическое решение здесь сложно
тем,
что
каждое
действие
игрока
изменяет игровое поле. Поэтому обычно
задачу решают с помощью алгоритмов
поиска пути (чаще всего это вариации
вокруг A*), где программа "путешествует"
по веткам изменений состояния поля. При
этом на каждом шаге из нескольких
вариантов мы выбираем тот, в котором
наша
оценка
"ошибки"
минимальна.
Ошибка
вычисляется
при
помощи
эвристик, из которых самая популярная манхэттенское расстояние.
Поиск в
ширину
Алгоритм
Дейкстры
Алгоритм
А*

6.

Алгоритм A*(A star)
Этот алгоритм был впервые
описан в 1968 году Питером
Хартом, Нильсом Нильсоном и
Бертрамом
Рафаэлем.
При
рассмотрении
каждой
отдельной вершины переход
делается
в
ту
соседнюю
вершину, предположительный
путь из которой до искомой
вершины самый короткий.

7.

Спасибо за внимание