python - 深さを限定した反復検索で最適でないパスが返される -- Python

Question

タイトルにあるように、私の反復的な深さ制限検索は次善のパスを返します。

これは割り当て用ではありません。BFS と比較して IDLS がどのように機能するかに興味がある

明らかに私が見落としているものがありますが、私のコードは最適なパスを返しません。また、設定された制限 (反復なし) で実行すると、最適な値またはそのすぐ上にパスが返されません。

ノードの内容: state、pathCost、ソリューション (パス)

コードは次のとおりです。

def depthLimitedSearch(problem, limit = 999999):
"""
Search the deepest nodes in the search tree first, up to limit depth. 
"""

  node = Node(problem.getStartState())
  if problem.isGoalState(node.state):
    return node.solution

  frontier = util.Stack()
  frontier.push(node);
  explored = set([node.state]);



  while not frontier.isEmpty():
    node = frontier.pop()
    explored.add(node.state)

    for child in node.createChildren(problem):
      if child.pathCost <= limit:
        if (child.state not in explored):
          if (child not in frontier.list):
            if problem.isGoalState(child.state):
              return child.solution
            frontier.push(child)

  return []

def iterateDLS(problem, limit = 999999, inc = 1):
''' iterate DLS starting from limit and rising in inc increments'''
  result = []
  while result == []:
    result = depthLimitedSearch(problem, limit)
    limit += inc
  return result
''' testing for fixed limit'''
##  limit = 31
##  result = depthLimitedSearch(problem, limit)