in reply to Highest total sum path problem
Is there a clever (meaning fast) way to compute this?Not so much.
Because there is no limitation on what a move will "cost", pruning the choice tree early isn't helpful. Also, there's no way to prioritise choices at an intermediate stage.
All paths have to be checked.
If this was a TSP (find the minimum path length) problem, with only non-zero edges, and you had a "best min so far", you could limit choices that immediately exceed that "best min so far". But you have negative-valued edges. And if you had a "best max so far", it's not clear how to avoid traversing the whole tree.
-QM
--
Quantum Mechanics: The dreams stuff is made of
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Highest total sum path problem
by LanX (Saint) on Mar 05, 2020 at 13:04 UTC | |
by baxy77bax (Deacon) on Mar 05, 2020 at 17:17 UTC |
In Section
Seekers of Perl Wisdom