Основы программирования. Пути на графах

Содержание

Слайд 2

Поиск кратчайших путей в графе

Поиск кратчайших путей в графе

 

Слайд 3

Алгоритм Дейкстры

Алгоритм Дейкстры

 

Слайд 4

Алгоритм Дейкстры

Алгоритм Дейкстры

 

Слайд 5

Алгоритм Дейкстры

Алгоритм Дейкстры

 

Слайд 6

Алгоритм Дейкстры

Алгоритм Дейкстры

 

Слайд 7

Алгоритм Дейкстры

Алгоритм Дейкстры

 

Слайд 8

Методы WGraph для алгоритма Дейкстры void WGraph::minpath(int s, double *D, int

Методы WGraph для алгоритма Дейкстры

void WGraph::minpath(int s, double *D, int

*P)
{ int i, j, w; double wmin;
bool *old = new bool[vernum];
for (i = 0; i < vernum; i++)
{ old[i] = false; D[i] = mat[s][i]; P[i]=s; }
old[s] = true; D[s] = 0;
for (i = 1; i < vernum; i++) {
for (w=-1, wmin=MAX, j=0; j if (!old[j] && D[j] < wmin)
{ w = j; wmin = D[j]; }
if (w < 0) break;
for (old[w] = true, j = 0; j < vernum; j++)
if (!old[j] && D[j] > D[w]+mat[w][j])
{ D[j] = D[w]+mat[w][j]; P[j] = w; }
} delete [] old;
}
Слайд 9

Выделение кратчайшего пути

Выделение кратчайшего пути

 

Слайд 10

Вычисление кратчайших расстояний от вершины s до всех остальных Матрица расстояний

Вычисление кратчайших расстояний от вершины s до всех остальных

Матрица расстояний в

общем случае несимметричная
s=0
+ вершина 3:
D
+ вершина 2:
D
+ вершина 1:
D
Слайд 11

Вычисление кратчайших расстояний от вершины s до всех остальных Матрица расстояний:

Вычисление кратчайших расстояний от вершины s до всех остальных

Матрица расстояний:
s=0
Кратчайшие расстояния

от вершины 0:
D
Кратчайшие пути от вершины 0 в обратном порядке:
P
Слайд 12

Алгоритм Флойда-Уоршалла

Алгоритм Флойда-Уоршалла

 

Слайд 13

Алгоритм Флойда-Уоршалла

Алгоритм Флойда-Уоршалла

 

Слайд 14

Алгоритм Флойда-Уоршалла

Алгоритм Флойда-Уоршалла

 

Слайд 15

Алгоритм Флойда-Уоршалла Вычисляется матрица весов всех кратчайших путей. double** WGraph::allminpath() {

Алгоритм Флойда-Уоршалла

Вычисляется матрица весов всех кратчайших путей.
double** WGraph::allminpath()
{ int i,

j, l;
double **W = new double* [vernum];
for (i = 0; i < vernum; i++)
W[i] = new double[vernum];
for (i = 0; i < vernum; i++)
for (j = 0; j < vernum; j++)
W[i][j] = mat[i][[j];
for (l = 0; l < vernum; l++)
for (i = 0; i < vernum; i++) {
if (W[i][l] < MAX)
for (j = 0; j < vernum; j++)
W[i][j]=min(W[i][j], W[i][l]+W[l][j]);
return W;
}
Слайд 16

Замечания к алгоритму Флойда-Уоршалла Алгоритм Флойда-Уоршалла –пример использования динамического программирования. Условия,

Замечания к алгоритму Флойда-Уоршалла

Алгоритм Флойда-Уоршалла –пример использования динамического программирования.
Условия, при

которых применимо ДП:
оптимизационная задача, для которой выполняется свойство оптимальности для подзадач;
относительно небольшое (полиномиальное от длины входа) число различных подзадач;
многократное решение одних и тех же подзадач при поиске общего решения на основе полного перебора вариантов – перекрывающиеся подзадачи.
Слайд 17

Замечания к алгоритму Флойда-Уоршалла Порядок решения задачи с помощью ДП: описать

Замечания к алгоритму Флойда-Уоршалла

Порядок решения задачи с помощью ДП:
описать структуру

оптимальных решений задачи и подзадач;
найти рекуррентное соотношение, связывающее оптимальные параметры\решения подзадач разных уровней;
двигаясь снизу вверх, от подзадач самого низкого уровня, вычислять их оптимальные параметры\решения только один раз и сохранять результаты в специальной таблице;
использовать данные из таблицы при поиске оптимального параметра\решения подзадач следующего уровня.
В приведенном алгоритме allminpath оптимальные решения подзадач разных уровней последовательно вычисляются в матрице W.
Слайд 18

Эйлеровы циклы и пути Эйлеров цикл в неориентированном графе: начинается в

Эйлеровы циклы и пути

Эйлеров цикл в неориентированном графе:
начинается в произвольной вершине

a
проходит по всем ребрам графа по одному разу
завершается в вершине a.
Условия существования эйлерова цикла:
граф является связным
степени всех вершин графа (число инцидентных ребер) четные (т.е. если существует ребро, по которому можно прийти в вершину, то всегда найдется ребро, по которому можно выйти).
Если в графе существуют ровно 2 вершины a и b с нечетными степенями, то можно найти эйлеров путь, который начинается в a, проходит по всем ребрам по одному разу и заканчивается в b.
Слайд 19

Идея алгоритма построения цикла/пути Вычисляются степени всех вершин. Если условия существования

Идея алгоритма построения цикла/пути

Вычисляются степени всех вершин. Если условия существования цикла/пути

не выполняются, то выход.
Выбирается произвольная вершина a (для цикла) или выделяются 2 вершины с нечетными степенями a и b (для пути).
Строится произвольный начальный (текущий) цикл из a или путь из a в b.
Для всех вершин v текущего цикла/пути (начиная с v=a) проверяется, есть ли еще не пройденные ребра, инцидентные v. Если есть, то выделяется побочный цикл, который начинается и заканчивается в v и проходит по не проверенным ранее ребрам. Далее побочный цикл включается в текущий непосредственно за вершиной v.
Слайд 20

Замечания по алгоритму Текущий путь и побочные циклы выгодно строить в

Замечания по алгоритму

Текущий путь и побочные циклы выгодно строить в виде

списков. Используем для этого класс List из раздела «Линейные списки». Элементы списков будут хранить номера пройденных вершин.
Для представления графа используем класс LGraph (списки смежных вершин).
Для исключения пройденных ребер можно просто удалять элементы в списках смежных вершин. Чтобы сохранить исходный массив списков lst, следует создать и модифицировать его копию, но для упрощения алгоритма мы используем сам lst.
Для вставки побочного цикла в текущий (вставки списка в список с заданной позиции) добавим в класс List новый метод insert(List &sec).
Слайд 21

Вставка побочного цикла в текущий

Вставка побочного цикла в текущий

Слайд 22

Вставка списка в список Вставка списка sec после текущего элемента (текущая

Вставка списка в список

Вставка списка sec после текущего элемента (текущая позиция

pcurpos не изменяется):
bool List::insert(List &sec)
{
if (!pcurpos || sec.is_empty())
return false;
(sec.pend)->next = pcurpos->next;
if (pcurpos == pend) pend = sec.pend;
pcurpos->next = sec.pbeg;
sec.pend = sec.pbeg = NULL;
return true;
}
bool List::is_empty()
{ return (!pbeg)? true : false; }
Слайд 23

Вспомогательные методы Проверка существования эйлерова цикла/пути и расчет начальной и конечной

Вспомогательные методы

Проверка существования эйлерова цикла/пути и расчет начальной и конечной вершины

(a и b, для цикла a=b=0).
bool LGraph::is_euler_path(int &a, int &b)
{ int i, k = 0;
for (i = 0; i < vernum; i++)
if (lst[i].getcount() % 2 == 1)
{ k++;
if (k == 1) a = i;
else if (k == 2) b = i;
else return false;
}
if (!k) a = b = 0;
return true;
}
Слайд 24

Вспомогательные методы Выделение произвольного пути из a в b (a=b в

Вспомогательные методы

Выделение произвольного пути из a в b (a=b в случае

цикла) с исключением просмотренных ребер. Путь формируется в виде списка пройденных вершин path.
void LGraph::get_path(int a, int b, List &path)
{ int i, vpre = a, vnex;
path.clear(); path.push_back(a);
while (true)
{
vnex = lst[vpre].pop_front();
lst[vnex].remove(vpre);
path.push_back(vnex);
if (vnex == b) break;
vpre = vnex;
}
}
- Предыдущая
Доступная среда в учреждениях культуры и спорта. Группа компаний «ИСТОК-АУДИО»
Следующая -
Основы программирования. Поиск на графах

Похожие презентации

Урок открытия нового знания - презентация для начальной школы_
Классификация страховых терминов
Увлажнитель воздуха с ночником
Классификатор бюджетных правонарушений и его применение органами государственного финансового контроля
Портреты эпохи Просвещения
Алгоритмические языки программирования
Портрет на фоне малой Родины
Деятельность саморегулируемых организаций по повышению качества работы кадастровых инженеров
Знакомство со Львовом
Правоохранительная деятельность, ее признаки, понятие и задачи. Органы, осуществляющие правоохранительную деятельность
Бином Ньютона. «Би»-удвоение, раздвоение … «Ном»(фран. nombre) –номер, нумерация. «Бином» -»два числа»
Подтягивание. Техники подтягивания
Кухня в традициях коми
Современное пятиборье
European law
Инициативное предложение Никитина Н. А.
Искусство XX века. Авангардизм
Управление процессом обучения на промышленном предприятии На материале ОАО «Каустик» Докладчик – начальник учебного центр
Исследование прочностных характеристик сердечников крестовин стрелочных переводов после упрочняющей обработки
Духовні святині Охтирщини
Теория и история религии
Общая физиология эндокринной системы
Денежная реформа Елены Глинской
Кәмелетке толмағандар қылмыстылығының себептері және оның алдын алу мәселелері
Культура, традиции, праздники в Бразилии
Сайт ГК. Контент. Рекламные блоки
Планирование питания туристов во время туристических походов и поездок
Машины постоянного тока
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть