Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Re^2: Brute force vs algorithm (PWC # 100)

by LanX (Saint)
on Feb 16, 2021 at 17:42 UTC ( [id://11128455]=note: print w/replies, xml ) Need Help??


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

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
Domain Nodelet?
Node Status?
node history
Node Type: note [id://11128455]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others surveying the Monastery: (4)
As of 2024-03-28 20:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found