Алгоритм возврата

Question

Как весовой порядок влияет на стоимость вычислений в алгоритме возврата? Количество узлов и деревьев поиска одинаковое, но когда оно не упорядочено, оно занимает больше времени, поэтому оно что-то делает.

Спасибо!

Answer 1

Иногда в алгоритмах обратного отслеживания, когда вы знаете, что определенная ветвь не является ответом - вы можете обрезать ее.Это очень часто встречается у агентов для игр и называется Alpha Beta Prunning .

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

Еще одна возможность - если нет сокращения, это производительность кеша.Иногда деревья хранятся в виде массива [особенно полных деревьев ].Массивы наиболее эффективны при итерации, а не "случайном скачке".Изменение порядка может изменить это поведение, что приведет к улучшению / ухудшению поведения кэша.

Answer 2

Суть возврата в точности не рассматривает все возможности или узлов (в данном случае), однако , если узлы не упорядочены , этоалгоритм не может «обрезать» возможную ветвь, потому что он точно не известен, если элемент действительно находится в этой ветке .

В отличие от , когда это упорядоченное дерево, поскольку, если искомый элемент является большим / меньшим корнем этого поддерева, искомый элемент находится справа или влево соответственно.Вот почему, если дерево не упорядочено, вычислительный порядок равен грубой силе, однако, если дерево упорядочено в худшем случае, эквивалентно грубой силе, но порядок выполнения меньше.