Предыдущая страница реферата | 4  5  6  7  8  9  10  11  12  13  14 | Следующая страница реферата

Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать суммарную протяженность маршрута F, которая запишется в следующем виде:

[pic] (4)

Относительно математической формулировки ЗК уместно сделать два замечания. Первое, в постановке Сij означали расстояния, поэтому должны выполняться следующие условия:

. неотрицательными, т.е. для всех j(Т:

Cij ( 0;

Cjj = ? (5)

(последнее равенство означает запрет на петли в туре),

. симметричными, т.е. для всех i, j:

Сij = Сji (6)

. удовлетворять неравенству треугольника, т.е. для всех:

Cij + Cjk ( Cik (7)

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (5)-(7) не удовлетворяют. Особенно часто нарушается условие (7) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (7) выполнено, и несимметричную - в противном случае. Условия (5)-(7) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной
ЗК все туры t=(j1,j2,…,jn,j1) и t’=(j1,jn,…,j2,j1) имеют разную длину и должны учитываться оба. Всего разных туров очевидно (n-1)!

Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. Симметричных туров имеется в два раз меньше, т.к. каждый засчитан два раза: как t и как t’.

Можно представить, что X состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если xij=0 и не проведено, если xij=1. Тогда, если существует тур длины 0, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).

Доказательство, что модель (1-4) описывает задачу о коммивояжере.

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

Рассмотрим условие (4) подробнее. Применим метод доказательства от противного, то есть предположим, что условие (4) выполняется для некоторого подцикла T из R городов, где R LHC ( LMT (9)

|— |1 |2 |3 |4 |5 |6 |
|1 |— |6 |4 |8 |7 |14 |
|2 |6 |— |7 |11 |7 |10 |
|3 |4 |7 |— |4 |3 |10 |
|1 |- |0 |0 |3 |3 |6 |
|2 |0 |- |1 |4 |1 |0 |
|3 |1 |2 |- |0 |0 |3 |
|табл. 4 |
|-|1 |2 |3 |4 |5|6 |
|1|- |6 |4 |8 |7|14|

Изложим алгоритм Литтла на примере 1 предыдущего раздела…

Повторно запишем матрицу:

Вычитание константы из элементов любой строки или столбца матрицы С, не изменяет минимальный тур.

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

Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.

Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на табл. 2.
Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-ый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. В таблице 2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.

Рекомендуем скачать другие рефераты по теме: доклад на тему культура, реферат н.





Предыдущая страница реферата | 4  5  6  7  8  9  10  11  12  13  14 | Следующая страница реферата