Задача - коммивояжер
Cтраница 3
Графическая модель задачи коммивояжера состоит из гамиль-тонова графа, вершины которого изображают города, а ребра - связывающие их дороги. Для решения задачи нам необходимо найти гамильтонов цикл минимального общего веса. [31]
Формальная постановка задачи коммивояжера приведена в гл. Повторим кратко эту постановку. Пусть задано п точек и известна матрица Cij 0 - матрица расстояний между точками. [32]
Комбинаторная постановка задачи коммивояжера состоит в следующем. [33]
Для решения задачи коммивояжера не существует эффективных алгоритмов, она является Л Р - полной проблемой. [34]
Очень наглядно задачу коммивояжера можно представить в виде графа G ( X, U), вершины которого соответствуют городам, а дуги - дорогам, соединяющим города между собой. Если из каждого города имеется непосредственный путь в любой другой город без захода в промежуточные города, то каждые две вершины графа будут соединены дугами в обоих направлениях. Получающийся при этом граф оказывается полным. [35]
Будучи NP-полной, задача коммивояжера не имеет практически реализуемого точного решения. На примере этой задачи мы ниже и рассмотрим различные методы ее приближенного решения с помощью нейросетей. [36]
Как правило, задача коммивояжера возникает только для сетей, которые содержат множество Гам и л ьто новых путей. В типичном примере коммивояжер должен посетить нескольких клиентов, используя самый короткий маршрут. В обычной сети улиц любые две точки будут связаны между собой, поэтому любой порядок расположения точек является Гамильтоиовым путем. Задача состоит в том, чтобы найти самый короткий. [37]
На первый взгляд задача коммивояжера кажется весьма похожей на задачу о китайском почтальоне и на задачу о взвешенном паросочетаний. Однако задача коммивояжера ( и даже ее специальный случай - задача о построении гамильтонова цикла) является существенно более сложной. [38]
Предполагается, что задачи коммивояжера большой размерности являются симметричными. [39]
 |
Решение задач о назначениях, ( а Решение задачи Р0. ( б Решение задачи Рг. [40] |
Так как решение задачи коммивояжера является гамильтоновым циклом, то мы будем пытаться исключить любое решение, состоящее более чем из одного цикла. [41]
Легко привести пример задачи коммивояжера, для которой описанный алгоритм дает сколь угодно плохое решение. [42]
К полученным решениям задач коммивояжера на всех уровнях для агрегатов и подмножеств могут применяться алгоритмы устранения пересечений и улучшения решений. [43]
Существует целочисленная постановка задачи коммивояжера, основанная на использовании булевых переменных xijk. Запишите подробно все ограничения и целевую функцию в такой постановке для задачи, включающей четыре города. Указание: коммивояжер в ходе своего объезда должен выезжать из каждого города. [44]
 |
Решение задач о назначениях, ( а Решение задачи Р0. [45] |
Страницы: 1 2 3 4