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


         

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


Для хранения дерева допустимых позиций используем два массива — массив строк 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 придется позаботиться о проверке на принадлежность границам матрицы каждого кандидата на перемещение. И включать в дерево решений мы будем только те позиции, которые еще не встречались.


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