5.10. МОДИФИКАЦИИ

Как и в случае переборов в пространстве состояний, существует ряд способов модификации основного алгоритма упорядоченного перебора, делающих его более практическим в конкретных ситуациях. Прежде всего, вместо того, чтобы после каждого раскрытия вершины заново строить новое потенциальное дерево решения, можно было бы не прерываясь раскрыть одну или более вершин в то и несколько их дочерних вершин, а затем уже строить новое дерево то. Такая стратегия приводит снижению общих затрат на построение то, но в то же время возникает риск, что некоторые из раскрытых вершин не будут расположены на наилучшем потенциальном дереве решения.

В случае «И/ИЛИ» деревьев можно выбрать также стратегию поэтапного перебора, описанную в гл. 3. При ее использовании необходимое пространство в памяти машины периодически очищается в результате отбрасывания некоторых из поисковых «И/ИЛИ» деревьев. Можно, например, определить, какое из потенциальных деревьев решения внутри дерева перебора имеет наибольшую оцениваемую стоимость. Тогда можно периодически отбрасывать некоторое число наиболее «дорогих» потенциальных деревьев решения (с риском, конечно, что отброшенное дерево окажется верхней частью истинного дерева минимальной стоимости).

Если наш метод предполагается использовать для перебора на «И/ИЛИ» графах (а не на «И/ИЛИ» деревьях), то в алгоритме следует произвести более важные изменения. При этом необходимо принять во внимание соображения, упомянутые в разд. 5.4.