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

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

1. Пример (Задача о кратчайшем пути) - student2.ru Пример (Задача о кратчайшем пути) - student2.ru Пример (Задача о кратчайшем пути) - student2.ru

2. Пример (Задача о кратчайшем пути) - student2.ru Пример (Задача о кратчайшем пути) - student2.ru Пример (Задача о кратчайшем пути) - student2.ru

3. Пример (Задача о кратчайшем пути) - student2.ru Пример (Задача о кратчайшем пути) - student2.ru Пример (Задача о кратчайшем пути) - student2.ru

на шаге 3 получен первый “рекорд” Пример (Задача о кратчайшем пути) - student2.ru Это позволяет исключить из активного множества вершину Пример (Задача о кратчайшем пути) - student2.ru

4. Пример (Задача о кратчайшем пути) - student2.ru Пример (Задача о кратчайшем пути) - student2.ru на этом шаге из активного множества исключаются вершины Пример (Задача о кратчайшем пути) - student2.ru и Пример (Задача о кратчайшем пути) - student2.ru

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

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

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

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

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

Наши рекомендации