Поиск контура с наименьшим средним значением в графе с переменными длинами дуг. Простейший случай
Аннотация
Рассматривается задача поиска в ориентированном графе, каждой дуге которого сопоставлены два числа - длина дуги и затраты от прохождения дуги, контура с минимальным отношением суммарных затрат к суммарной длине. Рассматривается простейший случай одноконтурного графа, в котором последовательность обхода вершин фиксирована, а требуется найти длины переходов. Изучены два частных случая зависимостей затрат от длины - произвольный дискретный набор и зависимость c = a + b· l^2.
Ключевые слова:
оптимальный контур, уравнение Беллмана, контур с минимальными средними затратами, тропическая математика
Скачивания
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Статьи журнала «Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Санкт-Петербургским государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
