Формалізація постановок задач про укладання туристичного ранця та алгоритми їх розв'язання

  • Yu. I. Hrytsiuk Національний університет "Львівська політехніка", м. Львів https://orcid.org/0000-0001-8183-3466
  • O. A. Nemova Національний університет "Львівська політехніка", м. Львів
Ключові слова: задача про ранець; задача цілочисельного програмування; задачі комбінаторної оптимізації; обмеження та умови задачі; умова оптимального розв'язку задачі

Анотація

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

Біографії авторів

Yu. I. Hrytsiuk, Національний університет "Львівська політехніка", м. Львів

д-р техн. наук, професор, кафедра програмного забезпечення

O. A. Nemova, Національний університет "Львівська політехніка", м. Львів

студентка, кафедра програмного забезпечення

Посилання

Batishhev, D. I., Neimark, E. A., & Starostin, N. V. (2007). Primenenie geneticheskikh algoritmov k resheniiu zadach diskretnoi optimizatcii. Nizhnii Novgorod. [In Russian].
Bretthauer, K. M., & Shetty, B. (2002). The nonlinear Knapsack Problem – algorithms and applications. European Journal of Operational Research – Elsevier, Vol. 138, Iss. 3, 459–472. https://doi.org/10.1016/S0377-2217(01) 00179-5
Burkov, V. N., Gorgidze, I. A. (Ed.), & Lovetckii, S. E. (1974). Prikladnye zadachi teorii grafov. Tbilisi: Vychislitelnyi tcentr AN SSSR, 231 p. [In Russian].
Dantzig, G. B. (1957). Discrete-Variable Extremum Problems. Operations Research, Vol. 5, Iss. 2, 266–277. Institute for Operations Research and the Management Sciences. https://doi.org/10.1287/OPRE.5.2.266
Diffie, Whitfield, & Hellman, Martin E. (1977). Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Journal Computer, Vol. 10, pp. 74–84. June 1977.
Diubin, G. N., & Korbut, A. A. (1999). Zhadnye algoritmy dlia zadachi o rantce: povedenie v srednem. Sibirskii zhurnal industrialnoi matematiki, Vol. II, № 2(4), pp. 68–93. [In Russian].
Dorigo, M. (1992). Optimization, Learning and Natural Algorithms. PhD Thesis. Dipertamento di Ellettronica, Politechnico Di Milano. Italy, 140 p.
Gabidulin, E. M., Kshevetckii, A. S., & Kolybelnikov, A. I. (2011). Zashhita informatcii: uchebnoe posobie. Moskva: MFTI, 225 p. [In Russian].
Gallo, G., Hammer, P. L., & Simeone, B. (2009). Quadratic Knapsack Problems. Mathematical Programming Studies, (Vol. 12, pp. 132–149). February 24.
Grusho, A. A., Primenko, E. A., & Timonina, E. E. (2000). Analiz i sintez kriptoalgoritmov. Kurs lektcii. Moskva: Nauka, 110 p. [In Russian].
Iukhimenko, B. I. (2004). Uskorennyi algoritm metoda vetvei i granitc dlia resheniia zadachi tcelochislennogo lineinogo programmirovaniia. Trudy Odesskogo politekhnicheskogo un-ta, 2, 223–226. [In Russian].
Iukhimenko, B. I., & Kozina, Iu. Iu. (2005). Sravnitelnaia kharakteristika algoritmov metoda vetvei i granitc dlia resheniia zadach tcelochislennogo lineinogo programmirovaniia. Trudy Odesskogo politekhnicheskogo un-ta, 2, 199–204. [In Russian].
Karp, R. M. (1972). Reducibility Among Combinatorial Problems. In: R. E. Miller and J. W. Thatcher (Ed.). Complexity of Computer Computations, (pp. 85–103). New York: Plenum.
Karte, B. (1986). Kombinatorische Optimierung und algorithmische Principien. Okonomische Prognose, Entscheidungs und Gleichgewichtsmodelle, (pp. 286–341). Weinheim: VCH Verlangsgesellschschact.
Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack Problems – Springer Science + Business Media, 548 p. https://doi.org/10.1007/978-3-540-24777-7
Kin Ming Lai. (2001). Knapsack Cryptosystems: The Past and the Future. [In Russian].
Koblitc, N. (2001). Kurs teorii chisel v kriptografii. Izd. 2-oe. Moskva: Nauchnoe izdatelstvo TVP, 254. [In Russian].
Kulik, A., & Shachnai, H. (2010). There is no EPTAS for two-dimensional knapsack. Information Processing Letters, 110(16), 707–710. https://doi.org/10.1016/j.ipl.2010.05.031.
Levitin, A. V. (2006). Algoritmy. Vvedenie v razrabotku i analiz. Moskva: Viliams, 576 p. [In Russian].
Martello, S., & Toth, P. (1990). Knapsack Problems: algorithms and computer implementations. John Wiley & Sons Ltd., 29, 50, 296 p.
Mathews, G. B. (1897). On the Partition of numbers. Proceedings of the London Mathematical Society, Vol. s1-28, Issue 1, November 1896, pp. 486–490, https://doi.org/10.1112/plms/s1-28.1.486.
Merkle Ralph C., Hellman Martin E. (1981). On the security of multiple encryption. Journal Communications of the ACM, num. 7 Vol. 24, pp. 465–467. July 1981
Okulov, S. (2007). Programmirovanie v algoritmakh. Izd. 1-oe, Binom. Laboratoriia znanii, 384. [In Russian].
Osipian, V. O. (2006). O sisteme zashhity informatcii na osnove problemy riukzaka. Izvestiia Tomskogo politekhnicheskogo universiteta, Vol. 309, № 2, 209–212. [In Russian].
Riedhammer, K., Gillick, D., Favre, B., & Hakkani-Tür, D. (2008). Packing the Meeting Summarization Knapsack. In: Proceedings of the 9th International Conference of the ISCA (Interspeech 2008), Brisbane Australia: Proc. Interspeech, pp. 2434–2437.
Romanovskii, I. V. (1977). Algoritmy resheniia ekstremalnykh zadach. Moskva: Nauka, 352 p. [In Russian].
Salomaa, A. (1995). Kriptografiia s otkrytym kliuchom = Public-Key Cryptography. Moskva: Mir, 102–150. [In Russian].
Shnaier, B. (2002). Prikladnaia kriptografiia. Protokoly, algoritmy, iskhodnye teksty na iazyke Si = Applied Cryptography. Protocols, Algorithms, and Source Code in C. Izd. 2-oe. Moskva: Triumf, 816 p. [In Russian].
Sigal, I. Kh., & Ivanova, A. P. (2007). Vvedenie v prikladnoe diskretnoe programmirovanie. Moskva: Fizmatlit, 304. [In Russian].
Stiven S. Skiena. (2011). Algoritmy. Rukovodstvo po razrabotke. Izd. 2-e, SPb.: BKhV-Peterburg, 720 p. [In Russian].
Опубліковано
2019-04-25
Як цитувати
Hrytsiuk, Y. I., & Nemova, O. A. (2019). Формалізація постановок задач про укладання туристичного ранця та алгоритми їх розв’язання. Науковий вісник НЛТУ України, 29(4), 93-102. https://doi.org/10.15421/40290420

Статті цього автора (авторів), які найбільше читають