Граф и его элементы

курсовая работа

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

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

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

Задача коммивояжера формулируется очень просто: на плоскости (в пространстве) расположены N городов, заданы расстояния между каждой парой городов. Требуется найти маршрут минимальной длины с посещением каждого города ровно один раз и с возвращением в исходную точку.

В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода.

Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния» можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения. В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из I в J. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства.

На графах задача формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.

Делись добром ;)