М. Н. Алексеев, Ф. М. Алексеев, “Об алгоритмах оптимальной разметки”, Челяб. физ.-матем. журн., 2016, том 1, выпуск 1,страницы 16

Математика

Об алгоритмах оптимальной разметки

М. Н. Алексеев^a, Ф. М. Алексеев^b

^a Челябинский государственный университет, Челябинск, Россия
^b Московский физико-технический институт (государственный университет), Долгопрудный, Россия

Аннотация: Задача о выборе оптимального порядка разметки рассмотрена как особый случай задачи коммивояжёра. Предложены алгоритмы точного и приближённого решений задачи. Обсуждены оценки сложности алгоритмов и возможные подходы к их улучшению.

Ключевые слова: задача коммивояжёра, неориентированный взвешенный граф, минимальное остовное дерево, гамильтонова цепь, динамическое программирование, жадный алгоритм, алгоритм Прима, алгоритм Краскала.

УДК: 519.17

Поступила в редакцию: 18.02.2015
Исправленный вариант: 02.02.2016