Referat.me

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

Вид работы: реферат

Рубрика: Астрономия

Размер файла: 22.23 Kb

Скачать файл: referat.me-5108.docx

Краткое описание работы: Реферат на тему: Задача про розміщення ферзів. Дерево пошуку та його обхід Розглянемо шахівницю, що має розміри не 8´ 8, а ´ >0. Як відомо, шаховий ферзь атакує всі клітини та фігури на одній з ним вертикалі, горизонталі та діагоналі. Будь-яке розташування кількох ферзів на шахівниці будемо називати їх

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

Реферат на тему:

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


Розглянемо шахівницю, що має розміри не 8´ 8, а n ´ n , де n >0. Як відомо, шаховий ферзь атакує всі клітини та фігури на одній з ним вертикалі, горизонталі та діагоналі. Будь-яке розташування кількох ферзів на шахівниці будемо називати їх розміщенням . Розміщення називається допустимим , якщо ферзі не атакують одне одного. Розміщення n ферзів на шахівниці n ´ n називається повним . Допустимі повні розміщення існують не при кожному значенні n . Наприклад, при n =2 або 3 їх немає. За n =4 їх лише 2 (рис.19.1), причому вони дзеркально відбивають одне одного.

Задача. Написати програму побудови всіх повних допустимих розміщень n ферзів, де 4£ n £ 20.

Для початку з'ясуємо деякі властивості допустимих розміщень. Очевидно, що в них кожний ферзь займає окрему вертикаль і горизонталь. Занумеруємо вертикалі й горизонталі номерами 1, … , n та позначимо через <H 1 , H 2 , ¼ , Hi > послідовність номерів горизонталей, зайнятих ферзями, що стоять у вертикалях 1, 2, ¼ , i , де 0£ i £ n . Випадок i =0 відповідає порожньому розміщенню <>.

Існує n способів розмістити ферзя в першій вертикалі, тобто перейти від порожнього розміщення до непорожнього. Цей перехід позначимо стрілкою (рис. 19.2(а)). За кожного з розміщень ферзя в першій вертикалі є n варіантів розміщення ферзя в другій вертикалі, але з них слід відкинути недопустимі. Відмітимо їх знаком '*' (рис.19.2(б)).

Узагалі, нехай зафіксовано розміщення ферзів у перших i -1вертикалях:

S (i -1)=<H 1 ,¼ ,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 є 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 задає обхід дерева пошуку з вузлів-розміщень ферзів. Цей обхід називається обходом дерева у глибину . Ця назва зумовлена тим, що обхід дерева з довільним коренем закінчується лише після того, як закінчено обхід усіх його нащадків . Тобто від вузла ми переходимо до його нащадків, заглиблюючися в дерево.

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

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

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

for k := 1 to n do

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

<H [1],¼ , H [i -1], 1>, <H [1],¼ , H [i -1], 2>, ¼ , <H [1],¼ , H [i -1], n >,

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

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

Як бачимо, відвідувати проміжний вузол доводиться лише двічі – на початку та в кінці обходу дерева, коренем якого він є. Для того, щоб відрізнити ці два випадки, потрібні додаткові змінні. У разі розміщень ферзів перехід від вузла до його правого брата задається збільшенням H[i] на 1. Це рівносильне одночасному виштовхуванню вузла з магазина та додаванню його правого брата. Звідси випливає, що коли обробляється вузол глибини i , в магазині є лише по одному вузлу кожної глибини m , m £ 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

if i=n then {обробка вузла-листка}

if test(H, i) then {друкування повного допустимого розміщення}

{ та повернення до батька незалежно від наявності братів}

begin writs(H, n); i:=i-1; {i>0!} D[i]:=1 end

else

if H[i]<n then H[i]:=H[i]+1 {перехід до правого брата}

else {повернення до батька – }

{піддерево, в якому він є коренем, вже обійшли}

begin i:=i-1; {i>0!} D[i]:=1 end

else {обробка проміжного вузла}

if (D[i]=0) and test(H, i) then {рух у глибину}

begin i:=i+1; H[i]:=1; D[i]:=0 end

else {рух праворуч або нагору}

if H[i]<n then {рух праворуч}

begin H[i]:=H[i]+1; D[i]:=0 end

else {рух нагору}

begin i:=i-1; if i>0 then D[i]:=1 end

end

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

Узагальнимо наведений алгоритм, вважаючи, що, на відміну від задачі про розміщення ферзів, кореневий вузол дерева також містить деяку відповідну інформацію:

