Метод віток та меж

Декомпозиція задачі на дерево підцілей є одним із загальних підходів до розв’язання складних проблем. Вітки останнього логічно з’єднуються за схемою ТА (АБО) залежно від того, що є необхідним для досягнення чергової цілі: усі її підцілі, чи хоча б одна. Пошук методом редукції до підзадач зводиться до побудови розв’язувального графу (рис.5)

Рис.5 Розв’язувальний граф

На рисунку 5 дугами помічено усі ТА-подрібнення, необхідні кінцеві підцілі затемнено.

Одним з відомих методів роботи з великими просторами станів є метод „породження та перевірки”. Його сутність полягає в тому, що деякий генератор вибудовує ряд станів-нащадків, далі застосовується послідовність тестів на припустимість породжених станів з метою мінімізації їх числа (частина тестів може бути вбудована в генератор). В основу методу віток та меж (МВМ) покладено такі дії:

1) обчислення границі цільової функції на множини планів (за умови максимізації – верхня оцінка, за умови мінімізації - нижня);

2) послідовне розбиття згаданих множин на дерево підмножин (галуження) та перелічування оцінок.

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

Можливі узагальнення методу такі:

1) алгоритм можна застосовувати, коли цільові функції та обмеження є нелінійними;

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

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

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

1) універсальних методів обчислення оцінок для підмножин планів;

2) способів напрацювання компромісів між точністю та трудомісткістю отримання оцінок;

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

У зв’язку з необхідністю запам’ятовування динамічних структур даних програмна реалізація МВМ не є тривіальною. Механізм повернення забезпечується стеком із запам’ятовуванням шляху від кореневої вершини (за умови невдалої реалізації виштовхується вершина стеку та здійснюється повернення на попередній рівень). Пошук „у глибину”, який складається з послідовного розбиття задачі на підзадачі до легко розв’язуваної підзадачі є малоефективним внаслідок необхідності прискіпливо аналізувати велику кількість тупикових напрямків. Так звана „глибина” існує на множині інтерпретаторів Прологу. Згодом було розроблено алгоритм „пошуку в ширину”, який передбачає першочерговий обхід найближчих до стартової вершин. Він програмується складнішим чином, оскільки потребує збереження альтернативних шляхів. При великому розмірі простору пошуку можна спробувати побудувати ієрархію просторів, що описують найважливіші рівні та найбільш конкретні сутності.

Наприклад, щоб планувати поїздку із центру міста А до центру міста Б, можна за дрібномасштабною картою спланувати переїзд від А до Б, а за великомасштабною – виїзд з А та проїзд всередині Б.

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