Правило I. ни один из маршрутов не может стоить меньше, чем половина суммы по всем узлам n стоимости 2-х ребер наименьшей стоимости, инцидентных узлу n в графе

Метод ветвей и границ

Широкий спектр задач (не только игровых), в которых нужно найти минимальную или максимальную конфигурацию того или иного типа, поддаются решению путём поиска с возвратами, применимого к дереву возможностей.

Будем считать, что узел n дерева – некоторая совокупность конфигураций, каждый сын узла n – некоторое подмножество этой совокупности. Каждый лист – отдельное решение задачи. Каждое решение можно оценить и выяснить, не является ли оно наилучшим среди уже найденных.

Пример 1. Рассмотрим задачу коммивояжёра для следующего графа

Начало дерева решений имеет вид:

(означает, что включено в маршрут, означает, что не включено)

A

Все маршруты

J

B

C

K

D

E

Метод границ

Рассмотрим способ определения нижней границы стоимости для совокупности решений задачи, представленной узлом n

1) Стоимость любого маршрута n ₀ n ₁… n_k можно определить как половину суммы по всем узлам стоимости ребер маршрута, инцидентных с n.

Например,

n₀

n₁

n₂

c₁

c₂

c₃

c₄

n₃

2) Далее сумма стоимостей двух рёбер инцидентных узлу n_i в маршруте не может быть меньше, чем сумма стоимостей двух ребер наименьшей стоимости во всем графе, инцидентных с n_i

Из 1) и 2) следует, что

Пример 2: Нижняя граница стоимости для маршрута в графе из Примера 1.

Для узла a: два ребра наименьшей стоимости из всех ребер графа ab и ad стоят 2 и 3

Для узла b: ab и be стоят 3 и 3

Для узла c: ac и bc стоят 4 и 4

Для узла d: ad и cd стоят 2 и 5

Для узла e: be и de стоят 3 и 6

Ни один из маршрутов в графе не может стоить меньше, чем

3) Получим нижнюю границу стоимости не всего множества маршрутов, а некоторого их подмножества, определяемого узлом дерева из Примера 1.

Например, узлом – маршруты, содержащие ac и не содержащие ab.

Для этого в правиле I при выборе двух ребер наименьшей стоимости, инцидентных какому-нибудь узлу никогда не выбирается ab и обязательно включается ac, если оно инцидентно данному узлу.

Пример 3: Нижняя граница стоимости маршрутов узла J дерева решений из Примера 1.

Для узла a: два ребра наименьшей стоимости ad и ac стоят 2 и 4 (ab брать нельзя, ac - включать обязательно).

Для узла b: be и bc стоят 3 и4 (ab брать нельзя).

Для узла c: ac и bc стоят 4 и 4 (ac включать обязательно).

Для узла d: ad и cd стоят 2 и 5.

Для узла e: be и de стоят 3 и 6.

Таким образом, нижняя граница стоимости любого маршрута, содержащего ac и не содержащего ab равна

Метод ветвей. При построении дерева решений при каждом разветвлении (определении 2-х сыновей данного узла) принимается решение о том, какие ребра необходимо включить или исключить из маршрутов представленных этими сыновьями используются правила:

Правило II.

Дата добавления: 2014-01-04