заштовхнути кореневий вузол у магазин ;

while магазин не порожній do

begin

нехай A – вузол на верхівці магазина ;

if A є листком then

begin

обробити листок A ;

виштовхнути A з магазина ;

if A не є правим сином свого батька then

заштовхнути в магазин правого брата A ;

end

else {A – проміжний вузол }

if A є допустимим і дерево з коренем A ще не оброблено then

заштовхнути в магазин лівого сина A

else {дерево з коренем A вже оброблено або A не є допустимим }

begin

виштовхнути A з магазина ;

if A не є правим сином свого батька і не є коренем then

заштовхнути правого брата A в магазин ;

end

end .

Наведений опис задає так званий вичерпний пошук у дереві пошуку варіантів, оскільки рано чи пізно ми дістаємося кожного допустимого вузла дерева. Зазначимо, що цей опис є схемою багатьох алгоритмів розв'язання різноманітних задач, пов'язаних із перебиранням варіантів.

Похожие работы

  • Засоби та принципи програмування на Ліспі

    Реферат на тему: Засоби та принципи програмування на Ліспі 1. Контрольні конструкції MuLisp використовує неявну форму PROGN для обчислення форм, які складають тіло функції. Окрім того, інтерпретатор muLіsp розпізнає в тілі функції неявні COND конструкції. Неявні COND-и роблять визначення функцій читабельними, короткими та ефективними.

  • Пошук даних в ОС Windows Основні прийоми роботи із пошуком в ОС WINDOWS

    Лабораторна робота№6 Тема : Пошук даних в ОС Windows. Мета : навчитись шукати всі потрібні файли, папки у Ос Win­dows за допомогою програми пошуку – Поиск.

  • Модальні групи

    Реферат на тему: Модальні групи (структурні властивості) Різноманітні дослідження багатьох математиків [3-4] присвячені вивченню зв’язків між будовою групи G і будовою решітки її підгруп LG. Встановлено, що будова цієї решітки суттєво впливає на будову самої групи G. Привертають особливу увагу групи G для яких решітка підгруп LG належить фіксованому многовиду решіток a.

  • About my favourite English writer

    Charles Dickens was an English novelist and one of the most popular writers in the history of literature. In his enormous body of works, Dickens combined masterly storytelling, humour, pathos, and irony with sharp social criticism and acute observation of people and places, both real and imagined.

  • Решения к Сборнику заданий по высшей математике Кузнецова Л.А. - 4 Интегралы (разное)

    Задача 1. Найти неопределенные интегралы. Задача 2. Вычислить определенные интегралы. Задача 3. Найти неопределенные интегралы. Задача 4. Вычислить определенные интегралы.

  • Решения к Сборнику заданий по высшей математике Кузнецова Л.А. - 6 Ряды (разное)

    Задача 1. Найти сумму ряда. Сумма ряда - сумма n первых членов ряда. Сумма ряда Задача 2. Исследовать на сходимость ряд. При любых значениях n выполняется неравенство

  • Початки комбінаторики

    Реферат на тему: 1. Принцип добутку і принцип суми. Розміщення з повтореннями Двома основними правилами комбінаторики є: Принцип суми . Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то AB містить m+n елементів.

  • Пенсії за віком Розміри і надбавки

    Реферат на тему: Пенсії за віком. Розміри і надбавки. План. 1. Розмір пенсії за віком. 2. Пенсії за віком при неповному стажі роботи. 3. Надбавки до пенсії за віком.

  • Метод розгалужень і меж Евристичні алгоритми Застосування принципу оптимальності

    Реферат на тему: Метод розгалужень і меж. Евристичні алгоритми. Застосування принципу оптимальності 1. Метод розгалужень і меж Обхід усіх вузлів дерева пошуку варіантів може виявитися надто довгим. Наприклад, якщо в дереві всі вузли є допустимими, кожний проміжний вузол має m синів, а глибина дерева n, то всього в дереві 1+m+m2+ … +mn=(mn+1-1)/(m-1) вузлів.

  • Цілі та дійсні типи мови Турбо Паскаль

    Реферат на тему: Цілі та дійсні типи мови Турбо Паскаль Базовий тип цілих integer утворено цілими, які займають 2 байти в знаковому поданні. Тепер уже зрозуміло, чому їх діапазон від -32768 до 32767. Крім цього типу, в мові Турбо Паскаль є ще кілька типів для подання цілих. Укажемо їх імена, спосіб (знаковий/беззнаковий) та розміри подання в байтах, а також їх діапазони.