ВИКОРИСТАННЯ МОЖЛИВОСТЕЙ ТЕСТУВАННЯ ПРОГРАМ НА ВІДДАЛЕНИХ СЕРВЕРАХ ДЛЯ ПОРІВНЯННЯ ЕФЕКТИВНОСТІ МЕТОДІВ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ
Ескіз недоступний
Дата
2023
Автори
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
В статті обгрунтована доцільність використання можливостей тестування програм навіддалених серверах для порівняння ефективностей реалізацій різних методів розв’язання обраної задачікомбінаторної оптимізації. Описано метод поступового формування множини значень цільової функції якальтернативного методам пошуку з поверненнями та врахування змін. Пояснено механізм дії алгоритмів, якізастосовують ці методи для розв’язування спрощеного варіанту класичної задачі пакування рюкзака. Наведенофрагменти програм, які реалізують дані алгоритми мовою програмування C# та проаналізовано результати їхтестування у віддаленому обчислювальному середовищі. За результатами тестування показано, що реалізаціяметоду поступового формування множини допустимих значень кардинально зменшує час виконання програм упорівнянні з реалізаціями інших методів, що вказує на його ефективність.За результатами дослідження зроблено основні висновки про те, що, по-перше, для прискореннярозв’язування задач комбінаторної оптимізації недостатньо оминати деякі варіанти повного перебору, апотрібно мінімізувати ще й час обчислення цільової функції для кожного варіанту, враховуючи обмеженнязадачі. По-друге, метод поступового формування множини допустимих значень цільової функції є дієвоюальтернативою методам пошуку з поверненнями та врахування змін при розв’язуванні задач комбінаторноїоптимізації, якщо область значень дискретна, а хід розв’язання подібний до методу динамічного програмування.І, по-третє, для визначення найефективнішого способу розв’язування задачі комбінаторної оптимізаціїнедостатньо порівнювати час виконання на відомих тестових наборах, а й потрібно намагатися попередньопроаналізувати їх обчислювальну складність.