Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.5. Пример из раздела 7.2 с улучшенной границей

Рассмотрим еще раз пример из раздела 7.2, используя улучшенную границу, описанную выше (вместо использования в качестве такой границы просто значения решения задачи о назначениях). Граница, соответствующая начальной задаче с матрицей весов (разд. 7.2), должна тогда быть (Необходимо второе стягивание, и решение новой задачи о назначениях равно 13.) Подзадачи получены, как и раньше,

но новой границей для подзадачи С будет вместо предыдущего значения 248. Новой границей для подзадачи будет то же, что и раньше. (Граница для В останется, конечно, неизменной, так как решение задачи В является на самом деле гамильтоновым циклом. Теперь ветвление нужно делать в узле как а не в С, как в предыдущем случае. Это ветвление приводит, как и прежде, к подзадачам , и наилучшее решение (подзадача имеет значение 251.

Рис. 10.26. Поиск с деревом решений из примера 7.2 с улучшенной границей для задачи о назначениях.

Дальнейшее ветвление в С (где решение не является гамильтоновым циклом) уже не будет необходимым, так как его нижняя граница, а именно 254, больше чем 251. Прежняя граница для С, равная 248 (меньше 251), была недостаточной для того, чтобы прекратить ветвление в этом узле. Таким образом, улучшенная граница позволяет сэкономить два узла в дереве решений поиска, как это показано на рис. 10.26. Это дает экономию только на 2/9 для этой маленькой задачи, но для задач большого размера получается большой процент экономии узлов дерева, т. е. числа задач на назначениях, которые следует решить

8. Задачи

(см. скан)

(см. скан)

(см. скан)

9. Список литературы

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление