Розробка ефективного алгоритму пошуку оптимального розв’язку задачі про паросполучення із «зникаючими» дугами
DOI:
https://doi.org/10.15587/1729-4061.2017.92226Ключові слова:
задача про паросполучення, NP-повнота, дводольний граф, оптимальний алгоритм, метод гілок та меж, метод повного переборуАнотація
Розглянуто задачу складання розкладу проходження процедур пацієнтами санаторію. Обрана задача зведена до розширеної задачі пошуку максимального паросполучення в дводольному графі. Наведено доказ NP-повноти сформульованої задачі. Розроблено оптимальний алгоритм її вирішення. Наведений алгоритм реалізований як частина системи управління лікувальним процесом. Проведено порівняльний експеримент наведеного алгоритму з методом повного перебору
Посилання
- Danilchenko, A. (2012). Optimal algorithm for solving the problem of matching with vanishing arcs. Science news, 6, 46–54.
- Lupin, S. A., Milehina, T. V. (2007). The method for solving scheduling problems, focused on cluster computing systems. Proceedings of the universities. Ser. Electronics, 6, 63–69.
- Gafarov, E. (2007). Hybrid algorithm for solving the problem of minimization of summarized delay for one device. Information technology, 1, 30–37.
- Tymofijeva, N. K., Grycenko, V. I. (2011). Solving the problem of scheduling theory planning by structural alphabet search algorithm and hybrid. Upravlyayuschye systems and mashiny: Information Technology, 3, 21–36.
- Panishev, A., Danilchenko, A., Danilchenko, A. (2012). The problem of matching with the disappearing "arcs". Modeling and Information Technology, 63, 75–81.
- Biro, P., Manlove, D. F., Mittal, S. (2010). Size versus stability in the marriage problem. Theoretical Computer Science, 411 (16-18), 1828–1841. doi: 10.1016/j.tcs.2010.02.003
- Mugurel, I. (2014). Practical Algorithmic Optimizations for Finding Maximal Matchings in Induced Subgraphs of Grids and Minimum Cost Perfect Matchings in Bipartite Graphs. Theory and Applications of Mathematics & Computer Science, 4 (1), 1–13.
- Gelain, M., Pini, M., Rossi, F., Venable, K., Walsh, T. (2013). Local Search Approaches in Stable Matching Problems. Algorithms, 6 (4), 591–617. doi: 10.3390/a6040591
- Ageev, A. A., Pjatkin, A. V. (2009). Approximate algorithm for solving the problem of metric peripatetic salesman with an estimate of the accuracy 2. Discrete Analysis and Operations Research, 16 (4), 3–20.
- Sonkin, D. (2009). Adaptive algorithm of distributing orders for taxi service. The Tomsk Polytechnic University, 315 (5), 65–69.
- Li, W., Patrikeev, E. M., Xiao, D. (2015). A DNA Algorithm for the maximal matching problem. Automation and Remote Control, 76 (10), 1797–1802. doi: 10.1134/s0005117915100070
- Sergienko, A., Simonenko, A., Simonenko, P. (2016). Superior appointment scheduler algorithm in heterogeneous distributed computing systems. System Research and Information Technologies, 2, 20–35.
- Mazij, O., Morozov, A., Panishev, A. (2016). Recurrent algorithm for solving the problem of the weighted matching. Cybernetics and Systems Analysis, 5, 101–112.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2017 Anna Danylchenko, Vladimir Skachkov, Anatoly Panishev
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
