Блог

Ниже приведен псевдокод реализации поиска в глубину (DFS) с одним стеком и большой таблицей для обозначения посещенных узлов:

 DFS(N0):
   StackInit(S)
   S.push((N0, null))
   if isGoal(N0) then do
      return true
   markVisited(N0)
   S.push((null, N0))
   while !isEmpty(S) then do
      (N, parent) := S.pop()
      R := next((N, parent))
      if isNull(R) then do
         continue             // So no new node add to this layer.
      S.push((R, parent))
      if marked(R) then do
         continue
      if isGoal(R) then do    // If it's goal don't have to explore it.
         return true
      markVisited(R)
      if depthMax((R, parent)) then do
         continue
      S.push((null, R))
   return false
 

Проблема, которую я хочу решить, — это его модификация: он заменяет стек S на PriorityQueue PQ . Этот алгоритм используется для моделирования алгоритма IDA * (это изложено в учебнике, который, к сожалению, не написан на английском языке, поэтому я не буду приводить название ссылки / книги):

 DFS2(N0, f, LIMIT):
   PriorityQueueInit(PQ)
   // A node (N, parent) stored in PQ represents a path from `N0` to `N`
        passing the node `parent`; A node with smaller value on f() is 
        prioritized than those with larger value.
   PQ.push((N0, null))
   if isGoal(N0) then do
      return true
   markVisited(N0)
   PQ.push((null, N0))
   while !isEmpty(PQ) then do     // (1)
      (N, parent) := PQ.poll()
      R := next((N, parent))      // (2)
      if isNull(R) then do
         continue
      PQ.offer((R, parent))
      if marked(R) then do
         continue
      if isGoal(R) then do
         return true
      markVisited(R)
      if f((R, parent)) > LIMIT then do
         continue
      PQ.offer((null, R))
   return false
 

• (1): В алгоритме A * приоритетная очередь используется для хранения узлов, которые еще не были исследованы, т.Е. Открытого списка. В то время как в первом псевдокоде DFS, который я предоставил, стек S является закрытым списком, поэтому я предполагаю, что во втором псевдокоде PQ тоже есть закрытый список. Итак, как второй псевдокод может имитировать алгоритм IDA * с закрытым списком?
• (2): Он извлекает текущий наименьший узел из PQ , который , вероятно, не является родственным узлом узла N , т. Е. Он переходит к другому поддереву из текущего поддерева , содержащегося N в нем. Какова цель этой строки?

Может кто-нибудь показать мне правильность второго алгоритма, т.Е. Почему его можно использовать в алгоритме IDA *?

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

1. Все графики, появляющиеся в учебнике, рисуются древовидно, т. Е. Только Один родительский элемент для каждого узла, чтобы показать концепции. Это меня смущает: работает ли второй алгоритм только для деревьев?
2. Учитывая строку

    if f((R, parent)) > LIMIT then do ...
    

   Если второй также работает для графика, а не только для дерева, тогда может быть много родителей R , должен ли я рассматривать все случаи или только текущий parent ?

Здесь многое происходит.

Насколько я могу судить, этот код всегда возвращает первый целевой узел, который достигает вершины очереди. Согласно приведенным ниже предположениям о f и next, этот целевой узел является f-оптимальным. Но я бы не назвал это IDA *.

Во-первых, обычно и A *, и IDA * одновременно открывают всех соседей текущего узла. Этот код … не работает. Он использует итераторы, но только один цикл. Первый толчок предназначен для следующего родственного узла текущего узла, а второй толчок предназначен для дочернего узла. Я думаю, это нормально, за исключением того, что братья и сестры должны быть перечислены в возрастающем порядке f, чтобы многообещающий брат не скрывался после бесперспективного.

Во-вторых, в отличие от A *, IDA * не имеет закрытого списка. В некотором смысле IDA * всегда имеет дерево поиска, поскольку, если оно достигает двух эквивалентных узлов, оно все равно обрабатывает их так, как если бы они были отдельными узлами. У A * есть закрытый список, но он сложнее, чем представленный здесь. Способ, которым A * обрабатывает циклы, заключается в том, что, если он обнаруживает более дешевый путь к уже закрытому узлу, он снова открывает узел. Этот код этого не делает, поэтому он корректен только в том случае, если нет необходимости повторно открывать узел. В результате этому коду необходимо, чтобы f было так называемой последовательной эвристикой (на каждом пути f никогда не уменьшается по мере следования по пути), в то время как A * требуется только, чтобы f было допустимым (f никогда не недооценивает стоимость достижения целевого состояния).