ТОЧНИЙ АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО ПАРОСПОЛУЧЕННЯ ЗІ ЗНИКАЮЧИМИ ДУГАМИ
DOI:
https://doi.org/10.26642/tn-2012-4(63)-159-164Анотація
В статті розглянуто задачу складання розкладу проходження процедур пацієнтами санаторію. Розроблено оптимальний алгоритм її розв’язку як розширеної задачі пошуку максимального паросполучення у дводольному графі зі зникаючими дугами. Запропонований точний алгоритм має меншу обчислювальну складність порівняно з методом повного перебору за рахунок скорочення кількості паросполучень, що аналізуватимуться.
Посилання
Данильченко А.М. Задача про паросполучення зі «зникаючими» дугами. Доведення NP- повноти / А.М. Данильченко, А.В. Панішев, А.А. Данильченко // Моделювання та інформаційні технології. – Вип. 63. – К., 2012. – С. 75–81.
Данильченко А.М. Задача о паросочетании с «исчезающими" дугами» / А.М. Данильченко, А.В. Панишев, А.А. Данильченко // Труды IХ Междунар. науч.-практ. конф. «Современные информационные и электронные технологии». – Одеса, 2011. – Т. 1. – С. 31.
Данильченко О.М. Розв’язання одного класу задач складання розкладів генетичними алгоритмами на кластерних системах / О.М. Данильченко, А.В. Панішев, А.О. Ібрагім // Вісник ЖІТІ. – 2004. – № 4. – С. 130–135.
Пантелеев А.В. Методы оптимизации в примерах и задачах / А.В. Пантелеев, Т.А. Летова. – М. : Высшая школа, 2005. – 544 с.
Кормен Т.Х. Алгоритмы для работы с графами / Т.Х. Кормен. – 2-е изд. – М. : Вильямс, 2006. – 1296 c.
Босс В.А. Перебор и эффективные алгоритмы / В.А. Босс. – K. : Изд-во ЛКИ, 2008. – 216 c.
Харари Ф. Теория графов / Ф.Харари ; пер. с англ. и предисл. В.П. Козырева ; под ред. Г.П. Гаврилова. – 2-е изд. – М. : Едиториал УРСС, 2003. – 296 с.
Пападимитриу Х. Комбинаторная оптимизация. Алгоритмы и сложность / Х.Пападимитриу, К.Стайглиц. – М. : Мир, 1985. – 512 с.
Акулич И.Л. Математическое программирование в примерах и задачах / И.Л. Акулич. – СПб. ; М. : Лань, 2011. – 185 с.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Анна Олександрівна Данильченко
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
Автор, який подає матеріали до друку, зберігає за собою всі авторські права та надає відповідному виданню право першої публікації, дозволяючи розповсюджувати даний матеріал із зазначенням авторства та джерела первинної публікації, а також погоджується на розміщення її електронної версії на сайті Національної бібліотеки ім. В.І. Вернадського та у відкритому доступі в електронному архіві університету та на сайті журналу.
