Задача - коммивояжер
Cтраница 2
Для задачи коммивояжера решением на каждом шаге является город, который надо посетить следующим. В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода. [16]
Для задачи коммивояжера R X, где X - пространство перестановок из п - 1 элементов ( городов), а функция / ( х) определяется для данной перестановки ( цикла) согласно матрице издержек С. [17]
Описание задачи коммивояжера и ее формулировка в виде целочисленной задачи линейного программирования были даны в § 3 гл. [18]
Постановку задачи коммивояжера используют часто и в терминах теории графов. В простейшем случае отображение Г - направлен-ный отрезок, соединяющий две произвольные точки множества X. Элементы х е X называются вершинами графа, а направленный отрезок, соединяющий точки хеХ и у е Гх е X, - дугой графа. [19]
Решить задачу коммивояжера с матрицей реберных весо ] из задачи 9, используя алгоритм поиска с деревом решений и. [20]
Рассмотрим задачу коммивояжера и приведем примеры определения окрестности. [21]
Рассмотрите задачу коммивояжера с пятью городами, но допустите, что коммивояжер должен вернуться в город 1, побывав в двух других городах, а затем посетить два оставшихся города. [22]
Рассмотрим задачу коммивояжера с п 4 городам. [23]
Решить задачу коммивояжера с матрицей реберных весо. [24]
В задаче коммивояжера относительно успешной техникой перестройки дерева является разбиение на каждом шаге всех оставшихся решений на две группы: те, которые включают выделенную дугу, и те, которые ее не включают. Дуга, используемая для разбиения множества решений, выбирается соответственно эвристике ( описываемой ниже), преследующей цель отсечения максимального количества ветвей деревьев. Конечно, каждому узлу в дереве, теперь, очевидно, бинарном, будет сопоставляться нижняя граница стоимости всех решений, вырастающих из него. [25]
Например, задача коммивояжера может быть сведена к задаче целочисленного линейного программирования многими способами. Однако решение возникающих при этом задач методами целочисленного линейного программирования без учета специфики задачи коммивояжера является крайне непрактичным, осуществимо лишь при небольшом числе городов и не идет ни в какое сравнение с методами улучшенного перебора, в частности с методом ветвей и границ, развитым специально для задачи коммивояжера. [26]
Как формулируется задача коммивояжера в простейшей постановке. [27]
Экстремальной является задача коммивояжера, заключающаяся в составлении кратчайшего маршрута посещения п городов с возвращением в исходный пункт при условии, что расстояния между городами известны. Эта задача имеет приложения к изучению транспортных сетей. Комбинаторные задачи экстремального характера рассматриваются в теории потоков в сетях и в теории графов. [28]
Для решения задачи коммивояжера в настоящее время разработаны как точные, так и приближенные методы. Методом / - - оптимизации тоже можно получить лишь локальный экстремум: сущность метода заключается в совершении всевозможных замен г коммуникаций с /; в уже имеющемся маршруте. [29]
 |
Ребра, входящие в гамильтонов цикл С. [30] |
Страницы: 1 2 3 4