Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Поиск по графу в ширину





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1.

Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

26. Задача о минимальном остовном дереве: алгоритм Прима

Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному.

Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно).

Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов.

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

И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов.

Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины.

В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет.

27. Задача о минимальном остовном дереве: алгоритм Крускала

Вначале текущее множество рёбер устанавливается пустым.

Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству.

Когда таких рёбер больше нет, алгоритм завершён.

Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.

28. Задача о кратчайшем пути в графе: алгоритм Флойда

На каждом шаге алгоритм генерирует двумерную матрицу W, . Матрица W содержит длины кратчайших путей между всеми вершинами графа. Перед работой алгоритма матрицаW заполняется длинами рёбер графа.

for k = 1 to nfor i = 1 to nfor j = 1 to nW[i][j] = min(W[i][j], W[i][k] + W[k][j])

29. Задача о кратчайшем пути в графе: алгоритм Дейкстры

Если все вершины посещены, алгоритм завершается.

В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку.

Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u, назовем соседями этой вершины.

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

Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины.

Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

30. Задача о максимальном потоке в сети: варианты постановки задачи

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

Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.

· Произвольное число источников и/или стоков

· Неориентированные рёбра

· Ограничение пропускной способности вершин

 

31. Задача о максимальном потоке в сети: алгоритм решения

Алгоритм Форда:

Найти любой увеличивающий путь.

Увеличить поток по всем его рёбрам на минимальную из их остаточных пропускных способностей.

Повторять, пока увеличивающий путь есть.

Задача о наибольшемпаросочетании

Наибольшее паросочетание — это такое паросочетание, которое содержит максимальное количество ребер.

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.