title: Performance difference RBFS - A*
body: <p>I've implemented the RBFS as defined in AIMA and wanted to compare it to an implementation of A*. When I try it out on an instance from the TSPlib (ulyssis16 - 16 cities), both come up with a correct solution, the memory usage is also correct (exponential for A*, linear for RBFS). The only weird thing is that the RBFS algorithm is much faster than A* when it shouldn't be the case. A* finished in about 3.5 minutes, RBFS takes only a few seconds. When I count the number of visits for each node, A* visits a lot more nodes than RBFS. That also seems counter-intuitive.</p>
  
  <p>Is this because of the trivial instance? I can't really try it out on a bigger instance as my computer doesn't have enough memory for that.</p>
  
  <p>Has anyone got any suggestions? Both algorithms seem to be correct according to their specifications, their results and memory usage. Only the execution time seems off...</p>
  
  <p>I already looked everywhere but couldn't find anything about a difference in their search strategy. Except for the fact that RBFS can revisit nodes.</p>
  
  <p>Thanks</p>
  
  <p>Jasper</p>
  
  <p>Edit 1: AIMA corresponds to the book Artificial Intelligence a Modern Approach by Russel and Norvig.
  Edit 2: TSPlib is a set of instances of the TSP problem (<a href="http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/" rel="nofollow">http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/</a>)
  Edit 4: The code for the A* algorithm is given as follows. This should be correct.
      def graph_search(problem, fringe):
          """Search through the successors of a problem to find a goal.
          The argument fringe should be an empty queue.
          If two paths reach a state, only use the best one. [Fig. 3.18]"""
          closed = {}
          fringe.append(Node(problem.initial))
          while fringe:
              node = fringe.pop()
              if problem.goal_test(node.state):
                  return node
              if node.state not in closed:
                  closed[node.state] = True
                  fringe.extend(node.expand(problem))
          return None</p>
  
  <pre><code>def best_first_graph_search(problem, f):
      return graph_search(problem, PriorityQueue(f,min))
  
  def astar_graph_search(problem, h):
      def f(n):
          return n.path_cost + h(n)
      return best_first_graph_search(problem, f)
  </code></pre>
  
  <p>Where problem is a variable containing details about the problem to be solved (when the goal is reached, how to generate successors, the initial state,...). A node contains the path on how to reach that state by storing the parent node and some other utility functions. Here is an older version of this code <a href="http://aima-python.googlecode.com/svn/trunk/search.py" rel="nofollow">http://aima-python.googlecode.com/svn/trunk/search.py</a>) For the TSP problem, the tours are created incrementally. The used heuristic is the minimal spanning tree on the nodes that are not yet visited. </p>
  
  <p>The code for RBFS is as follows:
      def rbfs(problem, h):
          def f(n):
              return n.path_cost + h(n)</p>
  
  <pre><code>    def rbfs_helper(node, bound):
          #print("Current bound: ", bound)
  
          problem.visit(node)
  
          if (problem.goal_test(node.state)):
              return [node, f(node)]
  
          backup = {}
          backup[node.state.id] = f(node)
  
          succ = list(node.expand(problem))
  
          if (not succ):
              return [None, float("inf")]
  
          for v in succ:
              backup[v.state.id] = max(f(v), backup[node.state.id])
  
          while(True):
              sortedSucc = sorted(succ, key=lambda node: backup[node.state.id])
  
              best = sortedSucc[0]
  
              if (backup[best.state.id] &gt; bound):
                  return [None, backup[best.state.id]]
  
              if (len(sortedSucc) == 1):
                  [resultNode, backup[best.state.id]] = rbfs_helper(best, bound)
              else:
                  alternative = sortedSucc[1]
                  [resultNode, backup[best.state.id]] = rbfs_helper(best, min(bound, backup[alternative.state.id]))
  
              if (resultNode != None):
                  return [resultNode, backup[best.state.id]]
  
      [node, v] = rbfs_helper(Node(problem.initial), float("inf"))
  
      return node
  </code></pre>
  
  <p>It also uses the problem and node as defined above. Those were specifically designed to be used as generic elements.</p>