Preview

Доклады БГУИР

Расширенный поиск

БЫСТРЫЙ ПОИСК КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ С ПРЕДОПРЕДЕЛЕННЫМИ РЕШЕНИЯМИ

Аннотация

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

Об авторах

М. П. Ревотюк
Белорусский государственный университет информатики и радиоэлектроники
Беларусь


М. К. Кароли
Белорусский государственный университет информатики и радиоэлектроники
Беларусь


Н. В. Хаджинова
Белорусский государственный университет информатики и радиоэлектроники
Беларусь


Список литературы

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.)

Просмотров: 2285


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1729-7648 (Print)
ISSN 2708-0382 (Online)