Коммивояжёра задача, задача о бродячем торговце, одна из известных задач конечной математики; в простейшем случае формулируется следующим образом: даны n городов и известны расстояния между каждыми двумя городами; коммивояжёр, выходящий из какого-нибудь города, должен посетить n — 1 других городов и вернуться в исходный. В каком порядке ему нужно посещать города (по одному разу каждый), чтобы общее пройденное расстояние было минимальным? К такого типа задачам, связанным с объездом ряда пунктов и возвращением в исходную точку, относятся: задачи доставки продуктов питания в магазины, подвода электроэнергии к потребителям, построения кольцевой линии электропередач, различные задачи, возникающие при автоматизации монтажа схем, и т.д. Такова, например, задача отыскания оптимальной программы работы автоматического фрезерного станка для просверливания отверстий в заданных точках панели радиоприёмника, то есть нахождения такого порядка прохождения этих точек, при котором длина маршрута головки сверла была бы минимальной. Здесь начало маршрута не обязательно должно совпадать с его концом, но математически такая постановка сводится к приведенной выше простейшей К. з. Методы решения К. з., по существу, сводятся к организации полного перебора вариантов; никакого эффективного алгоритма не известно.
Лит.: Мудров В. И., Задача о коммивояжёре, М., 1969; Гольштеин Е. Г., Юдин Д. Б., Новые направления в линейном программировании, М., 1966.
В. П. Козырев.
Большая Советская Энциклопедия М.: "Советская энциклопедия", 1969-1978
Коммод Луций Элий Аврелий Коммод Луций Элий Аврелий (Lucius Aelius Aurelius Commodus) (161, Ланувий, — 192, Рим), римский император в 180—192. Последний представитель династии Антонинов, сын Марка Аврелия. В 176—...
Коммонс Джон Роджерс Коммонс (Commons) Джон Роджерс (13.10.1862, Холландсберг, Огайо, — 11.5.1945), американский историк-экономист и социолог. С 1904 профессор экономики Висконсинского университета Основопол...
Коммуна Коммуна (франц. commune, от лат. communis — общий), во Франции, Италии, Бельгии, Алжире, Сенегале и некоторых других государствах поселение городского или сельского типа, образующее низш...