БОЛЬШАЯ СОВЕТСКАЯ ЭНЦИКЛОПЕДИЯ, БСЭ БОЛЬШАЯ СОВЕТСКАЯ ЭНЦИКЛОПЕДИЯ, БСЭ
Навигация:

Библиотека DJVU
Photogallery

БСЭ

Статистика:


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

Значение слова "Коммивояжёра задача" в Большой Советской Энциклопедии


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

 

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

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

В Большой Советской Энциклопедии рядом со словом "Коммивояжёра задача"

Коммерческий расчёт | Буква "К" | В начало | Буквосочетание "КО" | Коммифора


Статья про слово "Коммивояжёра задача" в Большой Советской Энциклопедии была прочитана 1652 раз


Интересное