Критерії подібності динамічних задач комбінаторної оптимізації

Анотація

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

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