Лекции по дискретной математике. Глава 4 Часть 2 - файл n1.doc

Лекции по дискретной математике. Глава 4 Часть 2
скачать (540 kb.)
Доступные файлы (1):
n1.doc540kb.01.06.2012 12:07скачать

n1.doc

    1. Проблема путешествующего купца

(проблеме коммивояжера)


Определение







Старинная задача звучит так:

Для заданного числа городов, сети дорог и известной стоимости путешествия из одного города в другой найти самый дешевый маршрут однократного посещения каждого города с обязательным возвратом в город-начало путешествия.

Эквивалентная формулировка проблемы коммивояжера в теории графов (орграфов):

Во взвешенном графе (орграфе) найти гамильтонов цикл наименьшего веса.

Класс сложности






Проблема коммивояжера относится к классу NP-тяжелых.

Точные алгоритмы






Известны точные алгоритмы решения проблемы коммивояжера:

В 2001 году было найдено точное решение проблемы коммивояжера для 15112 немецких городов для одной из задач специальной библиотеки TSPLIB. Решение получено по алгоритму, использующему специальный вариант линейного программирования. Решение проводилось сетью из 100 процессоров. Общее время вычислений эквивалентно 22,6 годам для одного процессора Alpha 500 мГц.

Эвристические алгоритмы






Известны различные эвристические алгоритмы решения проблемы коммивояжера, которые «быстро» находят «хорошие» решения с «высокой» точностью. Современные методы могут решить проблемы чрезвычайно большой размерности (миллионы вершин) за приемлемое время; решения отличаются, вероятно, на 2-3% от оптимального решения.

Проблема коммивояжера является пробным камнем, «оселком» для многих общих эвристических алгоритмов.

Особенно интересны алгоритмы, «подсмотренные» у природы:

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

Простой графический алгоритм







Этот эвристический алгоритм находит верхнюю и нижнюю границу веса гамильтонова цикла во взвешенном полносвязном графе. Очевидно, что чем ближе будут верхняя и нижняя граница, тем точнее будет решение.

Алгоритм нахождения верхней границы проблемы путешествующего купца:

  1. Начать с конечного множества вершин числом 3 и более, соединенных попарно взвешенными рёбрами меньшего веса.

  2. Выбрать любую вершину и найти другую вершину, соединенную с выбранной вершиной ребром наименьшего веса.

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

  4. Найти вершину вне цикла, которая соединена с любой вершиной цикла ребром наименьшего веса. Зарисовать его вместе с вершиной. Обозначить эту новую вершину vn, а вершину цикла, к которой через ребро подсоединена vn, через vk. Кроме того, обозначить vk-1 вершину, предшествующую vk, а через vk+1 – вершину, последующую после вершины vk.

Если для весов ребер выполняется условие:

W(vk-1,vn) - W(vk-1,vk)  W(vn,vk+1) - W(vk,vk+1),

то в существующем цикле заменить ребро {vk-1,vk} на два ребра {vk-1,vn} и{vn,vk} с вершиной vn между ними.

Если вышеуказанное условие не выполняется, то в существующем цикле заменяем ребро {vk,vk+1} на два ребра {vk,vn} и{vn,vk+1} с вершиной vn между ними.








  1. Повторить шаг 4 до тех пор, пока не образуется цикл, затем стоп. Полученный цикл является верхней границей решения проблемы путешествующего купца.

Пример






Применим данный алгоритм к полносвязному графу:




7



  1. Начальная вершина – а. Ребро наименьшего веса, соединяющее а с другими вершинами – {a,e}.




  1. Ребро наименьшего веса, соединяющее вершину а еще с одной вершиной – ребро {a,c}.




  1. Формируем цикл




  1. Ребро наименьшего веса вне цикла, инцидентное к одной из вершин (a,c,e) – ребро {b,c}.




  1. Вставляем ребра {c,b} и {a,b} с вершиной b между вершинами a и c, а ребро {a,c}убираем:


6. Ребро наименьшего веса вне цикла, инцидентное к одной из вершин {a,b,c,e} – ребро {e,d}.





