Правило I. ни один из маршрутов не может стоить меньше, чем половина суммы по всем узлам n стоимости 2-х ребер наименьшей стоимости, инцидентных узлу n в графе.
Метод ветвей и границ
Широкий спектр задач (не только игровых), в которых нужно найти минимальную или максимальную конфигурацию того или иного типа, поддаются решению путём поиска с возвратами, применимого к дереву возможностей.
Будем считать, что узел n дерева – некоторая совокупность конфигураций, каждый сын узла n – некоторое подмножество этой совокупности. Каждый лист – отдельное решение задачи. Каждое решение можно оценить и выяснить, не является ли оно наилучшим среди уже найденных.
Пример 1. Рассмотрим задачу коммивояжёра для следующего графа
Начало дерева решений имеет вид:
( означает, что включено в маршрут, означает, что не включено)
| A |
| Все маршруты |
| J |
| B |
| C |
| K |
| D |
| E |
Метод границ
Рассмотрим способ определения нижней границы стоимости для совокупности решений задачи, представленной узлом n
1) Стоимость любого маршрута n0n1…nk можно определить как половину суммы по всем узлам стоимости ребер маршрута, инцидентных с n.
Например,
| n0 |
| n1 |
| n2 |
| c1 |
| c2 |
| c3 |
| c4 |
| n3 |
2) Далее сумма стоимостей двух рёбер инцидентных узлу ni в маршруте не может быть меньше, чем сумма стоимостей двух ребер наименьшей стоимости во всем графе, инцидентных с ni
Из 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.