DOI: 10.17586/2226-1494-2015-15-1-166-168


УДК004.832.22;656.7

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

Бессмертный И.А., Королёва Ю.А., Суринов Р.Т.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования: Бессмертный И.А., Королёва Ю.А., Суринов Р.Т. Использование прецедентов для редуцирования дерева решений в задаче поиска путей на графе // Научно-технический вестник информационных технологий, механики и оптики. 2015. Том 15. № 1. С. 166–168

Аннотация

Рассматривается проблема организации взаиморасчетов между субъектами бизнеса с использованием клиринга, которая решается методом поиска путей на графе. Для сокращения сложности дерева решений в работе предлагается метод прецедентов, заключающийся в том, что в процессе развертывания дерева решений сохраняются промежуточные решения, которые используются при последующих операциях поиска. Приводятся алгоритм и пример, демонстрирующий сложность поиска, приближающуюся к линейной. Проведенные испытания в системе взаиморасчетов на воздушном транспорте демонстрируют сокращение объема реальных платежей приблизительно на 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.



Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2019 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика