ИСПОЛЬЗОВАНИЕ ПРЕЦЕДЕНТОВ ДЛЯ РЕДУЦИРОВАНИЯ ДЕРЕВА РЕШЕНИЙ В ЗАДАЧЕ ПОИСКА ПУТЕЙ НА ГРАФЕ

Рассматривается проблема организации взаиморасчетов между субъектами бизнеса с использованием клиринга, которая решается методом поиска путей на графе. Для сокращения сложности дерева решений в работе предлагается метод прецедентов, заключающийся в том, что в процессе развертывания дерева решений сохраняются промежуточные решения, которые используются при последующих операциях поиска. Приводятся алгоритм и пример, демонстрирующий сложность поиска, приближающуюся к линейной. Проведенные испытания в системе взаиморасчетов на воздушном транспорте демонстрируют сокращение объема реальных платежей приблизительно на 30%. Разработанный алгоритм предполагается внедрить также в других клиринговых организациях Российской Федерации. 

1. Rebezova M. Repayment problem at a settlement of debts // Computer Modelling and New Technologies. 2013. V. 17. N 2. P. 7–14.

2. Yang C., Song M. Access path planning of Mobile Agent in wireless sensor networks // Journal of Networks. 2014. V. 9. N 2. P. 507–514. doi: 10.4304/jnw.9.2.507-514

3. Swamy M.N.S., Thulasiraman K. Graphs, Networks, and Algorithms. NY: John Wiley & Sons, 1981. 454 p.

4. Takes F.W., Kosters W.A. Adaptive landmark selection strategies for fast shortest path computation in large real-world graphs // Proc. of IEEE/WIC/ACM International Joint Conf. on Web Intelligence and Intelligent Agent Technology, WI-IAT 2014. 2014. V. 1. Art. 6927522. P. 27–34. doi: 10.1109/WI-IAT.2014.13

5. Бессмертный И.А. Методы поиска информации с использованием интеллектуального агента // Изв. вузов. Приборостроение. 2009. Т. 52. № 12. С. 26–31.

6. Бессмертный И.А., Булыгин К.А. Многоагентный подход к решению задач неинформированного по- иска // Научно-технический вестник СПбГУ ИТМО. 2011. № 4 (74). С. 98–101.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License