double arrow

Лабораторна робота №5

Тема: Альтернативні представлення комбінаторних задач.

Мета: Навчитися розв’язувати комбінаторні задачі методом їх декомпозиції.

 

Вступ. Мистецтво розв’язку комбінаторних задач полягає в уникненні перебору непотрібних та еквівалентних варіантів. Для цього необхідно «підігнати» задачу під певну відому комбінаторну модель. Бувають ситуації, коли для розв’язку необхідно використовувати одночасно декілька комбінаторних моделей. У таких випадках говорять про декомпозицію складної задачі на прості.

В комбінаторних моделях кожна комбінація представлена числами, за якими прихований зміст комбінаторної задачі. Існують комбінаторні задачі, які вимагають уточнення, або перефразування, тобто, іншого логічного представлення, яке спирається на логічні твердження з іншої комбінаторної моделі. Для розв’язку задачі необхідно представити процес перебору варіантів як добре відомий алгоритм.

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

Комбінаторні моделі працюють лише з номерами об’єктів, і тому для знаходження оптимального розрізу всім об’єктам задачі необхідно надати номери: дошка (1,…), дошка (2,…), …, деталь (1,…), деталь (2,…), … На перший погляд, задача є простою, тим не менше, якщо її розв’язувати так, як вона сформульована, то в результаті розв’язку ми отримаємо величезну кількість варіантів (які насправді є одним розв’язком), в яких дошки переставлені в різних послідовностях, і в кожній дошці також в різних послідовностях фігурують деталі.

Якщо ми напишемо програму, яка моделює процес розрізання дошок, то все одно ми отримаємо велику кількість варіантів, тому що тоді програма буде розрізняти послідовності розрізів, наприклад: спочатку відрізали від дошки 1, потім – від дошки 2, або інший варіант: спочатку відрізали від дошки 2, а потім – від дошки 1. Кількість еквівалентних варіантів буде зростати пропорційно факторіалу від кількості розрізів. Еквівалентні варіанти не лише створюють незручності при аналізі розв’язку, але й суттєво сповільнюють процес обчислень.

Невпорядкована вибірка (Selection) дозволяє суттєво зменшити кількість варіантів, які необхідно проаналізувати. Вона дозволяє сформулювати задачу наступним чином: з заданої множини дошок необхідно вибрати таку підмножину (невпорядковану вибірку), з якої можна виготовити задані деталі з мінімальними втратами деревини. Для скорочення перебору будемо розглядати кожну дошку як підмножину виготовлених деталей.

Реалізація алгоритму для знаходження всіх невпорядкованих вибірок 3-х елементів з 5-ти дається наступною програмою:

 

goal:- n=3, k=0, Selection(n,k), prn, fail.

Selection(n,k):- n>0, list(X), X>k, suppose(list2(X)), n1=n-1, Selection(n1,X).

Selection(n,k):- n=0.

prn:- list2(X), X>0, write(X), fail.

prn:- write().

list(1). list(2). list(3). list(4). list(5).   list2(0).

 

У цій програмі використовується додаткова змінна k, яка не дозволяє вибраним елементам знаходитись у несортованому вигляді. Якщо елементи відсортовані, то пропадає інформація про порядок їх вибору, тобто вибірка елементів у list2(…) буде невпорядкованою.

Застосуємо принцип побудови твердження Selection(n,k) для розв’язку поставленої задачі. Будемо щоразу вибирати таку дошку, номер якої буде більше за поточний номер (щоб створити невпорядковану вибірку). Так само поступимо і з деталями (див. твердження дошку_ріжемо_на_деталі ()).

Таким чином, кожна вибрана дошка буде містити вибірку деталей, на які її розрізали:

 

Оптимальний_розріз_дошок:- write("Оптимальний розріз дошок"),

     початковий_номер_дошки = 0,

     процес_розрізу_дошок(початковий_номер_дошки),

       поточна_вигода = 0,

     підрахувати_вигоду(поточна_вигода, загальна_вигода),

       загальна_вигода>30058,

     write("ефективність=", загальна_вигода),

       роздрук_послідовності_розрізів.

дошка(1,30). дошка(2,125). дошка(3,120). дошка(4,85).  дошка(5,50).

деталь(1,11). деталь(2,46). деталь(3,15). деталь(4,14).

деталь(5,12). деталь(6,13). деталь(7,45).

процес_розрізу_дошок(попередній_номер_дошки):-

          дошка(номер_дошки,розмір_дошки),

          номер_дошки > попередній_номер_дошки,

          початковий_номер_деталі = 0,

          дошку_ріжемо_на_деталі (номер_дошки,

          початковий_номер_деталі, розмір_дошки),

          процес_розрізу_дошок(номер_дошки).

процес_розрізу_дошок(номер_дошки):-

        not(деталь(довільний_номер, довільна_довжина)).

дошку_ріжемо_на_деталі(номер_дошки,

початковий_номер_деталі,розмір_дошки):-

                    деталь(номер_деталі,розмір_деталі),

                    номер_деталі>початковий_номер_деталі,

            залишок = розмір_дошки - розмір_деталі, залишок > 0,

           suppose(розріз(номер_дошки, номер_деталі)),

     дошку_ріжемо_на_деталі(номер_дошки, номер_деталі, залишок).

 дошку_ріжемо_на_деталі(номер_дошки, номер_деталі, залишок):-

                     suppose(дошка(номер_дошки, залишок)).

підрахувати_вигоду(поточна_вигода, загальна_вигода):-

                      дошка(номер_дошки, розмір_дошки),

                      вигода_від_розрізу = розмір_дошки * розмір_дошки,

                      нова_сума_балів = поточна_вигода + вигода_від_розрізу,

                      підрахувати_вигоду(нова_сума_балів, загальна_вигода),!.

 підрахувати_вигоду(поточна_вигода, загальна_вигода):-

                    загальна_вигода = поточна_вигода.

розріз(0,0).; таблиця результату: номер_дошки, скільки_відрізали

роздрук_послідовності_розрізів:- write("Розріз дошок при даній

             ефективності:"),розріз(номер_дошки,номер_деталі),

             номер_дошки>0, write("від дошки", номер_дошки,

             "відрізаємо деталь",  номер_деталі), fail.

роздрук_послідовності_розрізів:- write("-------------------------------").

   

Для підрахунку ефективності отриманого розрізу дошок використовуємо суму квадратів довжин дошок, що залишилися. Ця формула максимізує розмір залишків, тому що квадрат довжини великої дошки завжди буде більше суми квадратів довжин маленьких її відрізків (це можна перевірити). Програма знаходить такий розріз, який краще заданої ефективності (змінна загальна_вигода у твердженні підрахувати_вигоду) і зупиняється.

Завдання 1. Написати програму для виводу невпорядкованих вибірок трьох номерів з 5-ти номерів вашого IMEI. Всі номери – трьохзначні.

Завдання 2. Знайти свій варіант розв’язку задачі оптимального розрізу матеріалів (дошок) при максимальній ефективності розрізання. Довжину дошок взяти як трьохзначні номери з вашого IMEI, а довжину деталей взяти як двохзначні номери з цього ж IMEI, взяті в потрійній кількості. Перевірити результат на оптимальність.

 

 


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: