НИКИФОРОВ
Владимир Олегович
д.т.н., профессор
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.