Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

Re: Brute force vs algorithm (PWC # 100)

by hdb (Monsignor)
on Feb 16, 2021 at 12:44 UTC ( #11128438=note: print w/replies, xml ) Need Help??

in reply to Brute force vs algorithm (PWC # 100)

Check for Dijkstra's algorithm in classic Graph Theory.

  • Comment on Re: Brute force vs algorithm (PWC # 100)

Replies are listed 'Best First'.
Re^2: Brute force vs algorithm (PWC # 100)
by LanX (Saint) on Feb 16, 2021 at 17:42 UTC
    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.

Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11128438]
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others pondering the Monastery: (6)
As of 2023-12-11 12:45 GMT
Find Nodes?
    Voting Booth?
    What's your preferred 'use VERSION' for new CPAN modules in 2023?

    Results (41 votes). Check out past polls.