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