ВИКОРИСТАННЯ МОЖЛИВОСТЕЙ ТЕСТУВАННЯ ПРОГРАМ НА ВІДДАЛЕНИХ СЕРВЕРАХ ДЛЯ ПОРІВНЯННЯ ЕФЕКТИВНОСТІ МЕТОДІВ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ

Анотація

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