Розробка алгоритму з квадратичною часовою складністю для знаходження максимального паросполучення
DOI:
https://doi.org/10.15587/1729-4061.2019.188104Ключові слова:
паросполучення, максимальне паросполучення, дводольний граф, збільшуючий шлях, задача про призначенняАнотація
Базуючись на розвитку ідеї пошуку в ширину у дводольних графах та основних визначеннях теорії паросполучень, показано, що задача побудови максимального паросполучення в довільному графі може бути зведена до його дводольного випадку. Доведено, що кожному поточному паросполученню в довільному графі взаємно однозначно відповідає паросполучення в дводольному графі. Проілюстровано, що жодний з поточних розв’язків задачі побудови максимального паросполучення в довільному графі не втрачається при переході до ітераційної схеми побудови максимального паросполучення у дводольному графі.
Для знаходження збільшуючого шляху відносно фіксованого паросполучення потужності k запропоновано модифікацію відомого алгоритму пошуку шляхів з даної вершини у всі досяжні вершини довільного графу. Роботу запропонованої модифікації проілюстровано на прикладі.
На основі викладених ідей, доведених тверджень та запропонованих алгоритмів та їх модифікації побудовано алгоритм знаходження максимального паросполучення з покращеною часовою оцінкою, порівняно з відомим алгоритмом Едмонса, що має часову оцінку складності O(n4). Основним недоліком алгоритму Едмонса є використання трудомісткої техніки стиснення циклів непарної довжини, які називають «квітками», що робить алгоритм непридатним для застосування в системах реального масштабу часу. Інші відомі алгоритми відрізняються від алгоритму Едмонса тільки більш досконалою організацією зберігання даних та обчислень, разом з тим зберігаючи складні дії по виявленню і упаковці циклів непарної довжини.
Запропонований підхід переходу від довільного графу до дводольного графу дозволив уникнути виникнення циклів непарної довжини, що дозволило значно підвищити ефективність алгоритму. Подальше підвищення продуктивності можливо за рахунок побудови паралельних версій алгоритму і оптимальної організації зберігання данихПосилання
- Toth, P., Vigo, D. (Eds.) (2014). Vehicle Routing: Problems, Methods, and Applications. SIAM. doi: https://doi.org/10.1137/1.9781611973594
- Brusco, M. J., Stahl, S. (2005). Branch-and-Bound Applications in Combinatorial Data Analysis. Springer. doi: https://doi.org/10.1007/0-387-28810-4
- Coste, P., Lodi, A., Pesant, G. (2019). Using Cost-Based Solution Densities from TSP Relaxations to Solve Routing Problems. Lecture Notes in Computer Science, 182–191. doi: https://doi.org/10.1007/978-3-030-19212-9_12
- Matsiy, O. B., Morozov, A. V., Panishev, A. V. (2016). Fast Algorithm to Find 2-Factor of Minimum Weight. Cybernetics and Systems Analysis, 52 (3), 467–474. doi: https://doi.org/10.1007/s10559-016-9847-9
- Zenklusen, R. (2019). A 1.5-Approximation for Path TSP. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 1539–1549. doi: https://doi.org/10.1137/1.9781611975482.93
- Papadimitriu, H., Stayglits, K. (1985). Kombinatornaya optimizatsiya: Algoritmy i slozhnost'. Moscow: Mir, 510.
- Edmonds, J. (1965). Paths, Trees, and Flowers. Canadian Journal of Mathematics, 17, 449–467. doi: https://doi.org/10.4153/cjm-1965-045-4
- Lovas, L., Plammer, M. (1998). Prikladnye zadachi teorii grafov. Teoriya parosochetaniy v matematike, fizike, himii. Moscow: Mir, 653.
- Sharifov, F. A. (2008). Sovershennye parosochetaniya i rasshirenniy polimatroid. Kibernetika i sistemniy analiz, 3, 173–179.
- Öncan, T., Şuvak, Z., Akyüz, M. H., Altınel, İ. K. (2019). Assignment problem with conflicts. Computers & Operations Research, 111, 214–229. doi: https://doi.org/10.1016/j.cor.2019.07.001
- Naser, H., Awad, W. S., El-Alfy, E.-S. M. (2019). A multi-matching approximation algorithm for Symmetric Traveling Salesman Problem. Journal of Intelligent & Fuzzy Systems, 36 (3), 2285–2295. doi: https://doi.org/10.3233/jifs169939
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2019 Andrii Morozov, Tamara Loktikova, Iurii Iefremov, Anatolii Dykyi, Pavlo Zabrodskyy
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
