From: tehom@REMOVEpanNOSPAMix.com   
      
   steve.breslin@gmail.com writes:   
      
   > I'm working on the details, and I have a couple concerns.   
   >   
   > > [E]ach boundary node would retain not just one   
   > > shortest path, but the shortest path relative to each combination of   
   > > keys.   
   >   
   > I don't see how we can use a closed list, at least in the normal sense,   
   > because we want to re-visit nodes after acquiring a new key.   
      
   I assume we are talking about a situation like:   
      
      
           Start --- A -- B::key-node   
                     |   
               C::locked-node   
                     |   
                   Goal   
      
   where the best (and in fact only) path must go through A twice.   
      
   Yes, you are exacly correct.  We can't used a closed list to detect   
   which nodes we have visited; it would reject revisits that we might   
   need to make.   
      
   But the "shortest path relative to each combination of keys" test I   
   mentioned is sufficient to reject truly cyclic paths.  From what you   
   write below, I think you already see this.   
      
   I assume you don't allow zero-length or negative-length edges, so the   
   cumulative distance only increases for revisits.  Therefore a revisit   
   without improvement of the keyset will show a longer cumulative   
   distance and thus will be rejected.   
      
      
   > A node   
   > could be closed conditionally if the currently-expanding node has a   
   > subset of the same key-list, but this check could as easily go   
   > alongside the bestDist comparison (i.e., this is the best path if it   
   > has a lower bestDist and the same or a superset of my key-list).   
      
   Yes, that is exactly the criterion.   
      
   > Am I   
   > looking at an A* minus the closed list?   
      
   Right.  I was thinking out loud and didn't nail that detail down   
   before.   
      
      
   > > And if later we find that path (B E) is shorter than both (B C D) and   
   > > (B D) and acquires K2, it doesn't replace the path with K1, but   
   > > replaces the path with no key[.]   
   >   
   > When a path is updated or "replaced" in this way, all of its children   
   > must also be replaced (or deleted, if this is faster).   
      
   For purposes of reconstructing the best path at the end of the   
   algorithm?   
      
   Even though we now store multiple paths per node, ISTM we can still   
   just store one back-pointer per node per keyset and reconstruct the   
   path backwards from the goal.   
      
   For non-key nodes, only consider the back-pointer with the same keyset.   
      
   For a key node giving K1, there are two keysets, "Set" and "Set - K1",   
   that might correspond to an outgoing path that has the keyset Set.   
   But we can arrange our (earlier) rejection test so that they never   
   both occur.  Then again there's only one relevant back-pointer, though   
   it may take two looks to find it.   
      
   So even when storing multiple paths per node, we can still get away   
   with storing 1 back-pointer.   
      
   How we can arrange our rejection test so that "Set" and "Set - K1"   
   never both occur?  Add K1 to both keysets before doing the superset   
   comparison.  Break ties any way you like.   
      
   I think this all still applies if lock nodes "consume" keys, with   
   slightly more sophisticated treatment of lock nodes.   
      
   --   
   Tom Breton, the calm-eyed visionary   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)