ТОЧНИЙ АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО ПАРОСПОЛУЧЕННЯ ЗІ ЗНИКАЮЧИМИ ДУГАМИ

Автор(и)

  • Анна Олександрівна Данильченко Житомирський державний технологічний університет, Україна

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##

Опубліковано

2015-10-20

Як цитувати

Данильченко, А. О. (2015). ТОЧНИЙ АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО ПАРОСПОЛУЧЕННЯ ЗІ ЗНИКАЮЧИМИ ДУГАМИ. Вісник ЖДТУ. Серія "Технічні науки", (4(63), 159–164. https://doi.org/10.26642/tn-2012-4(63)-159-164

Номер

Розділ

Інформатика