БЫСТРЫЙ ПОИСК КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ С ПРЕДОПРЕДЕЛЕННЫМИ РЕШЕНИЯМИ
Аннотация
Предлагаются приемы ускорения многократного поиска кратчайших путей на графах, когда порядок порождаемых деревьев путей существенно меньше порядка графа. Однократная инициализация переменных состояния и выделение предопределенных решений снижает сложность поиска путей до линейной зависимости от объема сканируемого пространства.
Об авторах
М. П. Ревотюк
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
М. К. Кароли
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
Н. В. Хаджинова
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
Список литературы
1. N. Deo, Chi-yin Pang // Networks. 1984. Vol. 14. P. 275-323.
2. Fredman M.L., Tarjan R.E. //J. ACM. 1987. Vol. 34(3). P. 596-615.
3. Demetrescu C., Italiano G.F. //ACM Transactions on Algorithms. 2006. № 2 (4). P. 578-601.
4. Ревотюк М.П., Застенчик Н.И., Шешко Е.В.// Изв. БИА. 2004. № 1 (17)/2. С. 112-114.
Рецензия
Для цитирования:
Ревотюк М.П., Кароли М.К., Хаджинова Н.В. БЫСТРЫЙ ПОИСК КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ С ПРЕДОПРЕДЕЛЕННЫМИ РЕШЕНИЯМИ. Доклады БГУИР. 2014;(4):73-79.
For citation:
Revotjuk M.P., Qaraleh M.K., Khajynova N.V. QUICK SEARCH OF The shortest paths on the graph WITH A PREDETERMINED DECISION. Doklady BGUIR. 2014;(4):73-79. (In Russ.)
Просмотров: 3396
Послать статью по эл. почте 