Актуальність теми




Скачати 66,16 Kb.
Дата конвертації25.12.2016
Розмір66,16 Kb.
РЕФЕРАТ

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

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

Об’єктом дослідження є задача пакування рюкзака.

Предметом дослідження є greedy-алгоритм розв'язку задачі пакування рюкзака.



Мета роботи: збільшення точності розв'язку задачі пакування рюкзака за допомоги модифікації greedy-алгоритму, за умови досягнення меншої складності, ніж у точних алгоритмів.

Наукова новизна роботи полягає в наступному:

1. Розроблено та проаналізовано спосіб модифікації greedy-алгоритму, який веде до збільшення точності розв'язку задачі пакування рюкзака при меншій складності, ніж у точних алгоритмів.

2.  Розроблено три варіанти реалізації модифікації greedy-алгоритму, які відрізняються за рівнем оптимізації та можуть використовуватися при різних умовах гранично допустимої пам'яті та часу, виділених на розв'язок задачі пакування рюкзака.



Практична цінність отриманих в роботі результатів полягає в тому, що запропонована модифікація greedy-алгоритму дає змогу підвищити точність розв'язку задачі пакування рюкзака, а складність модифікованого greedy-алгоритму не перевищує складність точних алгоритмів.

Апробація роботи. Основні положення і результати роботи були представлені та обговорювалися на VІI науковій конференції магістрантів та аспірантів «Прикладна математика та комп’ютинг – ПМК’2015» (Київ, 15 – 17 квітня 2015 року).

Структура та обсяг роботи. Магістерська дисертація складається зі вступу, трьох розділів та висновків.

У вступі подано загальну характеристику роботи, зроблено оцінку сучасного стану проблеми, обґрунтовано актуальність напрямку досліджень, сформульовано мету і задачі досліджень, показано наукову новизну отриманих результатів і практичну цінність роботи, наведено відомості про апробацію результатів і їхнє впровадження.

У першому розділі розглянуто задачу пакування рюкзака, її використання у сучасному житті та існуючі точні та наближені алгоритми пошуку розв'язання задачі пакування рюкзака.

У другому розділі сформульовано розроблену модифікацію greedy-алгоритму розв'язку задачі пакування рюкзака. Проведено аналіз запропонованої модифікації та теоретичне порівняння різних варіантів реалізації цієї модифікації, показані приклади різної роботи різних варіантів реалізації модифікації greedy-алгоритму.

У третьому розділі наведені умови та результати дослідження розробленої модифікації greedy-алгоритму розв'язку задачі пакування рюкзака з використанням різних масивів даних. Проведено практичне порівняння цієї модифікації з існуючими точними та наближеними алгоритмами пошуку розв'язку задачі пакування рюкзака.

У висновках представлені результати проведеної роботи.

Робота містить посилання на список використаних літературних джерел.



Ключові слова: задача пакування рюкзака, greedy-алгоритм, жадібний алгоритм.

ABSTRACT

Subject relevance. Knapsack problem is NP-complete problem from the field of combinatorial optimization. The unique formulation of the problem and the fact that it is present as a subproblem in larger, more general problems, making it important for research. While most researches of Knapsack problem relate to development and modification of accurate algorithms, approximate algorithms are overlooked leading research. However, the high speed of an acceptable solution in approximate algorithms makes them an important tool in solving practical problems related to the Knapsack problem.

Object is a Knapsack problem.

The object of the study is a greedy algorithm for solving the Knapsack problem.

Purpose: increasing of accuracy of solution of Knapsack problem by means of modification of greedy algorithm, subject to a lower complexity than accurate algorithms.

Scientific novelty consists in the following:

1. A method of modifying greedy algorithm is developed and analyzed, which leads to increased accuracy of Knapsack problem solution with less complexity than accurate algorithms.

2. A three implementations of the modified greedy algorithm are developed, which differ in terms of optimization and can be used under different conditions of the maximum allowable memory and time allocated for the search of the Knapsack problem solution.

The practical value obtained in the results is that the proposed modification of the greedy algorithm makes it possible to improve the accuracy of solution of Knapsack problem and the complexity of the modified greedy algorithm does not exceed the complexity of accurate algorithms.

