Лекции.Орг

Поиск:




Пример (Задача о кратчайшем пути)




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

Рассмотрим задачу о кратчайшем пути в графе с неотрицательными весами дуг (рис.1). Ветвление в этой задаче - это выбор очередной дуги. В качестве нижней оценки примем суммарную длину частичного пути до некоторой вершины. На рис.2. приведены шаги ветвления в предположении, что ветвление производится для вершины из активного множества с наименьшей нижней оценкой. Шаги ветвления можно выразить схемой:

1.

2.

3.

на шаге 3 получен первый “рекорд” Это позволяет исключить из активного множества вершину

4. на этом шаге из активного множества исключаются вершины и

5. Поскольку в активном множестве нет вершин, процесс закончен.

Рис.1. Задача о кратчайшем пути.

 

Рис.2. Дерево поиска, полученное при условии, что ветвление производится в вершине наименьшей нижней границы. - “рекорд”.






Дата добавления: 2015-02-12; Мы поможем в написании ваших работ!; просмотров: 595 | Нарушение авторских прав | Изречения для студентов


Поиск на сайте:



© 2015-2022 lektsii.org - Контакты - Последнее добавление

Ген: 0.009 с.
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7