Перебирання варіантів в програмуванні, Детальна інформація

Перебирання варіантів в програмуванні
Тип документу: Реферат
Сторінок: 10
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 26.4
Скачувань: 908
в) побудови всіх допустимих розміщень ферзів.

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

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

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

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

Це дерево відбиває пошук повних допустимих розміщень, тому називається деревом пошуку. Пересування по вузлах дерева у визначеному порядку називається обходом дерева. Отже, пошук розміщень у дереві є результатом його обходу.

Задамо алгоритм, реалізований процедурою deps із програми Queens, в узагальненому вигляді. Нехай A позначає вузол дерева, ОБХІД( A ) – обхід дерева з коренем А, а синами вузла A є A(1), A(2), \xF0BC , 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), що є номерами вертикалі й горизонталі. Саме такі пари додаються до магазина вузлів.

У задачі про ферзі роль магазина відіграє масив H. Збільшення номера вертикалі i, тобто перехід до наступного компонента масиву, разом із присвоюванням H[i]:=k відтворюють додавання до магазина нового елемента – пари (i, k). Цикл із заголовком

for k := 1 to n do

у процедурі deps задає перебирання вузлів-"братів"

, , \xF0BC , ,

що рівносильно послідовному вилученню з магазина попереднього брата з додаванням наступного.

Опишемо обхід дерева пошуку розміщень без застосування рекурсії. Розглянемо пересування, пов'язані з вузлами дерева. З допустимого вузла-листка ми одразу рухаємося до його батька, з недопустимого – до його брата. Пересування, пов'язані з кожним його проміжним вузлом, можна подати, як на рис.19.4.

Як бачимо, відвідувати проміжний вузол доводиться лише двічі – на початку та в кінці обходу дерева, коренем якого він є. Для того, щоб відрізнити ці два випадки, потрібні додаткові змінні. У разі розміщень ферзів перехід від вузла до його правого брата задається збільшенням H[i] на 1. Це рівносильне одночасному виштовхуванню вузла з магазина та додаванню його правого брата. Звідси випливає, що коли обробляється вузол глибини i, в магазині є лише по одному вузлу кожної глибини m, m\xF0A3 i. Тому достатньо однієї додаткової змінної для кожної можливої глибини. Отже, означимо додатковий масив D того ж самого типу, що й масив H. Значенням D[i] стає 0, коли до вузла глибини i ми приходимо згори або зліва, та 1 – коли знизу.

Перехід до вузла знизу – це повернення до батька, і його умовою в задачі про ферзі є H[i]=n.

Повернення до кореня дерева означає кінець його обходу. Тому використаємо умову i=0 як умову закінчення пошуку. Отже, пошук повних допустимих розміщень ферзів має таке описання, яке по суті є тілом процедури пошуку:

i:=1; H[i]:=1; D[i]:=0;

while (i<>0) do

begin

The online video editor trusted by teams to make professional video in minutes