Testing work. The main provisions and the results were presented and discussed at the VII scientific conference of undergraduates and graduate students "Applied Mathematics and Computing - PMK'2015" (Kyiv, 15 - April 17, 2015).

The structure and scope of work. Master's thesis consists of an introduction, three chapters and conclusion.

The introduction gives the general characteristics of, an estimation of the current state of the problem, the urgency towards research, formulated the goal and objectives of research, the scientific novelty of the results and practical value of the work, an understanding of the testing results and their implementation.

The first chapter introduces the Knapsack problem, its use in modern life and existing accurate and approximate algorithms of solving the Knapsack problem.

The second chapter formulated developed modification of greedy algorithm for solving the Knapsack problem. Performed an analysis of the proposed modification and theoretical comparison of various implementations of this modification, different examples of the various implementations of the modified greedy algorithm are shown.

The third chapter shown conditions and results of research of developed modification of greedy algorithm for solving the Knapsack problem using different data sets. A practical comparison of modification to existing accurate and approximate algorithms of solving the Knapsack problem was made.

In conclusion, the findings of this work showed.

The work contains links to a list of used literature.

Keywords: Knapsack problem, greedy-algorithm, greedy algorithm.

РЕФЕРАТ

Актуальность темы. Задача о рюкзаке представляет собой NP-полную задачу из области комбинаторной оптимизации. Уникальная формулировка задачи, а также тот факт, что она присутствует как подзадача в больших, общих проблемах, делает ее важной для научных исследований.

Объектом исследования является задача о рюкзаке.

Предметом исследования является greedy-алгоритм решения задачи о рюкзаке.

Цель работы: увеличение точности решения задачи о рюкзаке при помощи модификации greedy-алгоритма, при достижении меньшей сложности, чем у точных алгоритмов.



Научная новизна работы заключается в следующем:

1. Разработан и проанализирован способ модификации greedy-алгоритма, который ведет к увеличению точности решения задачи о рюкзаке при меньшей сложности, чем у точных алгоритмов.

2. Разработаны три варианта реализации модификации greedy-алгоритма, которые отличаются по уровню оптимизации и могут использоваться при различных условиях предельно допустимой памяти и времени, выделенных на решение задачи о рюкзаке.

Практическая ценность полученных в работе результатов заключается в том, что предложенная модификация greedy-алгоритма позволяет повысить точность решения задачи упаковки рюкзака, а сложность модифицированного greedy-алгоритма не превышает сложность точных алгоритмов.

Апробация работы. Основные положения и результаты работы были представлены и обсуждались на VII научной конференции магистрантов и аспирантов «Прикладная математика и компьютинг - ПМК'2015» (Киев, 15 - 17 апреля 2015 года).

Структура и объем работы. Магистерская диссертация состоит из введения, трех глав и выводов.

Во введении представлена общая характеристика работы, произведена оценка современного состояния проблемы, обоснована актуальность направления исследований, сформулированы цели и задачи исследований, показано научную новизну полученных результатов и практическую ценность работы, приведены сведения об апробации результатов и их внедрение.

В первом разделе рассмотрены задача о рюкзаке, ее использование в современной жизни и существующие точные и приближенные алгоритмы поиска решения задачи упаковки рюкзака.

Во втором разделе сформулирована разработанная модификация greedy-алгоритма решения задачи о рюкзаке. Проведен анализ предложенной модификации и теоретическое сравнение разных вариантов реализации этой модификации, показаны примеры разной работы различных вариантов реализации модификации greedy-алгоритма.

В третьем разделе приведены условия и результаты исследования разработанной модификации greedy-алгоритма решения задачи о рюкзаке с использованием различных массивов данных. Проведено практическое сравнение этой модификации с существующими точными и приближенными алгоритмами поиска решения задачи упаковки рюкзака.

В выводах представлены результаты проведенной работы.

Работа содержит ссылки на список использованных литературных источников.



Ключевые слова: задача о рюкзаке, greedy-алгоритм, жадный алгоритм.




База даних захищена авторським правом ©uchika.in.ua 2016
звернутися до адміністрації

    Головна сторінка