Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

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 (Cardinal) 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?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (1)
As of 2021-04-11 22:02 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?