RUS
ENG
Полная версия
ЖУРНАЛЫ
// Челябинский физико-математический журнал
// Архив
Челяб. физ.-матем. журн.,
2016
, том 1,
выпуск 1,
страницы
16–23
(Mi chfmj2)
Математика
Об алгоритмах оптимальной разметки
М. Н. Алексеев
a
,
Ф. М. Алексеев
b
a
Челябинский государственный университет, Челябинск, Россия
b
Московский физико-технический институт (государственный университет), Долгопрудный, Россия
Аннотация:
Задача о выборе оптимального порядка разметки рассмотрена как особый случай задачи коммивояжёра. Предложены алгоритмы точного и приближённого решений задачи. Обсуждены оценки сложности алгоритмов и возможные подходы к их улучшению.
Ключевые слова:
задача коммивояжёра, неориентированный взвешенный граф, минимальное остовное дерево, гамильтонова цепь, динамическое программирование, жадный алгоритм, алгоритм Прима, алгоритм Краскала.
УДК:
519.17
Поступила в редакцию:
18.02.2015
Исправленный вариант:
02.02.2016
Полный текст:
PDF файл (637 kB)
Список литературы
Реферативные базы данных:
©
МИАН
, 2024