Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Науковий вісник НЛТУ...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Науковий вісник НЛТУ України
Article . 2019 . Peer-reviewed
License: CC BY
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

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

Authors: O. A. Nemova; Yu. I. Hrytsiuk;

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

Abstract

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

Related Organizations
Keywords

задача про ранець; задача цілочисельного програмування; задачі комбінаторної оптимізації; обмеження та умови задачі; умова оптимального розв'язку задачі, Forestry, SD1-669.5

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
gold