Науковий вісник НЛТУ України (Apr 2019)
Формалізація постановок задач про укладання туристичного ранця та алгоритми їх розв'язання
Abstract
Наведено формалізовані постановки задач про укладання туристичного ранця, запропоновано ефективні алгоритми їх розв'язання, що загалом дало змогу отримати адекватні результати розрахунку, провести змістовний їх аналіз та вибрати вдалі постановки задач для їх подальшого застосування. З'ясовано, що процедура укладання туристичного наплічника зазвичай є проблемою як для початківців, так і бувалих мандрівників. Водночас, досвідчені туристи в таких ситуаціях володіють деякими загальними правилами, які дають їм змогу вкладати найбільш потрібні речі не тільки встановленої місткості та мінімальної ваги, але й дотримуватись деякого порядку розміщення цих речей в наплічнику і надати йому традиційну форму, що забезпечує зручність тривалого його перенесення. Виявлено, що класична постановка задачі про ранець належить до задач цілочисельного програмування, вона допускає значну кількість різних узагальнень залежно від обмежень, накладених на ранець, на предмети або на їх вибір, а також на умову отримання оптимального розв'язку задачі – булевого чи кількісного. Проаналізовано можливі варіанти її постановок, з'ясовано основні причини широкого застосування в різних областях знань. Встановлено, що задача про ранець належить до класу NP-повних задач комбінаторної оптимізації, тому для неї немає поліноміального алгоритму, здатного її розв'язати за розумний проміжок часу. Визначено особливості застосування точних методів розв'язання задачі про ранець, проаналізовано метод повного перебору можливих варіантів, метод гілок і меж, жадібний алгоритм і методи динамічного програмування. Дано рекомендації щодо вибору серед них найпридатнішого для розв'язання запропонованих у роботі постановок задач. Наведено приклади деяких практичних постановок задачі про ранець, здійснено їхню формалізацію, алгоритмізацію та програмну реалізацію, запропоновано адекватний метод розв'язання, а також проведено змістовний аналіз отриманих результатів розрахунку, на підставі яких вибрано вдалі постановки задач для їх подальшого застосування.
Keywords
