Большая Советская Энциклопедия (цитаты)

Коммивояжера задача

Коммивояжера задача (далее К) задача о бродячем торговце, одна из известных задач конечной математики; в простейшем случае формулируется следующим образом: даны n городов и известны расстояния между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n — 1 других городов и вернуться в исходный. В каком порядке ему нужно посещать города (по одному разу каждый), чтобы общее пройденное расстояние было минимальным? К такого типа задачам, связанным с объездом ряда пунктов и возвращением в исходную точку, относятся: задачи доставки продуктов питания в магазины, подвода электроэнергии к потребителям, построения кольцевой линии электропередач, различные задачи, возникающие при автоматизации монтажа схем, и т.д. Такова, например, задача отыскания оптимальной программы работы автоматического фрезерного станка для просверливания отверстий в заданных точках панели радиоприемника, то есть нахождения такого порядка прохождения этих точек, при котором длина маршрута головки сверла была бы минимальной. Здесь начало маршрута не обязательно должно совпадать с его концом, но математически такая постановка сводится к приведенной выше простейшей К Методы решения К, по существу, сводятся к организации полного перебора вариантов; никакого эффективного алгоритма не известно.

 

 Лит.: Мудров В. И., Задача о коммивояжере, М., 1969; Гольштеин Е. Г., Юдин Д. Б., Новые направления в линейном программировании, М., 1966.

  В. П. Козырев.


Для поиска, наберите искомое слово (или его часть) в поле поиска


Новости 29.05.2024 21:57:41