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?? |
Yes this problem can be represented as a 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 °) or you reimplement Heaps to have balanced search trees.
In Section
Meditations
|
|