Yes this problem can be represented as a shortest way lowest cost problem in a graph.

But Dijkstra also deals with generalized graphs, for instance here it s clear that any path will have the same length.

You'd have also more algorithmic overhead, it depends on always choosing the partial solution with the lowest cost so far. But Perl has no automatically sorted lists, so you'd run a sort each time over all open ends.°

And Dijkstra would handle a short path with lower cost (up in the triangle) before handling an almost finished path with slightly higher cost.

My guess is that Dijkstra would only pay off for triangles with several hundreds of rows. (update: An optimized branch-and-bound would do better but still need many rows.)

But OTOH there are ready to use Dijkstra / Graph packages...

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery

°) or you reimplement Heaps to have balanced search trees.

In reply to Re^2: Brute force vs algorithm (PWC # 100) by LanX
in thread Brute force vs algorithm (PWC # 100) by 1nickt

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.