Сборники трудов ИСП РАН


Оптимальное упорядочение конфликтующих объектов и задача коммивояжера.

Воеводин А.В., Косяченко С.А.

Аннотация

В работе представлена постановка задачи оптимального упорядочения конфликтующих объектов и ее связь с задачей коммивояжера (Travelling Salesman Problem или TSP). Задача оптимального упорядочения конфликтующих объектов возникает в социологии, при анализе графов в социальных сетях, при размещении рекламных заказов в сетях СМИ. В статье описаны используемые авторами на практике быстрые алгоритмы решения этой и связанных с ней задач. Также рассмотрена задача TSP с разреженной матрицей штрафов. Для задач TSP с ленточной и блочно-диагональной матрицами найдены необходимые и достаточные условия и построены точные алгоритмы, при которых достигается нулевое минимальное значение целевой функции задачи. Предложены эффективные алгоритмы и для произвольных разреженных матриц. Приведены результаты аналитических и численных исследований сложности разработанных алгоритмов и точности решения, а также рекомендации по применению алгоритмов для решения задач подобного типа.

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

оптимальное размещение; задача коммивояжера; TSP; NP-трудные задачи; ленточные матрицы; разреженные матрицы; жадный алгоритм; штрафная функция; конфликты, сети СМИ

Издание

Труды Института системного программирования РАН, том 25, 2013, стр. 207-224.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2013-25-12

Полный текст статьи в формате pdf Вернуться к содержанию тома