WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Задача про розміщення ферзів - Реферат

Задача про розміщення ферзів - Реферат

якого додаються та з якого вилучаються вузли дерева.
З кожним вузлом дерева пов'яжемо інформацію, яка додається при переході до цього вузла. В задачі про розміщення ферзів кореневий вузол відповідає порожньому розміщенню, тому з ним ніяка інформація не пов'язана. При переході від вузла, що подає розміщення , до вузла, відповідного розміщенню , збільшується номер останньої вертикалі i, в k-у клітину якої ставиться ферзь. Отже, з вузлом зв'язується пара чисел (i, k), що є номерами вертикалі й горизонталі. Саме такі пари додаються до магазина вузлів.
У задачі про ферзі роль магазина відіграє масив H. Збільшенняномера вертикалі i, тобто перехід до наступного компонента масиву, разом із присвоюванням H[i]:=k відтворюють додавання до магазина нового елемента - пари (i, k). Цикл із заголовком
for k := 1 to n do
у процедурі deps задає перебирання вузлів-"братів"
, , , ,
що рівносильно послідовному вилученню з магазина попереднього брата з додаванням наступного.
Опишемо обхід дерева пошуку розміщень без застосування рекурсії. Розглянемо пересування, пов'язані з вузлами дерева. З допустимого вузла-листка ми одразу рухаємося до його батька, з недопустимого - до його брата. Пересування, пов'язані з кожним його проміжним вузлом, можна подати, як на рис.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 (i0) 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]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]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.
Наведений опис задає так званий вичерпний пошук у дереві пошуку варіантів, оскільки рано чи пізно ми дістаємося кожного допустимого вузла дерева. Зазначимо, що цей опис є схемою багатьох алгоритмів розв'язання різноманітних задач, пов'язаних із перебиранням варіантів.
3. Метод розгалужень і меж
Обхід усіх вузлів дерева пошуку варіантів може виявитися надто довгим. Наприклад, якщо в дереві всі вузли є допустимими, кожний проміжний вузол має m синів, а глибина дерева n, то всього в дереві 1+m+m2+ … +mn=(mn+1-1)/(m-1) вузлів. Уже за m=10 та n=10 це більш, ніж 1010. Якщо припустити, що комп'ютер здатний обробити 105 вузлів за секунду, то обхід такого дерева триватиме 105 секунд, або приблизно добу.
Існує багато практичних задач, де вимагається відшукати чи побудувати не всі можливі варіанти, а лише один із них, найкращий у деякому розумінні, визначеному в задачі. Отже, тут з'являється таке поняття, як цінність варіантів. Загальним принципом розв'язання таких задач є скорочення обходу дерева варіантів. У ньому відкидаються деякі гілки, про які можна стверджувати, що вони не містять варіантів більш цінних, ніж уже знайдені. Розглянемо приклад.
Задача про три процесори. Нехай є три процесори, здатні виконувати завдання з однаковою швидкістю. Є набір завдань, про кожне з яких відомий час його виконання. Порядок виконання завдань неважливий. Якщо процесор почав виконувати завдання, то виконує його до кінця протягом зазначеного часу. Переключення процесора на виконання нового завдання відбувається миттєво. Треба так розподілити завдання між процесорами, шоб момент закінчення останнього завдання був мінімальним. Назвемо цю величину вартістю розподілу. Отже, займемося обчисленням мінімальної вартості серед можливих розподілів. Сам розподіл, що забезпечує таку вартість, для початку нас не цікавитиме.
Приклад. Нехай є 6 завдань, час виконання яких відповідно 7, 8, 9, 10, 11, 12. Якщо в зазначеному порядку розподілити перші три завдання між процесорами, а потім давати їх у тому ж порядку процесорам, що звільняються, то перший процесор закінчить роботу в момент 7+10=17, другий - у момент 8+11=19, а третій - 9+12=21. Маємо вартість 21. Проте їх можна розподілити інакше - 7+12, 8+11, 9+10, одержавши вартість 19.Р
Перше, що ми зробимо в розв'язанні задачі - упорядкуємо завдання за незростанням часу їх виконання. Отже, нехай P1, … , Pn - завдання, часи виконання T1, … , Tn яких задовольняють нерівності T1 … Tn. Розподіл можна
Loading...

 
 

Цікаве