Практика программирования (Бейсик, Си, Паскаль)
Дерево решений
В начале XX в. многие американские фермеры увлекались игрой в "15", за решение которой предлагался весьма солидный приз. На квадратном поле размером 4x4 размещались 15 фишек с числовыми номерами 1, 2, ..., 15.
Наличие одного свободного поля позволяло передвигать фишки по горизонтали и вертикали с целью их сортировки по возрастанию номеров. Позиция, за которую предлагалось вознаграждение в размере $100000, содержала единственное нарушение порядка — фишки с номерами 14 и 15 были переставлены местами. Позднее было доказано, что из этой позиции невозможно перейти к полностью упорядоченной последовательности фишек. Так что призовой комитет ничем не рисковал.
Более того, оказалось, что все позиции фишек делятся на две категории. Если суммарное количество нарушений порядка в исходной позиции было четным, то полная сортировка фишек возможна. И тогда единственный смысл игры (исключая простое времяпрепровождение) заключался в достижении полностью упорядоченной расстановки за минимальное количество ходов. Для определенности под ходом мы будем подразумевать перемещение одной фишки на свободное место (в реальной игре прибегают к одновременному сдвигу двух или трех фишек, расположенных в одной строке или одном столбце).
С целью сокращения количества переборов мы продемонстрируем аналогичную игру на поле размером 2x3, где расположены фишки с буквами А, В, С, I, S. Цель игры — за минимальное число ходов перевести заданную исходную позицию в позицию BASIC:
Идея решения этой задачи заключается в построении полного дерева решений, в верхушке которого располагается целевая позиция BASIC. Каждый последующий уровень дерева образуют позиции, полученные из предыдущей вершины за один ход. С целью удобства ввода начальной позиции и последующего отображения ходов пустая клетка у нас будет представлена символом "*".
В нашей игре начало дерева может выглядеть следующим образом:
Естественно, что в очередной вершине дерева должна находиться позиция, не повторяющая предыдущие позиции. Так как общее количество перестановок из шести элементов равно 6!=720, то общее количество вершин в нашем дереве не будет превосходить эту границу. Более того, задача симметрична и из целевой позиции BASIC* можно будет породить ровно 359 новых вершин.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий