title: Can I modify the standard A* (A star)  under consistent heuristic / uniform cost / Dijkstra's search so it doesn't have to update the frontier?
body: <p>the standard way is the following: <strong>AI: A modern Approach</strong></p>
  
  <pre><code>function UNIFORM-COST-SEARCH
  
  node &lt;- INITIAL-STATE
  frontier &lt;- priority queue ordered by PATH-COST, with node as the only element
  explored &lt;- an empty set
  loop do
      if frontier is empty then return failure
      node &lt;- POP frontier  /* chooses the lowest-cost node in frontier */
      if GOAL-TEST(node) then return SOLUTION(node)
      add node to explored
      for each action in ACTIONS(node) do
          child &lt;- CHILD-NODE(problem, node, action)
          if child is not in explored or frontier then
              frontier.INSERT(child)
          else if child is in frontier with higher PATH-COST then
              replace that frontier node with child
  </code></pre>
  
  <p>Here this step is complicated to achieve, a normal priority queue cannot update a certain element's priority efficiently.</p>
  
  <pre><code>        else if child is in frontier with higher PATH-COST then
              replace that frontier node with child
  </code></pre>
  
  <p>I am thinking to modify the algorithm the following way:</p>
  
  <pre><code>function UNIFORM-COST-SEARCH-Modified
  
  node &lt;- INITIAL-STATE
  frontier &lt;- priority queue ordered by PATH-COST, with node as the only element
  explored &lt;- an empty set
  loop do
      if frontier is empty then return failure
      node &lt;- POP frontier  /* chooses the lowest-cost node in frontier */
    &gt; if node is in explored then continue
      if GOAL-TEST(node) then return SOLUTION(node)
      add node to explored
      for each action in ACTIONS(node) do
          child &lt;- CHILD-NODE(problem, node, action)
    &gt;     if child is not in explored then
              frontier.INSERT(child)
  </code></pre>
  
  <p>So I don't care if the frontier contains repeated states. I only expand the first of the repeated states in the frontier. Since the path-cost is <code>consistent</code>, and the frontier is implemented using <code>priority queue</code>, it is not harmful to ignore the other repeated states with higher cost.</p>
  
  <p>Is it reasonable?</p>
  
  <h3>Update</h3>
  
  <p>Sorry I forgot to mention I am particularly interested in consistent heuristic case.</p>