Limbic~Region

> Now, let's say I first start descending from D -> X and beyond and unwind back to D in failure. Now I go to D -> F -> X. I already determined that paths to X coming from D are bad so I can stop here. 

   L     F       B
 / | \ /  \    / | \
R--J--X----D--Q  P  M
 \ | /         \ |  |
   Z             U--S

[download]

I haven't investigated the "short circuit" heuristics you've implemented so far, but it's certainly not trivial.

Let the following show a search for paths from 0 to * and the numbers denote the first steps taken in a DFS.

  3
 / \
0   2
 \ / \
  1---4
  |
  *

[download]
Now avoiding edges or nodes "failuring" after passing 2 would hinder you finding 0->3->2->4->1->* after unwinding to 0.

IMHO you need a mechanism to detect loops ("cycles") to "earlier" nodes in your actual search path before cutting of a branch of the graph which isn't trivial for DFS, I'd rather prefer BFS.

But this involves already more mathematical proofs than most of our fellow monks are likely to tolerate.

Which brings me back to the suspicion that we are trying to launch a rocket, while the OP most likely needs a tutorial about how to throw stones!

As long as he isn't capable/willing to correctly express his needs it doesn't make much sense continuing! :(

HTH!

Cheers Rolf

In reply to Re^3: Short Circuiting DFS Graph Traversal by LanX
in thread Short Circuiting DFS Graph Traversal by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.