Обозначим:

vn = d,

vk-1 = a,

vk+1 = e,

vk = c




Запишем условие:

(w(a,d)=8)-(w(a,e)=2)< (w(d,c)=9)-(w(e,c)=4)


  1. Вставляем ребра {e,d}и {d,c} между вершинами e и c, а ребро {c,t}убираем:



Замечание







Поскольку данный алгоритм является эвристическим, найденное решение будет зависеть от выбора начальной вершины. Например, если выбрать начальную вершину b, то алгоритм дает следующее решение:



Алгоритм нахождения нижней границы проблемы путешествующего купца:


  1. Выбрать у взвешенного полносвязного графа вершину VS и удалить её из графа вместе с инцидентными к ней рёбрами.

  2. Найти минимальное каркасное дерево T, соединяющее оставшиеся вершины и подсчитать общий вес дерева w (для этой цели использовать алгоритм Крускала или метод Прима).

  3. Найти два наименьших веса, w1 и w2, рёбер, инцидентных с VS. Тогда w+w1+ w2 является нижней границей решения проблемы путешествующего купца.

Пример






a

a

7

1
d
. Начальная вершина а. Удаляем ее вместе с инцидентными ребрами:




  1. Находим минимальное каркасное дерево Т:





  1. Два ребра с наименьшими весами, инцидентные вершине а:

w1=w(a,e)=2,

w2 =w(a,c)=4.

5. Нижняя граница решения проблемы ТСР

w+ w1+ w2=16+2+4=22.

Замечание






Как и для случая оценки верхней границы, величина оценки нижней границы зависит от выбора вершины VS. Например, если взять VS=d, то получим:



Это решение замечательно тем, что верхняя и нижняя границы совпали! Следовательно, точное решение проблемы ТСР=26.

    1. Кратчайшие пути во взвешенных

графах и орграфах


Определения






Задан граф G=(V,E) или орграф D=(V,A) с функцией веса w:E?R (или w:A?R).

Вес w(P) пути

P=(v0,e0,v1,e1,…,vk-1,ek-1,vk)

Определяется как сумма весов ребер (дуг) пути:

w(P)=w(ei).

Путь между вершинами u и v будет кратчайшим (минимальным), если его вес будет наименьшим по сравнению с другими возможными путями между этими вершинами:



?(u,v)= minwi(u,v).

Существуют следующие разновидности зазачи определения кратчашего пути графа (орграфа):

Класс сложности






Проблема нахождения кратчайших путей в графе (орграфе) относится к Р-классу (полиномиальному классу).

      1. Алгоритм Дейкстры (Dijkstra)


Является алгоритмом решения задачи одного источника графа и орграфа при неотрицательных весах ребер (дуг).

Атрибуты






В графе G=(V,E) задана вершина-источник s. Для каждой вершины vV устанавливаюся следующие атрибуты:

Релаксация







Процесс релаксации ребра {u,v} позволяет определить, уменьшается ли кратчайший путь при добавлении в этот путь какого-либо ребра.

Пусть d[v] будет оценкой кратчайшего расстояния от вершины s к вершине v, полученная ранее. Предшественником вершины v была вершина z , т.е. ?[z]=v . При добавлении к пути между s и v нового ребра {u,v} возможны два варианта (далее w(u,v) обозначает вес ребра {u,v}):

Механизм релаксации ребер лежит в основе почти всех алгоритмов нахождения кратчайших путей.

Пример






s


“Cтарый” путь

Оценки кратчайшего пути:

-d[v]=9 при предшественнике

?[v]=x;

-d[u]=5.


x





Изменненый путь


v

u

2




При новой итерации алгоритма путь к вершине v получается добавление ребра {u,v}.

Тогда

d[v]=9
Релаксация ребра:

d[v]=7, ?[v]=u.




Инициализация:

d[s]=0, stat[s] =просмотрена, d[v]=, vV-s, ?[v]=nil,

stat[v]=недостигнута для всех вершин vV-s.

Создать приоритетную очередь Q вершин.
До тех пор, пока Q не будет пуста, делать:

