рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Охрана труда
- /
- Алгоритм поиска кратчайших расстояний в графе
Реферат Курсовая Конспект
Алгоритм поиска кратчайших расстояний в графе
Алгоритм поиска кратчайших расстояний в графе - раздел Охрана труда, Оглавление Алгоритм Поиска Кратчайших Расстояний В Графе. 1 ...
Оглавление
Алгоритм поиска кратчайших расстояний в графе. 1
Алгори́тм Де́йкстры.. 1
Задача о кратчайшем пути. 4
Задача о максимальном потоке. 4
Задача линейного программирования при максимизации потока. 6
Контрольные вопросы.. 6
Лекция №22Поиск в ширину и в глубину в графе. Построение остовного дерева графа. Алгоритм поиска кратчайших расстояний в графе. Поиск Эйлерова пути в графе.
Графы широко используются как в самой математике, так и в ее приложениях. Они применяются при построении различных математических моделей: линий электропередачи, сетей автодорог, линий воздушных сообщений и пр.Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время).Исходные данные – это граф, дугам которого приписаны положительные числа – затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги – туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б – в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А. Многие постановки экономического содержания сводятся к задаче коммивояжера. Например:- составить наиболее выгодный маршрут обхода наладчика в цехе (контролера, охранника, милиционера), отвечающего за должное функционирование заданного множества объектов (каждый из этих объектов моделируется вершиной графа);- составить наиболее выгодный маршрут доставки деталей рабочим или хлеба с хлебозавода по заданному числу булочных и других торговых точек (парковка у хлебозавода).
Рассмотрим несколько типичных задач принятия решений, связанных с оптимизацией на графах.
Алгори́тм Де́йкстры
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных. Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами…Задача о кратчайшем пути
Рис.7. Исходные данные к задаче о кратчайшем пути. Ситуацию можно описать не только ориентированным графом с весами, приписанными дугам, но и таблицей (табл.8).Задача о максимальном потоке
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число - пропускная… Рис.8. Исходные данные к задаче о максимальном потокеЗадача линейного программирования при максимизации потока
Х01 +Х02+Х03=F (0) - Х01 + Х12 + Х13 +Х14 = 0 (1) - Х02 - Х12 + Х23 + Х24 = 0 (2) -Х03-Х13-Х23+Х34= 0 (3) -Х14-Х24-Х34=-F (4) Х01 ≤ 2 Х02 ≤ 3 Х03 ≤ 1Контрольные вопросы
- Дайте определение алгоритму поиска в графах.
- Принцип работы алгоритма Дейкстры.
- Сформулировать задачу о кратчайшем пути. Область применения.
- Сформулировать задачу о максимальном потоке. Область применения.
- Сформулировать задачу линейного программирования при максимизации потока. Область применения.
– Конец работы –
Используемые теги: Алгоритм, поиска, кратчайших, расстояний, графе0.082
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм поиска кратчайших расстояний в графе
Что будем делать с полученным материалом:
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.158 сек.
Новости и инфо для студентов