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.

Quantum Mechanics: The dreams stuff is made of

Replies are listed 'Best First'.
Re^2: Highest total sum path problem
by LanX (Cardinal) on Mar 05, 2020 at 13:04 UTC
    It really depends on the exact problem.

    There could be a dual problem which has to be minimised. (The skipped cells that is).

    In these cases one could use standard minimisation algorithms.

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    Wikisyntax for the Monastery

      That is true. But I have turned to the community like many times before because I have a task to solve and conditions passed down to me by a BI officer that has even vaguely described the problem than I did it here. (yes I simplified the problem but if i posted the obscured interaction it is aimed to solve i don't think anyone would even try to participate, let alone ask for claricifations). Yes the problem is not clearly specified here and through interactions on this forum I believe the community is doing exactly what its intent is. By posting your comments you are helping me. Those that do not want to help, need not to post, those that do, thank you !!

      Really ppl, thank you all !!