Поиск контура с наименьшим средним значением в графе с переменными длинами дуг. Простейший случай

Аннотация

Рассматривается задача поиска в ориентированном графе, каждой дуге которого сопоставлены два числа - длина дуги и затраты от прохождения дуги, контура с минимальным отношением суммарных затрат к суммарной длине. Рассматривается простейший случай одноконтурного графа, в котором последовательность обхода вершин фиксирована, а требуется найти длины переходов. Изучены два частных случая зависимостей затрат от длины - произвольный дискретный набор и зависимость c = a + b· l^2.

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

оптимальный контур, уравнение Беллмана, контур с минимальными средними затратами, тропическая математика