|
Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://num-meth.srcc.msu.ru/zhurnal/tom_2004/v5r110.html
Дата изменения: Thu Apr 15 14:09:50 2004 Дата индексирования: Mon Oct 1 20:19:18 2012 Кодировка: Windows-1251 |
|
Маршрутизация на решетчато-клеточных структурах
Рябов Г.Г. |
|
Рассматривается расширение класса решетчатых графов с включением в окрестность на решетке дополнительных ребер с весами, равными соответствующим длинам векторов в евклидовом пространстве с целью приближения к евклидовой метрике. Установлено соответствие координат вершин, инцидентных дополнительным ребрам, последовательностям несократимых дробей Фарея-Коши. Предложен соответствующий алгоритм построения множества кратчайших путей на такой взвешенной решетке, который по существу моделирует ``волновой'' процесс построения поля всех кратчайших (от множества-источника) путей. Приведены оценки и примеры при машинной реализации. |
| Рябов Г.Г. - Институт точной механики и вычислительной техники РАН им. С.А. Лебедева, Ленинский пр., 51, Москва; e-mail: ggr@ipmce.ru |