Page 89 - 4496

У житті ми постійно зустрічаємося із проблемою
ухвалення рішення з множини можливих розв'язків - із
проблемою вибору. У результаті вибору ми попадаємо в нову
ситуацію, коли знову потрібно робити вибір.
Можливості вибору при розв'язку проблеми можна
представити у вигляді дерева, де в корені – проблема, дузі
відповідає один з варіантів вибору, вершині - нова ситуація,
що виникає в результаті реалізації приписаного дузі варіанта.
Такому трактуванню відповідає граф типу дерева, що одержав
назву «дерево розв'язків». Припустимо, що можна оцінити
ефективність прийнятого вибору. Тоді виникає завдання
пошуку серед можливих шляхів від кореня (коли проблема
поставлена) до одного з листів (коли проблема вирішена)
шляхи, що мають оптимальну оцінку.
Стратегії пошуку по дереву розв'язків.
Припустимо, що дерево розв'язків дуже велике, тому
пошук шляхом повного перебору всіх можливих розв'язків
неможливий. Розглянемо стратегії пошуку, пов'язані зі
скороченим перебором розв'язків: метод розгалужень і метод
галузей і границь.
Метод розгалужень. Пошук починається від кореня
дерева. Вибирають мінімальну за вартістю вихідну дугу й по
ній переходять до наступної вершини. Якщо ця вершина не є
листом, знову переходять по мінімальній вихідній дузі, поки
не буде досягнуто листа. Алгоритм дуже просто реалізується,
але очевидно, що при цьому розв'язок може бути далеким від
мінімального.
Приклад. Визначимо за методом розгалуження шлях у
дереві на рис. 3.14. Шлях пройде по вершинах 1,3,8,16 і
рівний 21.
Метод галузей і границь. На кожному кроці
виділяється множина вершин як границі, ваги вершин якої
оцінюються довжиною шляху до неї від кореня, на границі
перебуває вершина з мінімальною оцінкою. Якщо ця вершина
є листком, то розв'язок знайдений – шлях до цього листка й
буде мінімальним розв'язком, якщо ні, то будується нова
границя із заміною знайденої вершини на вершини, пов'язані з
нею по вихідних дугах, і пошук розв'язку триває. Метод
гарантує одержання мінімального розв'язку, однак часто
пов'язаний з більшим обсягом обчислень.
86