62. Нахождение кратчайших путей в графе. Алгоритм Форда – Беллмана. Алгоритм беллмана рюкзак


Методы решения задачи о рюкзаке

альное время, но это далеко не так. Задача называется NP - полной, если для нее не существует полиномиального алгоритма.[3] Алгоритм называется полиномиальным, если его сложность O(N) в худшем случае ограничена сверху некоторым многочленом (полиномом) от N. Такие задачи возникают очень часто в различных областях: в булевой логике, в теории графов, теории множеств, кодировании информации, в алгебре, в биологии, физике, экономике, теории автоматов и языков. Считается что NP - полные задачи очень трудноразрешимы, а так же, что если хотя бы для одной из них удастся найти полиномиальный алгоритм, то такой алгоритм будет существовать для любой задачи из этого класса. Над поиском полиномиальных алгоритмов к таким задачам трудились многие ученые, и все же и все же при таком разнообразии NP - полных задач, ни для одной из них до сих пор не найдено полиномиального алгоритма.[10]. Из всего вышесказанного следует, что если известна NP - полнота задачи, то лучше потратить время на построение приближенного алгоритма, чем пытаться построить полиномиальный, или же, если это позволяют условия, использовать алгоритмы с экспоненциальной сложностью работы

 

Глава 2 Методы решения задачи о рюкзаке

 

2.1 Классификация методов

 

На практике очень часто возникают NP-полные задачи, задач о рюкзаке одна из них . Конечно надежд, на то что для них найдется полиномиальный алгоритм практически нет, но из этого не следует что с задачей нельзя ничего сделать. Во первых, очень часто удается построить полиномиальный алгоритм для NP полной задачи, конечно он даст приближенное, а не точное решение, но зато будет работать за реальное время. Во вторых, данные могут быть таковы, что экспоненциальный алгоритм, например переборный сможет работать на них разумное время. К точным методам относятся: Полный перебор, метод ветвей и границ, ДП программирование. К приближенным: Жадные алгоритмы. Полный перебор перебор всех вариантов (всех состояний) малоэффективный, но точный метод. Метод ветвей и границ по сути сокращение полного перебора с отсечением заведомо “плохих” решений. ДП алгоритм, основанный на принципе оптимальности Беллмана. Жадный алгоритм основан на нахождении относительно хорошего и “дешевого” решения.

 

2.2 Динамическое программирование

 

В основе метода динамического программирования лежит принцип оптимальности Беллмана:”Каково бы ни было состояние системы перед очередным шагом, надо выбирать управление на этом шаге так, чтобы выигрыш на этом шаге плюс оптимальный выигрыш на всех последующих шагах был оптимальным”. Проще говоря оптимальное решение на i шаге находится исходя из найденных ранее оптимальных решений на предшествующих шагах. Из этого следует, что для того чтобы найти оптимальное решение на последнем шаге надо сначала найти оптимальное решения для первого, затем для второго и так далее пока не пройдем все шаги до последнего.

Имеется набор из N предметов. Пусть MaxW - объем рюкзака, Pi стоимость i-го предмета, Wi вес i-го предмета. Value [W, i] максимальная сумма, которую надо найти. Суть метода динамического программирования на каждом шаге по весу 1<Wi<W находим максимальную загрузку Value[Wi, i], для веса Wi. Допустим мы уже нашли Value[1..W, 1..i-1], то есть для веса меньше либо равного W и с предметами, взятыми из 1..N-1. Рассмотрим предмет N, если его вес WN меньше W проверим стоит ли его брать.

Если его взять то вес станет W-Wi , тогда Value[W, i] = Value[W Wi , i-1] + Pi (для Value[W Wi , i-1]) решение уже найдено остается только прибавить Pi.

Если его не брать то вес останется тем же и Value[W , i] = Value[W Wi , i-1]. =Из двух вариантов выбирается тот, который дает наибольший результат. Рассмотрим алгоритм подробнее.

 

Рис 1.1

-

Рис 1.2

 

Рис 1.3

 

