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


Дерево решений - часть 2


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




- Начало -  - Назад -  - Вперед -



Книжный магазин