Пример (Задача о кратчайшем пути)
Лекции.Орг

Поиск:


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




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

1.

2.

3.

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

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

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

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

 

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





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


Читайте также:

Рекомендуемый контект:


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



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

Ген: 0.002 с.