Динамическое программирование для задачи о рюкзаке дает точное решение, причем одновременно вычисляются решения для всех размеров рюкзака от 1 до MaxW, но какой ценой? Для хранения таблицы стоимости и запоминания того, брался каждый предмет или нет, требуется порядка O(N*MaxW) памяти, временная сложность равна O(N*MaxW) ;

Опишем основную логику решения: {Загружаем рюкзак если его вместимость = Weight} for Weight:=1 to MaxW do begin

for i:=1 to N do {берем предметы с 1 по N}

{если вес предмета больше Weight}

{или предыдущий набор лучше выбираемого}

if (W[i]>Weight) or (Value[Weight, i-1] >=

Value[Weight-W[i], i-1]+P[i]) then begin

{Тогда берем предыдущий набор}

Value[Weight, i]:=Value[Weight, i-1];

{говорим что вещь i не взята}

Take [Weight, i]:= false;

End

{иначе добавляем к предыдущему набору текущий

предмет}

Else begin

Value [Weight, i]:=Value [Weight - W[i], i-1]

+P[i];

{говорим что вещь i взята}

Take [Weight, i]:= true;

End;

End;

Как было сказано ранее, алгоритм динамического программирования для рюкзака дает точное решение путем использования дополнительной памяти O(N*MaxW), временная сложность алгоритма так же будет порядка O(N*MaxW).

2.3 Полный перебор

 

Название метода говорит само за себя. Чтобы получить решение нужно перебрать все возможные варианты загрузки. Здесь мы будем рассматривать такую постановку задачи. В рюкзак загружаются предметы N различных типов (количество предметов каждого типа не ограничено), каждый предмет типа I имеет вес Wi и стоимость Pi , i=(1,2..N). Требуется определить максимальную стоимость груза вес, которого не превышает W. Очевидна простая рекурсивная реализация данного подхода Рис 1.4. Временная сложность данного алгоритма равна O(N!). Алгоритм имеет сложность

www.studsell.com

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

Будем рассматривать ориентированные графы G = <V, Е>, дугам которых приписаны веса. Это означает, что каждой дуге (u, v)E поставлено в соответствие некоторое вещественное число a(u, v), называемое весом данной дуги. Полагаем, что a(u, v)=, если не существует дуга (u, v). Если последовательность вершин Vq , V1,..., Vp определяет путь в графе G, то его длина определяется как сумма . Нас будет интересовать нахождение кратчайшего пути между двумя фиксированными вершинами s, t V. Длину такого пути обозначим d(s, t) и назовем расстоянием от s до t (расстояние, определенное таким образом, может быть и отрицательным). Если не существует ни одного пути из s в t, то полагаем d(s, t) =. Отметим, что если каждый контур нашего графа имеет положительную длину, то кратчайший путь будет всегда элементарным путем.

Для произвольных s, t V (st) существует вершина v такая, что d(s, t) = d(s, v) + d(v, t).

Таким свойством обладают предпоследние вершины кратчайшего пути из s в t. Далее мы можем найти вершину и, для которой d(s, v) = d(s, u) + d(u, v) и т.д. Из условия положительности длины всех контуров следу­ет, что последовательность t, v, u, ... не содержит повторений и заканчивается вершиной s. Перечислив верши­ны в обратном порядке, найдем кратчайший путь из s в t.

Алгоритм для нахождения кратчайшего пути можно построить с использованием стека, куда последова­тельно заносим вершины t, v,u, ..., s:

1 BEGIN

  1. СТЕК :=; СТЕК  t; v := t;

  2. WHILE vs DO

  3. BEGIN

  1. u := вершина, для которой d[v] = d[u] + a[u, v]

  2. СТЕК  u;

  3. v := u

8 END

9 END

Отметим, что если выбор вершины и в строке 5 происходит в результате просмотра всех вершин, то слож­ность нашего алгоритма - 0(n2). Если же будем просматривать только список ПРЕДШ[у], содержащий все вершины и, такие, что u—>v, то сложность будет О(m).

