Область применения. Постановка задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3,4 n и вернуться в первый

Постановка задачи. Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2,3,4…n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь коммивояжера был кратчайшим? В терминах теории графов: найти гамильтонов цикл в графе минимальной длины.

Задача коммивояжера является так называемой NP-трудной задачей, т.е. задачей, точное решение которой в общем случае может быть получено только за экспоненциальное время. Следовательно, решать ее переборным алгоритмом неэффективно при большом количестве вершин графа.

Одним из подходов к ее решению является сокращение перебора методом ветвей и границ. Этот метод позволяет опознать бесперспективные частичные решения, в результате чего от дерева поиска на одном шаге отсекается целая ветвь. Тем не менее, удовлетворительных оценок быстродействию алгоритма Литтла, основанного на этом методе, и родственных алгоритмов нет, хотя практика показывает, что на современных ЭВМ они иногда позволяют решить задачу коммивояжера для графов с количеством вершин, меньшим 100.

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его “второе рождение” связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера. В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (стратегия “разделяй и властвуй”). На каждом шаге метода элементы разбиения подвергаются проверке для выяснения, содержит данное подмножество оптимальное решение или нет. В качестве примера конкретного применения метода может быть предложена прикладная задача, связанная с проблемой размещения и обслуживания оборудования, в которой требуется определить оптимальную траекторию циклического маршрута движения робота-транспортера по траектории цеха с целью периодического обслуживания оборудования.