|
|
Большая Советская Энциклопедия (цитаты)
|
|
|
|
|
Коммивояжера задача | Коммивояжера задача (далее К) задача о бродячем торговце, одна из известных задач конечной математики; в простейшем случае формулируется следующим образом: даны n городов и известны расстояния между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n — 1 других городов и вернуться в исходный. В каком порядке ему нужно посещать города (по одному разу каждый), чтобы общее пройденное расстояние было минимальным? К такого типа задачам, связанным с объездом ряда пунктов и возвращением в исходную точку, относятся: задачи доставки продуктов питания в магазины, подвода электроэнергии к потребителям, построения кольцевой линии электропередач, различные задачи, возникающие при автоматизации монтажа схем, и т.д. Такова, например, задача отыскания оптимальной программы работы автоматического фрезерного станка для просверливания отверстий в заданных точках панели радиоприемника, то есть нахождения такого порядка прохождения этих точек, при котором длина маршрута головки сверла была бы минимальной. Здесь начало маршрута не обязательно должно совпадать с его концом, но математически такая постановка сводится к приведенной выше простейшей К Методы решения К, по существу, сводятся к организации полного перебора вариантов; никакого эффективного алгоритма не известно.
Лит.: Мудров В. И., Задача о коммивояжере, М., 1969; Гольштеин Е. Г., Юдин Д. Б., Новые направления в линейном программировании, М., 1966.
В. П. Козырев. |
Для поиска, наберите искомое слово (или его часть) в поле поиска
|
|
 |
 |
 |
|
