Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Граф – это набор вершин (узлов) и соединяющих их ребер (дуг).
Направленный граф (ориентированный, орграф) – это граф, в котором все дуги имеют направления.
Цепь – это последовательность ребер, соединяющих две вершины (в орграфе – путь).
Цикл – это цепь из какой-то вершины в нее саму.
Взвешенный граф (сеть) – это граф, в котором каждому ребру приписывается вес (длина).
Связный граф – это граф, в котором существует цепь между каждой парой вершин.
k-cвязный граф – это граф, который можно разбить на k связных частей.
Кратчайшие пути (алгоритм Дейкстры)
Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов.
Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.
Алгоритм Дейкстры:
1)присвоить всем вершинам метку ∞;
2)среди нерассмотренных вершин найти вершину j с наименьшей меткой;
3)для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние;
4)если остались необработанны вершины, перейти к шагу 2;
5)метка = минимальное расстояние.
Реализация:
Массивы:
1)массив a, такой что a[i]=1, если вершина уже рассмотрена, и a[i]=0, если нет.
2)массив b, такой что b[i] – длина текущего кратчайшего пути из заданной вершины x в вершину i;
3)массив c, такой что c[i] – номер вершины, из которой нужно идти в вершину i в текущем кратчайшем пути.
Инициализация:
1)заполнить массив a нулями (вершины не обработаны);
2)записать в b[i] значение W[x][i];
3)заполнить массив c значением x;
4)записать a[x]=1.
Основной цикл:
1)если все вершины рассмотрены, то стоп.
2)среди всех нерассмотренных вершин (a[i]=0) найти вершину j, для которой b[i] – минимальное;
3)записать a[j]:=1;
4)для всех вершин k: если путь в вершину k через вершину j короче, чем найденный ранее кратчайший путь, запомнить его: записать b[k]:=b[j]+W[j,k] и c[k]=j.
Вывод маршрута в вершину i (использование массива c):
1)установить z:=i;
2)пока c[i]<>x присвоить z:=c[z] и вывести z.
Сложность Алгоритма: 2 цикла по n шагов => n^2
Алгоритм Флойда-Уоршелла:
Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти все кратчайшие расстояния, от каждого города до всех остальных городов.
Реализация:
Нет информации о маршруте, только кратчайшие расстояния!
for k: =1 to N
for i: = 1 to N
for j: = 1 to N
if W[i,j] > W[i,k] + W[k,j] then
W[i,j] := W[i,k] + W[k,j];
Если из вершины i в вершину j короче ехать через вершину k,мы едем через вершину k!
Версия с запоминанием маршрута:
for i:= 1 to N
for j := 1 to N
c[i,j] := i; // i–ая строка строится так же, как массив c в алгоритме Дейкстры
...
for k: =1 to N
for i: = 1 to N
for j: = 1 to N
if W[i,j] > W[i,k] + W[k,j] then begin
W[i,j] := W[i,k] + W[k,j];
c[i,j] := c[k,j];
end;
в конце цикла c[i,j] – предпоследняя вершина в кратчайшем маршруте из вершины i в вершину j
Сложность алгоритма: N^3
Задача коммивояжера
Коммивояжер (бродячий торговец) должен выйти из первого города и, посетив по разу в неизвестном порядке города 2,3,...N, вернуться обратно в первый город. В каком порядке надо обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?
Это NP-полная задача, которая строго решается только перебором вариантов (пока)!
Точные методы(большое время счета для больших N. Сложность N!):
1)простой перебор;
2)метод ветвей и границ;
3)метод Литтла;
4)…
Приближенные методы(не гарантируется оптимальное решение):
1)метод случайных перестановок (Matlab);
2)генетические алгоритмы;
3)метод муравьиных колоний;
4)…
27.