Алгоритм Форда-Беллмана.O(n3) При данной матрице весов дуг a[u, v], u, ve V, вычисляем некоторые верхние ограничения d[v] на расстоя­ния от вершины s до всех v е V.

Каждый раз, когда окажется, что D[u]+a[u, v]<D[v] (1), оценку D[v] улучшаем: D[v] := D[u]+a[u, v]. Про­цесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Легко показать, что значение каждой из переменных D[v] в этом случае равно кратчайшему пути от s к v.

Таким образом для вычисления расстояния от s до t мы находим расстояние от s до всех вершин графа. Алгоритм Belman-Ford(G,A,S,t)1.for each vV do d[v] 2.d[S]<- 0; 3.for k=1 to n-1 do 4.for each vV-{S} do 5.for each wV do if d[v]>d[w]+a[w,v] then d[v] d[w]+a[w,v] end for;end for; end for.

63 Поиск кратчайших путей в графе. Алгоритм Дэйкстры.

Общая теория:

У нас есть граф G=(V,E), где связь между вершинами v и w следующая: a(v,w) E. Если связь между вершинами отсутствует, то a(v,w)=.

Если последняя вершина wo, w1, …, wnопределяет путь в графе, то его длина равна суммарному весу входящих вершин:

Наша задача – нахождение кратчайшего пути между вершинами S, t. M(S,t) – расстояние между S и t.

Путь из S в t, который имеет минимальную длину – есть кратчайший путь, между вершинами S и t.

d(S,t)=d(S,vk) + a(vk,t)

d(S,vk)=d(S,vk-1)+a(vk-1,vk)

vk-1 vk

t

S

Алгоритм Дейкстры позволяет найти путь с не отрицательными весами.

Алгоритм Dijkstra (G,A,S)

  1. for each v V do d[v];

  2. d[s]0; //путь до вершины S

  3. S; //множество вершин с известным расстоянием

  4. tv; //множество вершин с не известным расстоянем

  5. while T0 do;

  6. d[w]=min {d[p], p T};

  7. SSV{w}; TT-{w};

  8. for each v T do;

  9. if d[v] > d[w]+a[w,v] then;

  10. d[v] d[w] + a[w,v];

  11. end for;

  12. end while;

  13. return d.

# A 3 B 2

4 9 E

S 2 2

3

C 3 D

d[S]=0; d[A]=; d[B]=; d[C]=; d[D]=; d[E]=;

S; T={S, A, B, C, D, E};

d[A]=min{d[A], d[S] + a[S,A]=4};

d[B]=min{d[B], d[S] + a[S,B]=9};

d[C]=3; – Минимальное значение переносим во множество S;

d[D]=;

d[E]=;

S={S,C} T={A,B,D,E};

Пересчитываем

d[A]=min{d[A], d[C] + a[C,A]}=min{4, 3 + } = 4;

d[B]=min{d[B], d[C] + a[C,B]}=min{9, 3 + }=9;

d[D]=min{d[D], d[C] + a[C,D]}=min{, 3 + 3}=6;

d[E] =;

S={S,C,A} T={B,D,E};

Пересчитываем

d[B]=min{d[B], d[А] + a[А,B]}=min{9, 3 + 4}=7;

d[D]=min{d[D], d[А] + a[А,D]}=min{6, 4 + 2}=6;

d[E] =;

S={S,C,A,D} T={B,E};

Пересчитываем

d[B]=min{d[B], d[D] + a[D,B]}=min{7, 6 + }=7;

d[E] = min{d[E], d[D] + a[D,E]}=8;

S={S,C,A,D,B} T={E};

Пересчитываем

d[E] = min{d[E], d[B] + a[B,E]}=min{9,8}=8;

S={S,C,A,D,B,E} T=;

studfiles.net

Алгоритм Беллмана-Форда Алгоритм маршрутизации алгоритм Беллмана Форда был

Алгоритм Беллмана-Форда Алгоритм маршрутизации (алгоритм Беллмана– Форда) был впервые разработан в 1969 году, как основной для сети ARPANET.

