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

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

1.

2.

3.

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

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

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

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

 

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