|
симметричными, т.е. для всех i, j : C,j=CJt; удовлетворять неравенству треугольника, т.е. для всех i, j , k: (36) CIJ+CJk>Clk. (37) В математической постановке говорится о произвольной матрице, так как достаточно часто нарушается условие (36). В связи с этим различают два варианта задачи: симметричную задачу, когда условие (36) выполнятся, и несимметричную в противном случае. Второе замечание касается числа всех возможных туров. В несимметричной задаче коммивояжера все туры t=(ji,j2v.,jn,ji) и t'=(ji,jn,..,J2,ji) имеют разную длину и должны учитываться оба. Число разных туров определяется как (п-1)!. Симметричных туров будет в два раза меньше, т.к. каждый засчитан два раза: KaKtn какг\ Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i, j) проведено, если Сц=0 и не проведено, если Су=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём) [127, с. 311]. В терминах теории графов симметричную задачу коммивояжера можно сформулировать следующим образом: дана полная сеть с п вершинами, длина ребра (i, j) = Су. Найти гамильтонов цикл минимальной длины. В несимметричной задаче вместо термина «цикл» необходимо употреблять «контур», а вместо «ребра» «дуги». Среди простейших методов решения задачи коммивояжера лежат методы сплошного перебора, случайного перебора, а также жадные алгоритмы типа алгоритма ближайшего соседа (каждый очередной включаемый пункт должен 81 |
удовлетворять неравенству треугольника, т.е. для всех [,'}, к: С,+С^.>С,. (42) В математической постановке говорится о произвольной матрице, так как достаточно часто нарушается условие (41). В связи с этим различают два варианта задачи: симметричную задачу, когда условие (41) выполнятся, и несимметричную в противном.случае. Второе замечание касается числа всех возможных туров. В несимметричной задаче коммивояжера все туры 1=(}\,}2,-,}п,и) и t ' = ( j . , j 2 , j О имеют разную длину и должны учитываться оба. Число разных туров определяется как (п-1)!. Симметричных туров будет в два раза меньше, т.к. каждый засчитан два раза: как 1 и как 1'. Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (1,}) проведено, если Су^О и не проведено, если Су=1. Тогда, если существует тур длины О, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом.Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём) [65, с. 31Г. В терминах теории графов симметричную задачу коммивояжера можно сформулировать следующим образом: дана полная сеть с п вершинами, длина ребра (1, ]) = Су. Найти гамильтонов цикл минимальной длины. В несимметричной задаче вместо термина «цикл» необходимо употреблять «контур», а вместо «ребра» «дуги». Среди простейших методов решения задачи коммивояжера лежат методы сплошного типа перебора, случайного ближайшего перебора, соседа а также жадные алгоритмы алгоритма (каждый очередной включаемый пункт должен быть ближайшим к последнему выбранному пункту среди всех остальных, ещё не включенных в состав маршрута). Все эффективные, т.е. сокращающими полный перебор, методы решения задачи 97 |