Реферат на тему:
Задача про розміщення ферзів. Дерево пошуку та його обхід
Розглянемо шахівницю, що має розміри не 8 8, а n n, де n>0. Як відомо, шаховий ферзь атакує всі клітини та фігури на одній з ним вертикалі, горизонталі та діагоналі. Будь-яке розташування кількох ферзів на шахівниці будемо називати їх розміщенням. Розміщення називається допустимим, якщо ферзі не атакують одне одного. Розміщення n ферзів на шахівниці n n називається повним. Допустимі повні розміщення існують не при кожному значенні n. Наприклад, при n=2 або 3 їх немає. За n=4 їх лише 2 (рис.19.1), причому вони дзеркально відбивають одне одного.
Задача. Написати програму побудови всіх повних допустимих розміщень n ферзів, де 4 n20.
Для початку з'ясуємо деякі властивості допустимих розміщень. Очевидно, що в них кожний ферзь займає окрему вертикаль і горизонталь. Занумеруємо вертикалі й горизонталі номерами 1, ... , n та позначимо через <H1, H2, , Hi> послідовність номерів горизонталей, зайнятих ферзями, що стоять у вертикалях 1, 2, , i, де 0 i n. Випадок i=0 відповідає порожньому розміщенню <>.
Існує n способів розмістити ферзя в першій вертикалі, тобто перейти від порожнього розміщення до непорожнього. Цей перехід позначимо стрілкою (рис. 19.2(а)). За кожного з розміщень ферзя в першій вертикалі є n варіантів розміщення ферзя в другій вертикалі, але з них слід відкинути недопустимі. Відмітимо їх знаком '*' (рис.19.2(б)).
Узагалі, нехай зафіксовано розміщення ферзів у перших i-1вертикалях:
S(i-1)=<H1, ,Hi-1>.
Для побудови всіх допустимих розміщень із початком S(i-1) треба перебрати всі допустимі розміщення S(i)з ферзем у i-й вертикалі та для кожного побудувати всі допустимі розміщення з початком S(i).
Отже, маємо рекурсивний алгоритм побудови всіх допустимих розміщень, за яким пошук усіх допустимих заповнень ферзями останніх n-i+1вертикалей зводиться до пошуку заповнень n-i вертикалей.
Уточнимо цей алгоритм рекурсивною процедурою deps. Нехай розмір шахівниці не більше nm=20. Номери вертикалей та діагоналей містяться в діапазоні nums=1..nm, а розміщення зображається станом масиву H типу
arh = array[ nums ] of nums.
Процедура deps задає побудову розміщення, починаючи з i-ї вертикалі за фіксованих H[1], , H[i-1]. Підпрограми test та writs задають відповідно перевірку допустимості розміщення <H[1], ... , H[i-1], H[i]> та друкування повного розміщення. Вони викликаються у процедурі deps:
procedure deps ( var H : arh; n, i : nums);
var j, k : nums;
begin
for k := 1 to n do
begin
H[i] := k;
if test ( H, i) then
if i = n then writs ( H, n) {друкування повного розміщення }
else deps ( H, n, i+1 ) {рекурсивний виклик}
end
end
Функція test задає перевірку допустимості розміщення <H[1], , H[i-1], H[i]> за умови, що <H[1], , H[i-1]> є допустимим:
function test ( var H : arh; i : nums ) : boolean;
var j : nums; flag : boolean;
begin
j := 1; flag := true;
{перевірка, чи займається нова горизонталь і діагональ}
while ( j < i ) and flag do
begin
flag := ( H[i] <> H[j] ) and ( abs ( H[i]-H[j] ) <> i-j ); j := j+1
end;
test := flag
end
Розробка процедури writs друкування повного розміщення залишається вправою.
Програма розв'язання задачі має такий вигляд:
program Queens ( input, output );
const nm = 20;
type nums = 1..nm;
arh = array[ nums ] of nums;
var H : arh; n : nums;
procedure writs end;
function test end;
procedure deps end;
begin
writeln ('задайте розмір дошки: 4..20>'); readln ( n );
deps ( H, n, 1)
end.
2. Дерево пошуку та його обхід
Розміщення ферзів на шахівниці, що будуються в процесі виконання програми Queens, можна подати вузлами кореневого орієнтованого дерева(рис.19.3).
У цьому дереві кожний вузол <H[1], , H[i]>, де 0 i<n, має синів
<H[1], , H[i], 1>, <H[1], , H[i], 2>, , <H[1], , H[i], n>.
Відповідно цей вузол називається їхнім батьком. Сини вузла, сини його синів тощо називаються його нащадками, а він – їхнім попередником. Порожнє розміщення <> є коренем дерева, повні чи недопустимі розміщення – його листками, а допустимі неповні – проміжними вузлами. Кожний вузол дерева має певну глибину, або рівень у дереві. Глибиною кореня є 0, його синів – 1 тощо. Повним розміщенням відповідають листки дерева, які в даному разі мають глибину n. Зазначимо, що в даному разі глибина вузлів дерева збігається з довжиною їх як розміщень.
Це дерево відбиває пошук повних допустимих розміщень, тому називається деревом пошуку. Пересування по вузлах дерева у визначеному порядку називається обходом дерева. Отже, пошук розміщень у дереві є результатом його обходу.
Задамо алгоритм, реалізований процедурою deps із програми Queens, в узагальненому вигляді. Нехай A позначає вузол дерева, ОБХІД( A ) – обхід дерева з коренем А, а синами вузла A