Практика программирования (Бейсик, Си, Паскаль)



Дерево решений


В начале XX в. многие американские фермеры увлекались игрой в "15", за решение которой предлагался весьма солидный приз. На квадратном поле размером 4x4 размещались 15 фишек с числовыми номерами 1, 2, ..., 15.

Наличие одного свободного поля позволяло передвигать фишки по горизонтали и вертикали с целью их сортировки по возрастанию номеров. Позиция, за которую предлагалось вознаграждение в размере $100000, содержала единственное нарушение порядка — фишки с номерами 14 и 15 были переставлены местами. Позднее было доказано, что из этой позиции невозможно перейти к полностью упорядоченной последовательности фишек. Так что призовой комитет ничем не рисковал.

Более того, оказалось, что все позиции фишек делятся на две категории. Если суммарное количество нарушений порядка в исходной позиции было четным, то полная сортировка фишек возможна. И тогда единственный смысл игры (исключая простое времяпрепровождение) заключался в достижении полностью упорядоченной расстановки за минимальное количество ходов. Для определенности под ходом мы будем подразумевать перемещение одной фишки на свободное место (в реальной игре прибегают к одновременному сдвигу двух или трех фишек, расположенных в одной строке или одном столбце).

С целью сокращения количества переборов мы продемонстрируем аналогичную игру на поле размером 2x3, где расположены фишки с буквами А, В, С, I, S. Цель игры — за минимальное число ходов перевести заданную исходную позицию в позицию BASIC:


Идея решения этой задачи заключается в построении полного дерева решений, в верхушке которого располагается целевая позиция BASIC. Каждый последующий уровень дерева образуют позиции, полученные из предыдущей вершины за один ход. С целью удобства ввода начальной позиции и последующего отображения ходов пустая клетка у нас будет представлена символом "*".

В нашей игре начало дерева может выглядеть следующим образом:


Естественно, что в очередной вершине дерева должна находиться позиция, не повторяющая предыдущие позиции. Так как общее количество перестановок из шести элементов равно 6!=720, то общее количество вершин в нашем дереве не будет превосходить эту границу. Более того, задача симметрична и из целевой позиции BASIC* можно будет породить ровно 359 новых вершин.




Содержание  Назад  Вперед