Методы решения NP-полных задач
Алгоритмы с возвратом
Метод ветвей и границ — частный случай метода поиска с ограничением. 1. Задание множества G (0) — множество всех циклов в графе 2. Задание множеств G (K), каждое из которых состоит из всех циклов, подчиненных одному из условий: ● из пункта i следует идти в пункт j для всех упорядоченных пар (i, j), входящих во множество P (V) (K) ● из пункта i запрещено идти в пункт j напрямую для всех (i, j), входящих в дополнение множества P (V) (K) 3. Вычисление оценок для G (0) Лемма: вычитая любое постоянное значение из всех элементов любой строки (столбца) матрицы C, мы оставим минимальный тур минимальным l(c 1, …, c n) = sum(h i ) + sum(h j ) + (c’i 1 i 2 + c’i 2 i 3 + c’i n i 1); hsum = sum(h i ) + sum(h j ) 4. Ветвление. G V (K) разбивается на 2 подмножества. По некоторому способу выбирают пару пунктов (r, m), не входящую в P V (K) и его дополнение: Первое получается при добавлении условия: из r в m нужно идти напрямую Второе получается при добавлении условия: из r в m напрямую идти запрещено Выбор r и m организован так, чтобы первое подмножество с большей вероятностью содержало оптимальный цикл, а второе не содержало. r выбирают так, чтобы (r, m)-й элемент матрицы равнялся нулю. 5. Преобразование матрицы расстояний при ветвлении и пересчет оценок G V2(i, j) = G V (K)(i, j) если (i, j) != (r, m) или inf в ином случае
|
|
|
Гамильтонов путь в графе G — это путь, содержащий все вершины графа G. Гамильтоновым циклом в графе G называется цикл, содержащий все вершины графа G.Проблема существования гамильтонова пути принадлежит к классу NP-полных задач. Генерируем все (n!) различных последовательностей вершин и для каждой из них проверяем, определяет ли она гамильтонов путь. Такие действия требуют по меньшей мере (n*n!) шагов, но функция подобного вида растет быстрее, чем произвольная экспоненциальная функция a^n. Общим методом организации исчерпывающего поиска и позволяющим значительно сократить число шагов в алгоритмах типа полного перебора всех возможностей является так называемый возвратный ход по упорядоченному множеству частичных возможных решений. Этот метод — метод поиска с возвращением — основан на том, что мы многократно пытаемся расширить текущее частичное решение, или, что то же самое, сузить множество тех возможных полных решений, которые не противоречат текущему частичному решению. Если расширение невозможно на текущем шаге поиска, то происходит возврат к предыдущему более короткому частичному решению и делается попытка его расширения, но уже другим способом. Вход : граф G=<V, E>, представленный списками инцидентности rec[v]. Результаты: список всех гамильтоновых циклов графа. Procedure GAMILT (k); /* генерирование всех гамильтоновых циклов, являющихся расширением последовательности <x[1], ..., x[k-1]>, массив x - глобальный */ begin for y in rec [x[k-1]] do if (k=n+1) and (y=V0) then write (x[1], ..., x[n], V0); else if DOP[y] then begin x[k]:=y; DOP[y]:=FALSE; GAMILT (k+1);
|
|
|
DOP[y]:=TRUE end end; /* end GAMILT */ begin /* главная программа */ for v in V do DOP[v]:=TRUE; /* инициализация */ x[1]:=V0; /* V0 - произвольная фиксированная вершина графа */ DOP[V0]:=FALSE; GAMILT (2) end.
Алгоритм Дейкстры находит в графе кратчайший путь между двумя вершинами S и T при условии положительных весов ребер. G = <V, E>, S->T.В алгоритме 2 части: 1. отыскание длины кратчайшего пути выставлением меток 2. отыскание самого пути обратным ходом1. y = S, d(y) = d(S) = 0, d(x) = inf 2. для всех вершин x, смежных с y и не имеющих постоянной метки, пересчитываем d(x): d(x) = min{ d(x), d(y) + a(y, x) } если d(x) = inf для всех непомеченных вершин x, то закончить процедуру, т.к. в исходном графе нет пути из S в T иначе выбираем ту из x, которая имеет наименьшую из временных меток, т.к. d(y) = min{ d(x) } 3. если y = T — закончить, иначе вернуться в 2.
|
|
|
Представления графов, их достоинства и недостатки.
Матрица инциденций NxM (N вершин, M ребер) В случае неориентированного графа столбец содержит единицы в строках, соответствующих инцидентным вершинамДля ориентированного графа: -1 для начала дуги, 1 для конца дугиПетлю удобно представлять каким-нибудь другим значением в матрице. Алгоритмически это худший способ: 1. размер NxM, а большая часть матрицы — нули 2. неудобный доступ к информации; чтобы узнать, существует ли ребро между вершинами, может потребоваться до m шагов.Матрица смежности (NxN) Ячейка матрицы ij имеет значение 1, если существует ребро между вершинами i и j, иначе 0. Недостаток: объем памяти не зависит от количества ребер, особенно для ориентированного графа Список ребер Пары соответствий. Недостаток: большое число шагов (порядка M) для получения множества вершин, к которым ведут ребра из данной. Список инцидентности . Каждая вершина ассоциируется со связным списком смежных с ней вершин и хранит информацию о принадлежащих графу вершинах
Методы решения NP-полных задач
Жадные (градиентные) методы . На каждой стадии жадный алгоритм выбирает тот вариант, который локально оптимален, с расчетом на оптимальность всего решения. Сравнение DP и жадных методов: 1. жадные быстрее, но не всегда дают оптимальное решение 2. DP принимает решение, просчитав все варианты; жадный алгоритм берет на каждом шаге локально лучший вариант.Методы случайного поиска основаны на том, что генерируется случайная последовательность, которая проверяется на решение. Из множества найденных так решений выбирается лучшее. Дальнейшим развитием жадных алгоритмов является их вероятностный вариант GRASP. Это итеративный алгоритм, который состоит из стадий: 1. конструирование возможного решения 2. локальный поиск, в которой ищется локальный оптимум в окрестностях построенного решения На первой стадии возможные решения строятся по одному элементу. На каждой итерации составляется список лучших кандидатов в зависимости от коэффициента alpha, который регулирует перекос алгоритма к жадному или случайному. Первый подходящий (FF) и прочие. Данные методы основаны на выборе первого подходящего решения по какому-то критерию.
|
|
|
Эйлеров путь — путь, проходящий через каждое ребро графа в точности 1 раз. Если путь заканчивается в стартовой вершине, то это эйлеров цикл . Если граф содержит эйлеров цикл, то это эйлеров граф . Принцип алгоритма: пусть V 0 — выбранная начальная вершина. Цикл начинает строить путь из выбранной вершины, причем вершины пути помещаются в промежуточный стек, а не удаляются из графа. Эти действия продолжаются, пока не станет невозможным удлинить путь включением вершины. Т.о. из начального графа был удален цикл C 1 , вершины которого помещены в S. 1. в цикл вошли все ребра G — это и есть эйлеров цикл.
Дата добавления: 2020-04-08; просмотров: 111; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!