Ускорение многократного поиска кратчайших путей на графах

Ревотюк, М. П.; Кароли, М. К.; Кот, О. В.; Наймович, В. В.

Ускорение многократного поиска кратчайших путей на графах

Ревотюк, М. П., Кароли, М. К., Кот, О. В., Наймович, В. В.

Дата публикации: 2014

Дата публикации в реестре: 2020-03-03T07:07:54Z

Аннотация:

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

Ключевые слова:
деревья путей, переменные состояния, материалы конференций, графы, пути на графах

Тип: Статья