Алгоритм Беллмана–Форда — алгоритм поиска кратчайшего пути во взвешенном графе. За время O(|V| × |E|) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана–Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

Максимальная пропускная способность графа Рассмотрим алгоритм Форда на примере графа изображенного на рис. 1. Допустим, у нас исток будет в 1 узле, а сток в 4 узле. Алгоритм можно разбить на три шага:

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

Шаг 2 Нахождение в выбранном пути ребра с минимальной пропускной способностью. Прибавляем значение этого ребра к пропускной способности, которая в начале выполнения алгоритма равна 0.

Шаг 3 Вычитание из всех значений ребер пути, значения минимального ребра этого пути. При этом само ребро обратиться в 0 и его уже нельзя учитывать в дальнейшем. Далее продолжаем с шага 1.

В начале у нас пропускная способность равна 0 (P=0). Допустим, мы нашли путь из истока 1 в сток 4 через вершины 2 и 3, т. е. весь путь можно записать как (1 -2 -3 -4). В этом пути минимальное ребро соединяет вершины 2 и 3, его значение 5, увеличиваем пропускную способность на 5 (Р=5). Вычитаем 5 из ребер соединяющих вершины 1 и 2, 2 и 3, 3 и 4. Из исходного графа у нас выпадает ребро соединяющее вершины 2 и 3.

Получился граф изображенный на рис. 2. В этом графе снова ищем произвольный путь из 1 в 4. Нашли (1 -2 -5 -4), где минимальное ребро соединяет 2 и 5, его значение 6. Увеличиваем пропускную способность на 6 (P=5+6=11).

Вычитаем 6 из всех ребер пути, выпадает ребро 2 -5 (рис. 3). На следующем шаге находим путь (1 -6 -5 -4), минимальное ребро 1 -6 равно 7, тогда P=11+7=18.

Вычитаем из ребер пути 6, при этом выпадает ребро 1 -6 и граф распадается на две компоненты рис. 4. Мы не находим пути из истока в сток и алгоритм завершается. Получаем максимальную пропускную способность из 18.

Решение задачи на графе без отрицательных циклов Дан ориентированный или неориентированный граф G со взвешенными рёбрами. Длиной пути назовём сумму весов рёбер, входящих в этот путь. Требуется найти кратчайшие пути от выделенной вершины S до всех вершин графа. Кратчайших путей может не существовать. Так как, в графе, содержащем цикл с отрицательным суммарным весом, существует сколь угодно короткий путь от одной вершины этого цикла до другой (каждый обход цикла уменьшает длину пути). Цикл, сумма весов рёбер которого отрицательна, называется отрицательным циклом.

Здесь V — множество вершин графа G, E — множество его рёбер, а w — весовая функция, заданная на ребрах графа. Внешний цикл выполняется раз, поскольку кратчайший путь не может содержать большее число ребер, иначе он будет содержать цикл, который точно можно выкинуть. Вместо массива d можно хранить всю матрицу A, но это требует O(V²) памяти. Зато при этом можно вычислить и сами кратчайшие пути, а не только их длинны.

Чтобы вычислить и сами кратчайшие пути, а не только их длины мы заведем матрицу Pij. Если элемент Aij содержит длину кратчайшего пути из s в i, содержащего j рёбер, то Pij содержит предыдущую вершину до i в одном из таких кратчайших путей (ведь их может быть несколько).

После выполнения этого алгоритма элементы содержат длины кратчайших путей от s до i с количеством ребер j, и из всех таких путей следует выбрать самый короткий. А сам кратчайший путь до вершины i с j ребрами восстанавливается так:

Граф с отрицательными циклами Алгоритм Беллмана–Форда позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Достаточно произвести внешнюю итерацию цикла не |V|-1 , a ровно |V| раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из s. На основе этого можно предложить следующую оптимизацию: отслеживать изменения в графе и, как только они закончатся, сделать выход из цикла (дальнейшие итерации будут бессмысленны).

present5.com