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

         

Для хранения дерева допустимых позиций


Для хранения дерева допустимых позиций используем два массива — массив строк tree, обеспечивающий хранение 360 шестисимвольных значений позиций, и числовой массив ind[360], в элементах которого будут фиксироваться индексы породивших строк. В нашем примере начальное заполнение массивов tree и ind может выглядеть следующим образом (табл. 6.1):

Таблица 6.1. Начальное заполнение массивов tree и ind





























































































































Индекс строки

Значение строки

Ссылка на породившую строку


0

BASIC*

-1


1

BAIC*S

0


2

BASI*C

0


3

B*AICS

1


4

B*SIAC

2


5

BASIC

2


6

BCAI*S

3


После того как построение полного дерева приводимых решений будет завершено, поиск оптимальной цепочки перестановок сводится к довольно простой процедуре. Сначала надо проверить, содержится ли исходная позиция среди вершин дерева. Если ее там нет, то заданная позиция не может быть сведена к позиции BASIC*. Если заданная позиция обнаружена в k-й вершине, то для восстановления цепочки переходов используем массив индексов породивших строк:

  • k1 = ind[k] - индекс предыдущей вершины, определяющей 1-й ход;


  • k2 = ind[k1l] - индекс вершины, определяющей 2-й ход;


  • k3 = ind[k2] - индекс вершины, определяющей 3-й ход;


  • ....................................................

    И это построение надо продолжать до тех пор, пока мы не встретим целевую вершину, у которой нет продолжения (ее индекс равен —1).

    Совет 1 (общий)

    Для построения дерева решений можно воспользоваться самым простым перебором: если пустая клетка находится на пересечении i-й строки и j-ro столбца, то теоретически с ней могут поменяться местами символы с индексами (i-l, j), (i+1, j), (i, j-1), (i, j + 1). На самом деле допустимых перемещений не четыре, а три или два, в зависимости от положения пустой клетки. Следовательно, в процедуре change придется позаботиться о проверке на принадлежность границам матрицы каждого кандидата на перемещение. И включать в дерево решений мы будем только те позиции, которые еще не встречались.


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