Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re: Highest total sum path problem

by QM (Parson)
on Mar 04, 2020 at 14:58 UTC ( [id://11113769]=note: print w/replies, xml ) Need Help??


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
    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 !!

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others exploiting the Monastery: (6)
As of 2024-03-29 14:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found