Next: 4.8
Метод ветвей и границ
Up: 4
Разработка алгоритмов
Previous: 4.6
Обходы графа в глубину и ширину
).
Можно ограничиться исследованием только таких конфигураций, в которых на
каждой вертикали и на каждой горизонтали находится не более одного ферзя,
что дает только 
конфигураций. Тот факт, что никакие два ферзя не могут находиться на одной
диагонали, уменьшает число возможностей; при использовании этого ограничения
число вершин в дереве поиска сокращается до 2056.
Использование подобного анализа для сокращения множества возможных решений
называется поиском с ограничениями или с отсечением ветвей
(в связи с тем, что при этом осуществляется удаление поддеревьев из дерева
поиска решения). Например, размещение первого ферзя на клетке (1,1) дает
ограничение: оно запрещает размещение другого ферзя на некоторых клетках,
среди которых, например, есть клетка (2,2). Процесс введения ограничений
в задаче о ферзях можно продолжать дальше. Например, две конфигурации можно
считать эквивалентными, если одна из них переводима в другую с помощью
вращений и отражений. Поэтому можно ограничиться поиском только всех попарно
неэквивалентных конфигураций, а затем с помощью вращений и отражений строить
из них все множество конфигураций. Например, для любой конфигурации с ферзем
в клетке (1,1) имеется эквивалентная конфигурация, в которой клетка (1,1)
пуста, что позволяет начинать поиск с 
и получать, однако, все неэквивалентные решения.
Другим усовершенствованием является слияние (или склеивание)
ветвей. Идея его состоит в том, чтобы избегать повторного выполнения одной
и той же работы: Если несколько поддеревьев поиска изоморфны, желательно
исследовать лишь одно из них. В задаче о ферзях, например, можно использовать
склеивание, заметив, что если 
,
то найденную конфигурацию можно отразить и получить конфигурацию, для которой 
.
В добавление к ограничениям и склеиванию, которые, очевидно, могут сократить поиск, иногда (например, когда требуется найти не все решения, а только какое-нибудь одно) оказывается полезным применять эвристический прием, называемый переупорядочением поиска:
во-первых, если известно, что искомое решение будет иметь некоторый определенный вид, то целесообразно строить поиск так, чтобы раньше других исследовались возможные решения именно этого вида;
во-вторых, если это возможно, то дерево поиска следует перестроить так, чтобы вершины, имеющие относительно мало сыновей, были близки к корню дерева (например, дерево поиска, изображенное на рис. 22, является более предпочтительным, чем дерево поиска, показанное на рис. 23). Это позволит за счет накопления ограничений при движении по дереву поиска отбрасывать "большие" поддеревья.
Рис. 22. Предпочтительное дерево поиска
Следует иметь в виду, что различные усовершенствования полезно применять не только при разработке программы, но и включить в разрабатываемую программу. В задаче о ферзях, например, анализ задачи позволяет ввести ограничения уже при составлении программы, но ограничение, состоящее в том, что ферзи не должны стоять на одной диагонали, можно применять только в процессе появления конфигураций.
Рис. 23. Менее удачное дерево поиска
Аналогично склеивание и переупорядочение поиска оказываются полезными
в некоторых ситуациях во время работы процедуры поиска. Например, во время
работы можно пытаться распознавать одинаковые поддеревья по частичному
решению, соответствующему корню поддерева, и, таким образом, осуществлять
склеивание. Использование во время работы приема переупорядочения может,
например, заключаться в том, что для частичного решения 
остальные компоненты решения ищутся в некотором динамически определяемом
порядке вместо обычного порядка 
.
Next: 4.8
Метод ветвей и границ
Up: 4
Разработка алгоритмов
Previous: 4.6
Обходы графа в глубину и ширину