Запишем тему урока: « Поиск кратчайших путей в графе» Виды алгоритмов: «жадный алгоритм» - алгоритм состоит в том, чтобы на каждом шаге многоходового процесса выбирать наилучший в данный момент вариант, не думая о том, что впоследствии этот выбор может привести к худшему решению (алгоритм, который, на каждом шагу принимают локально оптимальное решение, не заботясь о том, что будет дальше) сформулируйте алгоритм Прима-Крускала - это «жадный» алгоритм, который всегда приводит к правильному решению. В теории графов – это построение минимального основного дерева, т.е. дерева, связывающего все вершины 1.начальное дерево – пустое 2.на каждом шаге добавляется ребро минимального веса, которое ещё не входит в дерево и не приводит к появлению цикла в чем заключается алгоритм Дейкстра? - алгоритм, нахождения кратчайшего расстояния от одной из вершин графа до всех остальных Вывод: не всякий алгоритм дает оптимальное решение. Решим следующую задачу: граф рисую на доске требуется найти кратчайшее расстояние от 1-й вершины до 6 используя «жадный алгоритм». 1) Жадный алгоритм Ответ: 1 - 6 = 19 Жадные алгоритмы – это общее название подхода к решению задач оптимизации. Вопрос: в какой области науки решают задачи по оптимизации? 2)Алгоритм Прима-Крускала Общая длина равна 33. 3) 1 | 2 | 3 | 4 | 5 | 6 | 0 | | | | | | | 7 | 9 | | | 14 | | | 9 | 22 | | 14 | | | | 20 | | 11 | | | | 20 | 20 | | | | | | 20 | | Результат работы алгоритма: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11. Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины. Так, вершина 5 имеет длину пути 20. Она связана с вершинами 6 и 4. Для вершины 6 получим вес 20 — 9 = 11 (совпал). Для вершины 4 получим вес 20 — 6 = 14 (не совпал). Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути. Далее определяем ребро, через которое мы попали в вершину 6. И так пока не дойдем до начала. Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину. |