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