Задача про розміщення ферзів. Дерево пошуку та його обхід

begin

writeln ('задайте розмір дошки: 4..20>'); readln ( n );

deps ( H, n, 1)

end.

2. Дерево пошуку та його обхід

Розміщення ферзів на шахівниці, що будуються в процесі виконання програми Queens, можна подати вузлами кореневого орієнтованого дерева (рис.19.3).

У цьому дереві кожний вузол , де 0 i
, ,  , .

Відповідно цей вузол називається їхнім батьком. Сини вузла, сини його синів тощо називаються його нащадками, а він – їхнім попередником. Порожнє розміщення <> є коренем дерева, повні чи недопустимі розміщення – його листками, а допустимі неповні – проміжними вузлами. Кожний вузол дерева має певну глибину, або рівень у дереві. Глибиною кореня є 0, його синів – 1 тощо. Повним розміщенням відповідають листки дерева, які в даному разі мають глибину n. Зазначимо, що в даному разі глибина вузлів дерева збігається з довжиною їх як розміщень.

Це дерево відбиває пошук повних допустимих розміщень, тому називається деревом пошуку. Пересування по вузлах дерева у визначеному порядку називається обходом дерева. Отже, пошук розміщень у дереві є результатом його обходу.Задамо алгоритм, реалізований процедурою deps із програми Queens, в узагальненому вигляді. Нехай A позначає вузол дерева, ОБХІД( A ) – обхід дерева з коренем А, а синами вузла A є A(1), A(2),  , A(n). Тоді процедура deps із програми Queens має таку схему:

for k := 1 to n do

begin

перехід до вузла A(k);

if A(k) є допустимим then

if A(k) є листком then обробка листка A(k)

else ОБХІД( A(k) )

end

Як бачимо, процедура deps задає обхід дерева пошуку з вузлів-розміщень ферзів. Цей обхід називається обходом дерева у глибину. Ця назва зумовлена тим, що обхід дерева з довільним коренем закінчується лише після того, як закінчено обхід усіх його нащадків. Тобто від вузла ми переходимо до його нащадків, заглиблюючися в дерево.

Обхід дерева в глибину відтворюється за допомогою магазина (стека), до якого додаються та з якого вилучаються вузли дерева.

З кожним вузлом дерева пов'яжемо інформацію, яка додається при переході до цього вузла. В задачі про розміщення ферзів кореневий вузол відповідає порожньому розміщенню, тому з ним ніяка інформація не пов'язана. При переході від вузла, що подає розміщення , до вузла, відповідного розміщенню , збільшується номер останньої вертикалі i, в k-у клітину якої ставиться ферзь. Отже, з вузлом зв'язується пара чисел (i, k), що є номерами вертикалі й горизонталі. Саме такі пари додаються до магазина вузлів.