русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Взвешенные графы и алгоритмы поиска кратчайшего пути.


Дата добавления: 2015-07-23; просмотров: 1563; Нарушение авторских прав


До сих пор нас интересовали вершины и ребра графа, по которым можно перемещаться. Теперь нас будет интересовать, как наилучшим способом осуществить перемещение из точки А в точку В. Возникает вопрос, что значит «наилучшим способом». Это может быть самый дешевый путь. самый короткий путь, или путь, выбранный с каким – то другим критерием. В дальнейшем для общности мы будем говорить о наилучшем или кратчайшем пути. Для определения кратчайшего пути присвоим каждому ребру вес или меру. Если попытаться найти кратчайшее расстояние между двумя городами, то города можно интерпретировать как вершины графа, а веса как расстояния между городами, которые мы будем проезжать .Если найти самый дешевый способ перелета из одного города в другой, то вес ребер между вершинами, представляющими города, будет стоимостью перелета из города в город. Если прямого перелета из города в город нет, то не будет и ребра между соответствующими вершинами. Для упрощения в дальнейшем будем рассматривать вес ребра как расстояние между городами, а наилучший путь из точки А в точку В как кратчайший путь между А и В.

Определение.

Граф, каждому ребру которого поставлено в соответствие некоторое число, называется взвешенным графом. Число, поставленное в соответствие ребру, называется весомэтого ребра.

Одной из важнейших задач в теории взвешенных графов является задача о кратчайшем соединении, основанная на применении алгоритма Краскала. Краскал (род. в 1928 г. в Нью-Йорке. рассматриваемый далее алгоритм был предложен Краскалом еще на втором курсе университета.

Теорема (алгоритм Краскала).

Последовательность дуг покрывающего дерева минимального веса мжожепт быть найдена с помощью следующего алгоритма:

  1. v1 – дуга наименьшего веса из всех имеющихся, не являющаяся петлей;
  2. если уже определен начальный отрезок последовательности v1, v2, ..., vk-1, то дуга vk

а) добавление дуги vк не приводит к образованию цикла;



b) из всех дуг, удовлетворяющих условию а), дуга vk - обладает наименьшим весом.

Применим алгоритм Краскала к графу, изображенному на рисунке. Пусть А, В, С, D, E, F – населенные пункты, линии – проектируемые участки дорог, цифры над линиями – их стоимость.

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

6 C

B 1

5 3

D

1 3 F 4 3

A E

 

В нашем случае выбираем v1 = CD, v2 = AB, v3 = ED далее отпадает возможность выбора CE, т.к. приводит к образованию цикла. Далее v4 = CF и отпадает возможность выбора EF, v5 = AF, отпадает возможность выбора BC, BF, AE и процесс выбора дуг автоматически оборвался. Полученный путь изображен на рисунке. Пунктиром обозначены дуги, не вошедшие в этот маршрут. Полученный путь изображен на рисунке.

B C

5 1

 

1 F D

4 3 2

A E



<== предыдущая лекция | следующая лекция ==>
Некоторые общие понятия теории графов. | Задача о кратчайших путях.


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.076 сек.