Маршрутизация на решетчато-клеточных структурах

Авторы

  • Г.Г. Рябов

Ключевые слова:

решетчатые графы
окрестности на решетке
целые точки
кратчайшие пути
метрика
волновой процесс

Аннотация

Рассматривается расширение класса решетчатых графов с включением в окрестность на решетке дополнительных ребер с весами, равными соответствующим длинам векторов в евклидовом пространстве с целью приближения к евклидовой метрике. Установлено соответствие координат вершин, инцидентных дополнительным ребрам, последовательностям несократимых дробей Фарея-Коши. Предложен соответствующий алгоритм построения множества кратчайших путей на такой взвешенной решетке, который по существу моделирует «волновой« процесс построения поля всех кратчайших (от множества-источника) путей. Приведены оценки и примеры при машинной реализации.

Новые вычислительные технологии

Загрузки

Опубликован

2004-04-15

Выпуск

Том 5 (2004): Выпуск 1.

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

Г.Г. Рябов

Институт точной механики и вычислительной техники имени С. А. Лебедева РАН (ИТМиВТ РАН)
Ленинский пр., 51, 119991, Москва

Библиографические ссылки

  1. Александров А.Д. Внутренняя геометрия выпуклых поверхностей. М.: Гостехиздат, 1948.
  2. Lee C.Y. Algorithm for path connections and its applications // IEEE Trans. 1961. T. EC-10.
  3. Зиман 3.Ю., Рябов Г.Г. Волновой алгоритм и электрические соединения. М.: Изд-во ИТМ и ВТ, 1965.
  4. Рябов Г.Г. Об одном алгоритме решения лабиринта на дискретном поле и его применении // ДАН. 1966. 166, № 5.
  5. Rosenfeld A., Pfaltz J. Distance functions on digital pictures // Pattern Recognition. 1968. N 1.
  6. Монтролл Э. Статистика решеток // Прикладная комбинаторная математика. М.: Мир, 1968.
  7. Рябов Г.Г. Связность и преобразования дискретных конечных множеств // Труды семинара струк. и лог. схем. 7 . М.: Изд-во ИТМ и ВТ, 1969.
  8. Gardner M. Mathematical games. New York: Scientific American, 1971.
  9. Чандрасекхаран Э. Введение в аналитическую теорию чисел. М.: Мир, 1974.
  10. Santalo L. Integral geometry and geometric probability. Boston: Addison Wesley, 1979.
  11. Wolfram S. Cellular automata as simple selforganizing systems. Shampain: Univ. Illinois Press, 1982.
  12. Рябов Г.Г. Научные основы создания комплексных САПР высокопроизводительных ЭВМ. Автореферат докт. дис. М.: ИТМ и ВТ, 1983.
  13. Wolfram S. Cellular automation supercomputing. Shampain: Univ. Illinois Press, 1982.
  14. Рябов Г.Г. Модели коммутационных свойств конструкций ЭВМ. М.: Изд-во ИТМ и ВТ, 1989.
  15. Das P. Lattice of octagonal distances in digital geometry // Pattern Recognition. 1990. N 11.
  16. Hadju A. and Hadju L. Velocity and distance of neighbourhood sequences // Acta Cybernetica. 2003. 16 .
  17. Y.Boykov Y. and Kolmogorov Y. Computing geodesics and minimal surfaces via graph cut // Trans. Inter. Conf. On Computer Vision. 2003.