06. Задача коммивояжера

Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).

Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А.

Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:

· составить наиболее выгодный маршрут обхода наладчика в цехе (контролера, охранника, милиционера), отвечающего за должное функционирование заданного множества объектов (каждый из этих объектов моделируется вершиной графа);

· составить наиболее выгодный маршрут доставки деталей рабочим цеха или хлеба с хлебозавода по заданному числу булочных и других торговых точек (парковка у хлебозавода).

< Предыдущая		Следующая >