{изять вершину u из головы очереди Q;

{для каждой вершины z, инцидентной вершине u,

делать

{ если d[z]>d[u]+w(u,z), тогда

d[z]=d[u]+w(u,z);

stat[z]=помечена;

stat[u]=просмотрена;

?[z]=u.

Убрать u из очереди, поставить z в очередь

}

}



Существует несколько способов создания приоритетной очереди. Самым простым явялется метод сортировки: очередь сортируется по созрастанию d[v] – от меньшего (голова очереди) к наибольшему (хвост очереди). Если d[v]=d[u], то размещение ребер в очереди друг относительно друга несущественно.

В этом случае сложность алгоритма O(n2+m), где n=|V|, m=|E|.







По указателям-предшественникам восстанавливаются кратчайшие пути (записываются только вершины пути)

d[s]=0;

?[b]=s ? (s-a), d[a]=3 ?[c]=d, ?[d]=b, ?[b]=s ? (s-b-d-s), d[c]=7


?[d]=b, ?[b]=s ? (s-b-d), d[d]=4 ?[e]=d, ?[d]=b, ?[b]=s ? (s-b-d-e), d[e]=7.
      1. Алгоритм Беллмана-Форда

(

Определение

Bellman-Ford)




Алгоритм Беллмана-Форда позволяет решать задачу одного источника для взвешенного (графа) орграфа. Алгоритм работает при отрицательных весах дуг и, кроме того, определяет цикл отрицательного веса.

Атрибуты






В орграфе D=(V,A) задана вершина-источник s. Для каждой вершины vV устанавливаются следующие аттрибуты:

Релаксация







Процесс релаксации аналогичен процессу, применяемому в алгоритме Дейкстры.

Очередь






Алгоритм устанавливает очередь FIFO дуг (первым пришел – первым вышел). Вершины ставятся в очередь случайным образом, поэтому не требуются сведения о расстояниях d[u].

Итерации






Алгоритм Беллмана-Форда выполняется в общем случае за |V|-1 итераций.



Инициализация:

d[s]=0, d[v]= ?[v]=nil для всех vV-s.
При i=1 до i-|V|-1

Делать для каждой дуги {u,v} из FIFO очереди

Делать

Если d[u]+w(u,v)
d[v]= d[u]+w(u,v);

?[v]=u.
Определение циклов отрицательного веса:

Для каждой дуги {u,v}A

Делать

Если d[v]>d[u]+w(u,v), то возвратить FALSE,

Иначе TRUE


Псевдокод






Сложность алгоритма Беллмана-Форда – О(mn), n=|V|, m=|A|.



FIFO очередь дуг (случайно построенная)

{d,c},{e,d},{b,e},{b,d},{d,b},{b,c},{s,c},{s,b}







FIFO очередь дуг (случайно построенная)

{b,d},{b,e},{e,d},{{d,c},d,b},{b,c},{s,c},{s,b}




3.6.3. Алгоритм Флойда (Floyd)


Определения






Алгоритм Флойда находит кратчайшие пути между всеми парами взвешенного графа или орграфа.

Алгоритм Флойда оперирует с матрицей весов[W(i,j)], которая является разновидностью взвешенной матрицы связности:


0 при i=j;

w(vi,vj), если есть ребро (дуга)из вершины vi в вершину vj;

в остальных случаях;


[W(i,j)]=

где w(vi,vj) – вес ребра (дуги) { vi,vj };

- знак бесконечности.

В течении k проходов справедлива следующай формула:

W(i,j)=min {W(i,j),W(i,k)+W(k,j)},

которая означает, что если путь через V(k) является кратчайшим, то он и выбирается.



Для k=1 до n делать

Для j=1 до n делать

Для i=1 до n делать

S=W(i,k)+W(k,j);

Если S Конец j цикла;

Конец k цикла.




Псевдокод





Сложность алгоритма Флойда – О(n3), n=|V|.











Расстояния между любыми парами вершин задаются следующей матрицей:

Проблема путешествующего купца (проблеме коммивояжера)
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации