Ігрова самоорганізація гамільтонового циклу графа
| dc.citation.epage | 32 | |
| dc.citation.issue | 10 | |
| dc.citation.journalTitle | Вісник Національного університету "Львівська політехніка". Інформаційні системи та мережі | |
| dc.citation.spage | 13 | |
| dc.contributor.affiliation | Національний університет “Львівська політехніка” | |
| dc.contributor.affiliation | Lviv Polytechnic National University | |
| dc.contributor.author | Кравець, Петро | |
| dc.contributor.author | Пасічник, Володимир Володимирович | |
| dc.contributor.author | Проданюк, Микола | |
| dc.contributor.author | Kravets, Petro | |
| dc.contributor.author | Pasichnyk, Volodymyr | |
| dc.contributor.author | Prodaniuk, Mykola | |
| dc.coverage.placename | Львів | |
| dc.coverage.placename | Lviv | |
| dc.date.accessioned | 2023-06-07T07:24:38Z | |
| dc.date.available | 2023-06-07T07:24:38Z | |
| dc.date.created | 2021-03-01 | |
| dc.date.issued | 2021-03-01 | |
| dc.description.abstract | У роботі запропоновано нове застосування моделі стохастичної гри для розв’язування задачі самоорганізації гамільтонового циклу графа. Для цього у вершинах неорієнтованого графа розміщено ігрових агентів, чисті стратегії яких є варіантами вибору одного із інцидентних ребер. Випадковий вибір стратегій усіма агентами утворює набір локальних шляхів, що розпочинаються у кожній вершині графа. Поточні платежі гравців визначено як функції програшів, залежні від стратегій сусідніх гравців, які контролюють суміжні вершини графа. Ці функції сформовано зі штрафу за вибір протилежних стратегій сусідніми гравцями та штрафу за стратегії, які призвели до зменшення довжини локального шляху. Випадковий вибір чистих стратегії гравців спрямовано на мінімізацію їх функцій середніх програшів. Генерування послідовностей чистих стратегій виконано за дискретним розподілом, побудованим на основі динамічних векторів змішаних стратегій. Елементи векторів змішаних стратегій є імовірностями вибору відповідних чистих стратегій, які адаптивно враховують значення поточних програшів. Формування векторів змішаних стратегій визначено за марковським рекурентним методом, для побудови якого використано градієнтний метод стохастичної апроксимації. У ході гри метод збільшує значення імовірностей вибору тих чистих стратегій, які призводять до зменшення функцій середніх програшів. Для заданих способів формування поточних платежів результатом стохастичної гри є утворення патернів самоорганізації у вигляді циклічно зорієнтованих стратегій ігрових агентів. Умови збіжності рекурентного методу до колективно оптимальних розв’язків забезпечено дотриманням фундаментальних умов стохастичної апроксимації. Виконано розширення ігрової задачі на випадкові графи. Для цього вершинам приписано імовірності відновлювальних відмов, які спричиняють зміну структури графа на кожному кроці гри. Реалізації випадкового графа адаптивно враховуються під час пошуку гамільтонових циклів. Збільшення імовірності відмов сповільнює збіжність стохастичної гри. Комп’ютерне моделювання стохастичної гри забезпечило отримання патернів самоорганізації стратегій агентів у вигляді декількох локальних циклів або глобального гамільтонового циклу графа залежно від способів формування поточних програшів гравців. Достовірність експериментальних досліджень підтверджено повторенням реалізацій патернів самоорганізації для різних послідовностей випадкових величин. Результати дослідження можна використати на практиці для ігрового розв’язування NPскладних задач, транспортних і комунікаційних задач, для побудови протоколів автентифікації у розподілених інформаційних системах, для колективного прийняття рішень в умовах невизначеності. | |
| dc.description.abstract | This paper proposes a new application of the stochastic game model to solve the problem of selforganization of the Hamiltonian cycle of a graph. To do this, at the vertices of the undirected graph are placed game agents, whose pure strategies are options for choosing one of the incident edges. A random selection of strategies by all agents forms a set of local paths that begin at each vertex of the graph. Current player payments are defined as loss functions that depend on the strategies of neighboring players that control adjacent vertices of the graph. These functions are formed from a penalty for the choice of opposing strategies by neighboring players and a penalty for strategies that have reduced the length of the local path. Random selection of players' pure strategies is aimed at minimizing their average loss functions. The generation of sequences of pure strategies is performed by a discrete distribution built on the basis of dynamic vectors of mixed strategies. The elements of the vectors of mixed strategies are the probabilities of choosing the appropriate pure strategies that adaptively take into account the values of current losses. The formation of vectors of mixed strategies is determined by the Markov recurrent method, for the construction of which the gradient method of stochastic approximation is used. During the game, the method increases the value of the probabilities of choosing those pure strategies that lead to a decrease in the functions of average losses. For given methods of forming current payments, the result of the stochastic game is the formation of patterns of self-organization in the form of cyclically oriented strategies of game agents. The conditions of convergence of the recurrent method to collectively optimal solutions are ensured by observance of the fundamental conditions of stochastic approximation. The game task is extended to random graphs. To do this, the vertices are assigned the probabilities of recovery failures, which cause a change in the structure of the graph at each step of the game. Realizations of a random graph are adaptively taken into account when searching for Hamiltonian cycles. Increasing the probability of failure slows down the convergence of the stochastic game. Computer simulation of the stochastic game provided patterns of self-organization of agents’ strategies in the form of several local cycles or a global Hamiltonian cycle of the graph, depending on the ways of forming the current losses of players. The reliability of experimental studies is confirmed by the repetition of implementations of self-organization patterns for different sequences of random variables. The results of the study can be used in practice for game-solving NP-complex problems, transport and communication problems, for building authentication protocols in distributed information systems, for collective decision-making in conditions of uncertainty. | |
| dc.format.extent | 13-32 | |
| dc.format.pages | 20 | |
| dc.identifier.citation | Кравець П. Ігрова самоорганізація гамільтонового циклу графа / Петро Кравець, Володимир Пасічник, Микола Проданюк // Вісник Національного університету "Львівська політехніка". Інформаційні системи та мережі. — Львів : Видавництво Львівської політехніки, 2021. — № 10. — С. 13–32. | |
| dc.identifier.citationen | Kravets P. Game self-organization of hamiltonian cycle of the graph / Petro Kravets, Volodymyr Pasichnyk, Mykola Prodaniuk // Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Informatsiini systemy ta merezhi. — Lviv : Lviv Politechnic Publishing House, 2021. — No 10. — P. 13–32. | |
| dc.identifier.doi | doi.org/10.23939/sisn2021.10.013 | |
| dc.identifier.uri | https://ena.lpnu.ua/handle/ntb/59160 | |
| dc.language.iso | uk | |
| dc.publisher | Видавництво Львівської політехніки | |
| dc.publisher | Lviv Politechnic Publishing House | |
| dc.relation.ispartof | Вісник Національного університету "Львівська політехніка". Інформаційні системи та мережі, 10, 2021 | |
| dc.relation.references | 1. Gamazine, S., Deneubourg, J.-L., Frank, N. R., Sneyd, J., Theraula, G., Bonabeau, E. (2020). SelfOrganization in Biological Systems. Princeton University Press. | |
| dc.relation.references | 2. Sun, Z. (2018). Cooperative Coordination and Formation Control for Multi-agent Systems. Springer. | |
| dc.relation.references | 3. Кравець, П. О. (2019). Ігрові стратегії прийняття рішень в ієрархічних системах. І. Математична модель стохастичної гри. Системні дослідження та інформаційні технології, 3, 63–75. DOI: 10.20535/SRIT.2308-8893.2019.3.06 . | |
| dc.relation.references | 4. Кравець, П. О. (2019). Ігрові стратегії прийняття рішень в ієрархічних системах. II. Комп’ютерне моделювання стохастичної гри. Системні дослідження та інформаційні технології, 4, 105–118. DOI: 10.20535/SRIT.2308-8893.2019.4.11. | |
| dc.relation.references | 5. Zhang, W. J. (Editor). (2013). Self-organization: Theories and Methods. USA: Nova Science Publishers. | |
| dc.relation.references | 6. Кравець, П. О. (2015). Ігрова модель самоорганізації мультиагентних систем. Вісник Нац. ун-ту “Львівська політехніка”. Серія: Інформаційні системи та мережі, 829, 161–176. | |
| dc.relation.references | 7. Кравець, П. О. (2005). Ігрова самоорганізація системи агентів з індивідуальним оцінюванням стратегій. Вісник Нац. ун-ту “Львівська політехніка”. Серія: Комп’ютерні системи та мережі, 546, 75–85. | |
| dc.relation.references | 8. Schweisguth, F., Corson, F. (2019). Self-Organization in Pattern Formation. Review. Developmental Cell, 49 (5), 659–677. DOI: 10.1016/j.devcel.2019.05.019. | |
| dc.relation.references | 9. Кравець, П. О., Юринець, Р. В., Кісь, Я. П. (2020). Патерни самоорганізації стратегій у грі мобільних агентів. Вісник Нац. ун-ту “Львівська політехніка”. Серія: Інформаційні системи та мережі, 7, 24–34. DOI: 10.23939/sisn2020.07.024. | |
| dc.relation.references | 10. Кравець, П. О. (2021). Самоорганізація стратегій у грі переміщення агентів. Вісник Нац. ун-ту “Львівська політехніка”. Серія: Інформаційні системи та мережі, 9, 131–141. DOI: 10.23939.sisn2021.09.131. | |
| dc.relation.references | 11. Christofides, N. (1975). Graph theory: an algorithmic approach. New York: Academic Press. | |
| dc.relation.references | 12. Saoub, K. R. (2021). Graph Theory. An Introduction to Ptoofs, Algorithms, and Applications. Chapman and Hall/CRC. | |
| dc.relation.references | 13. Garey, M. R., Johnson, D. S., Endre, R. (1976). The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM Journal on Computing, 5 (4), 704–714. DOI: 10.1137/0205049. | |
| dc.relation.references | 14. Alhalabi, W., Kitanneh, O., Alharbi, A., Balfakih, Z., Sarirete, A. (2016). Efficient solution for finding Hamilton cycles in undirected graphs. SpringerPlus (2016) 5:1192, 1–14. DOI 10.1186/s40064-016-2746-8. | |
| dc.relation.references | 15. Korte, B., Vygen, J. (eds.). (2008). The Traveling Salesman Problem. In : Combinatorial Optimization. Algorithm and Combinatorics, 21, 527–562. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-71844-4_21. | |
| dc.relation.references | 16. Абросимов, М. Б. (2019). Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин. Прикладная дискретная математика, 45, 55–63. DOI: 10.17223/20710410/45/6. | |
| dc.relation.references | 17. Waligóra, Ł. (2017). Application of Hamilton’s graph theory in new technologies. World Scientific News, 89, 71–81. | |
| dc.relation.references | 18. Seo, J. H., Lee, H., Jang, M. S. (2008). Optimal Routing and Hamiltonian Cycle in Petersen-Torus Networks. Third 2008 Internaional Conference on Convergence and Hybrid Information Technоlogy, 303–308. | |
| dc.relation.references | 19. Шаріфов, Ф. А., Юн, Г. М., Кандиба, Г. Ю. (2014). Оптимізація маршрутів повітряних суден, що виконують агроавіаційні роботи. Наукоємні технології, 3 (23), 319–325. | |
| dc.relation.references | 20. Литвин, В. В., Угрин, Д. І. (2016). Методика вирішення завдань пошуку оптимальних туристичних маршрутів алгоритмами наслідування мурашиної колонії. Вісник Нац. техн. ун-ту “ХПІ”; зб. наук. пр. Сер.: Інформатика та моделювання. Харків: НТУ “ХПІ”, 21 (1193), 47–60. | |
| dc.relation.references | 21. Zhang, Q., Cheng, R., Zheng, Z. (2020). Energy-efficient renewable scheme for rechargeable sensor networks. EURASIP Journal on Wireless Communications and Networking, 74, 1–13. DOI: 10.1186/s13638-020-01687-4. | |
| dc.relation.references | 22. Листровой, С. В., Минухин, С. В., Листровая, Е. С. Разработка метода мониторинга распределенной вычислительной системы на основе определения кратчайших путей и кратчайших гамильтоновых циклов в графе. Восточно-Европейский журнал передовых технологий, 6/4 (78), 32–45. DOI: 10.15587/1729-4061.2015.56247. | |
| dc.relation.references | 23. Xiong, N., Wu, W., Wu, C. (2017). An improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. Sustainability, 9, 1–15. DOI: 10.3390/su9060985. | |
| dc.relation.references | 24. Medvedev, P., Pop, M. (2021). What do Eulerian and Hamiltonian cycles have to do genome assembly? PLoS Computational Biology, 17(5):e1008928, 1–5. DOI: 10.1371/journal.pcbi.1008928. | |
| dc.relation.references | 25. Мелкозерова, О. М., Рассомахин, С. Г. (2019). Идентификация отпечатков пальцев на основе гамильтоновых циклов распределения локальных признаков. Вісник Харківського нац. ун-ту ім. В. Н. Каразіна. Серія: “Математичне моделювання. Інформаційні технології. Автоматизовані системи управління”, 44, 51–65. DOI: 10.26565/2304-6201-2019-44-06. | |
| dc.relation.references | 26. Кавун, С. В., Ревак, І. О. (2015). Застосування теорії графів у задачах комунікаційного менеджменту. Науковий вісник Львівського державного університету внутрішніх справ, 2, 225–240. | |
| dc.relation.references | 27. Рацеев, С. М., Ростов, М. А. (2019). О протоколах аутентификации с нулевым разглашением знания. Изв. Сарат. ун-та. Нов. сер. Сер.: “Математика. Механика. Информатика”, 19 (1), 114–121. | |
| dc.relation.references | 28. Гуляницький, Л. Ф., Мулеса, О. Ю. (2016). Прикладні методи комбінаторної оптимізації: навч. посіб. К.: Видавничо-поліграфічний центр “Київський університет”. | |
| dc.relation.references | 29. Peng, Y., Choi, B., Xu, J. (2021). Graph Learning for Combinatorial Optimization: A Survey of State of the Art. Data Science and Engineering, 6, 119–141. DOI: 10.1007/s41019-021-00155-3. | |
| dc.relation.references | 30. Кутельмах, Р. К., Угриновський, Б. В. (2017). Дослідження ефективності декомпозиційного алгоритму спільних ребер для розв’язування задачі комівояжера великих розмірностей. Молодий вчений, 12 (52), 1–5. | |
| dc.relation.references | 31. Sleegers, J., Berg, D. (2021). Backtracking (the) Algorithms on the Hamiltonian Cycle Problem. arXiv:2107.00314v1 [cs.DS] 1 Jul 2021, 1–13. Access mode: https://arxiv.org/pdf/2107.00314v1.pdf. | |
| dc.relation.references | 32. Прокопенков, В. Ф. (2020). Новый метод поиска гамильтонова цикла на графе. Вісник Нац. техн. ун-ту “ХПІ”. Серія: Стратегічне управління, управління портфелями, програмами та проектами, 2, 43–49. DOI: 10.20998/2413-3000.2020.2.6. | |
| dc.relation.references | 33. Tambouratzis, T. (2000). Solving the Hamiltonian cycle problem via an artificial neural network. Information Processing Letters 75 (6), 237–242. DOI: 10.1016/S0020-0190(00)00116-2. | |
| dc.relation.references | 34. Ponce-de-Leon, E., Ochoa, A., Santana, R. (2020). A genetic Algorithm for a Hamiltonian Path Problem. In book: Industrial and Engineering Application of Artificial Intelligence and Expert Systems, 13–19. | |
| dc.relation.references | 35. Голембо, В. А., Муляревич, О. В. (2011). Модифікація методу мурашиної колонії для розв’язання задачі комівояжера колективом автономних агентів. Вісник Нац. ун-ту “Львівська політехніка”. Серія: Комп’ютерні системи та мережі, 717, 24–30. | |
| dc.relation.references | 36. Chen, B.-S. (2020). Stochastic Game Strategies and their Applications. CRC Press. | |
| dc.relation.references | 37. Ungureanu, V. (2018). Pareto-Nash-Stackelberg Game and Control Theory: Intelligent Paradigms and Applications. Springer. | |
| dc.relation.references | 38. Назин, А. В., Позняк, А. С. (1986). Адаптивный выбор вариантов: Рекуррентные алгоритмы. Москва: Наука. | |
| dc.relation.references | 39. Kushner, H. J., Yin, G. G. (2013). Stochastic Approximation Algorithms and Applications. Springer. | |
| dc.relation.references | 40. Кравець П. О. (2001). Збіжність ігрового градієнтного методу у знакододатних середовищах. Вісник Нац. ун-ту “Львівська політехніка”. Серія: Комп’ютерні системи та мережі, 438, 83–89. | |
| dc.relation.referencesen | 1. Gamazine, S., Deneubourg, J.-L., Frank, N. R., Sneyd, J., Theraula, G., Bonabeau, E. (2020). SelfOrganization in Biological Systems. Princeton University Press. | |
| dc.relation.referencesen | 2. Sun, Z. (2018). Cooperative Coordination and Formation Control for Multi-agent Systems. Springer. | |
| dc.relation.referencesen | 3. Kravets, P. (2019). Game strategies for decision making in hierarchical systems. I. Mathematical model of stochastic game (in Ukrainian). System Research and Information Technologies, 3, 63–75. DOI: 10.20535/SRIT.2308-8893.2019.3.06. | |
| dc.relation.referencesen | 4. Kravets, P. (2019). Game strategies for decision making in hierarchical systems. II. Computer simulation of stochastic game (in Ukrainian). System Research and Information Technologies, 4, 105–118. DOI: 10.20535/SRIT.2308-8893.2019.4.11. | |
| dc.relation.referencesen | 5. Zhang, W. J. (Editor). (2013). Self-organization: Theories and Methods. USA: Nova Science Publishers. | |
| dc.relation.referencesen | 6. Kravets, P. (2015). Game model of self-organizing of multiagent systems (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Information systems and networks, 829, 161–176. | |
| dc.relation.referencesen | 7. Kravets, P. (2005). Game self-organization of agents system with individual estimation of strategies (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Computer systems and networks, 546, 75–85. | |
| dc.relation.referencesen | 8. Schweisguth, F., Corson, F. (2019). Self-Organization in Pattern Formation. Review. Developmental Cell, 49 (5), 659–677. DOI: 10.1016/j.devcel.2019.05.019. | |
| dc.relation.referencesen | 9. Kravets, P., Jurinets R., Kis, Y. (2020). Patterns of self-organizing strategies in the game of mobile agents (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Information systems and networks, Issue 7, 24–34. DOI: 10.23939/sisn2020.07.024. | |
| dc.relation.referencesen | 10. Kravets, P. (2021). Self-organizing strategies in game of agent movement (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Information systems and networks, Issue 9, 131–141. DOI: 10.23939.sisn2021.09.131. | |
| dc.relation.referencesen | 11. Christofides, N. (1975). Graph theory: an algorithmic approach. New York: Academic Press. | |
| dc.relation.referencesen | 12. Saoub, K. R. (2021). Graph Theory. An Introduction to Ptoofs, Algorithms, and Applications. Chapman and Hall/CRC. | |
| dc.relation.referencesen | 13. Garey, M. R., Johnson, D. S., Endre, R. (1976). The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM Journal on Computing, 5 (4), 704–714. DOI: 10.1137/0205049. | |
| dc.relation.referencesen | 14. Alhalabi, W., Kitanneh, O., Alharbi, A., Balfakih, Z., Sarirete, A. (2016). Efficient solution for finding Hamilton cycles in undirected graphs. SpringerPlus (2016) 5:1192, 1–14. DOI 10.1186/s40064-016-2746-8. | |
| dc.relation.referencesen | 15. Korte, B., Vygen, J. (eds.). (2008). The Traveling Salesman Problem. In : Combinatorial Optimization. Algorithm and Combinatorics, 21, 527–562. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-71844-4_21. | |
| dc.relation.referencesen | 16. Abrosimov, M. (2019). Comparison of sufficient degree based conditions for Hamiltonian graph (in Russian). Prikl. Diskr. Mat., 45, 55–63. DOI: 10.17223/20710410/45/6. | |
| dc.relation.referencesen | 17. Waligóra, Ł. (2017). Application of Hamilton’s graph theory in new technologies. World Scientific News, 89, 71–81. | |
| dc.relation.referencesen | 18. Seo, J. H., Lee, H., Jang, M. S. (2008). Optimal Routing and Hamiltonian Cycle in Petersen-Torus Networks. Third 2008 Internaional Conference on Convergence and Hybrid Information Technjlogy, 303–308. | |
| dc.relation.referencesen | 19. Sharifov, F., Jun, G., Kandiba, G. (2014). Optimazation of routes of aircraft performing argo-aviation works (in Ukrainian). Science-intensive technjlogy, 3 (23), 319–325. | |
| dc.relation.referencesen | 20. Lytvyn, V., Ugrin, D. (2016). Methods of solving problems of finding optimal tourist routes by ant colony imitation algorithms (in Ukrainian). Bulletin of the National Technical University “Kharkiv Polytechnic Institute”. Collection of scientific works. Series: Computer Science and Modeling. Kharkiv: NTU “Kharkiv Polytechnic Institute”, 21 (1193), 47–60. | |
| dc.relation.referencesen | 21. Zhang, Q., Cheng, R., Zheng, Z. (2020). Energy-efficient renewable scheme for rechargeable sensor networks. EURASIP Journal on Wireless Communications and Networking, 74, 1–13. DOI: 10.1186/s13638-020-01687-4. | |
| dc.relation.referencesen | 22. Listrovoy, S., Minukhin, S., Listrovaya, E. (2015). Monitoring distributed computing systems on the basis of the determined shortest paths and shortest Hamiltonian cycles in a graph (in Russian). Eastern-European Journal of Enterprise Technologies 6 (4), 32–45. DOI: 10.15587/1729-4061.2015.56247. | |
| dc.relation.referencesen | 23. Xiong, N., Wu, W., Wu, C. (2017). An improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. Sustainability, 9, 1–15. DOI: 10.3390/su9060985. | |
| dc.relation.referencesen | 24. Medvedev, P., Pop, M. (2021). What do Eulerian and Hamiltonian cycles have to do genome assembly? PLoS Computational Biology, 17(5):e1008928, 1–5. DOI: 10.1371/journal.pcbi.1008928. | |
| dc.relation.referencesen | 25. Melkozerova, O., Rassomakhin, S. (2019). Identification of fingerprints based on Hamiltonian cycle of distribution of local features (in Russian). Bulletin of V. N. Karazin Kharkiv National University. Series: Mathematical modelling. Information technology. Automated control systems, 44, 51–65. DOI: 10.26565/2304-6201-2019-44-06. | |
| dc.relation.referencesen | 26. Kavun, S., Revak, I. (2015). Application of graph theory in communication management problems (in Ukrainian). Scientific Bulletin of Lviv State University of Internal Affairs, 2, 225–240. | |
| dc.relation.referencesen | 27. Ratseev, S., Rostov, M. (2019). Zero-knowledge proof authentication protocols (in Russian). Izv. Saratov Univ. Math. Mech. Inform., 19 (1), 114–121. | |
| dc.relation.referencesen | 28. Gulyanytsky, L., Mulesa, O. (2016). Applied methods of combinatorial optimization: Tutorial (in Ukrainian). Kyiv: Publishing and printing center “ Kyiv University”. | |
| dc.relation.referencesen | 29. Peng, Y., Choi, B., Xu, J. (2021). Graph Learning for Combinatorial Optimization: A Survey of State of the Art. Data Science and Engineering, 6, 119–141. DOI: 10.1007/s41019-021-00155-3 . | |
| dc.relation.referencesen | 30. Kutelmakh, R., Uhrynovskyi, B. (2017). Investigation of the efficiency of common edges decomposition algorithm for solving large-size traveling salesman problem (in Ukrainian). “Young Scientist”, No. 12 (52), 1–5. | |
| dc.relation.referencesen | 31. Sleegers, J., Berg, D. (2021). Backtracking (the) Algorithms on the Hamiltonian Cycle Problem. arXiv:2107.00314v1 [cs.DS] 1 Jul 2021, 1–13. Access mode: https://arxiv.org/pdf/2107.00314v1.pdf. | |
| dc.relation.referencesen | 32. Prokopenkov, V. (2020). A new method for finding a Hamiltonian cycle on a graph (in Russian). Bulletin of the National Thecnical University “Kharkiv Polytechnic Institute”. Series: Strategic management, portfolio management, and projects (in Russian), 2, 43 – 49. DOI: 10.20998/2413-3000.2020.2.6. | |
| dc.relation.referencesen | 33. Tambouratzis, T. (2000). Solving the Hamiltonian cycle problem via an artificial neural network. Information Processing Letters 75 (6), 237–242. DOI: 10.1016/S0020-0190(00)00116-2. | |
| dc.relation.referencesen | 34. Ponce-de-Leon, E., Ochoa, A., Santana, R. (2020). A genetic Algorithm for a Hamiltonian Path Problem. In book: Industrial and Engineering Application of Artificial Intelligence and Expert Systems, 13–19. | |
| dc.relation.referencesen | 35. Muliarevych, O., Golembo, V. (2011). A modification of the ant colony method for solving the problem og a salesman by a team of autonomous agents (in Ukrainian). Computer systems and networks: Bulletin of the Lviv Polytechnic National University, 717, 24–30. | |
| dc.relation.referencesen | 36. Chen, B.-S. (2020). Stochastic Game Strategies and their Applications. CRC Press. | |
| dc.relation.referencesen | 37. Ungureanu, V. (2018). Pareto-Nash-Stackelberg Game and Control Theory: Intelligent Paradigms and Applications. Springer. | |
| dc.relation.referencesen | 38. Nazin, A. V., Poznyak, A. S. (1986). Adaptive Choice of Variants: Recurrence Algorithms (in Russian). Moscow: Science. | |
| dc.relation.referencesen | 39. Kushner, H. J., Yin, G. G. (2013). Stochastic Approximation Algorithms and Applications. Springer. | |
| dc.relation.referencesen | 40. Kravets, P. (2001). Convergence of the game gradient method in sign-positive environments (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Computer systems and networks, 438, 83–89. | |
| dc.relation.uri | https://arxiv.org/pdf/2107.00314v1.pdf | |
| dc.rights.holder | © Національний університет “Львівська політехніка”, 2021 | |
| dc.rights.holder | © Кравець П. О., Пасічник В. В., Проданюк М. М., 2021 | |
| dc.subject | самоорганізація | |
| dc.subject | поведінковий патерн | |
| dc.subject | граф | |
| dc.subject | гамільтонів цикл | |
| dc.subject | стохастична гра агентів | |
| dc.subject | марковський рекурентний метод | |
| dc.subject | self-organization | |
| dc.subject | behavioral pattern | |
| dc.subject | graph | |
| dc.subject | Hamiltonian cycle | |
| dc.subject | stochastic agent game | |
| dc.subject | Markov recurrent method | |
| dc.subject.udc | 004.[852 | |
| dc.subject.udc | 94] | |
| dc.subject.udc | 519.837.3 | |
| dc.title | Ігрова самоорганізація гамільтонового циклу графа | |
| dc.title.alternative | Game self-organization of hamiltonian cycle of the graph | |
| dc.type | Article |
Files
Original bundle
License bundle
1 - 1 of 1