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

Highest total sum path problem

by baxy77bax (Deacon)
on Mar 04, 2020 at 10:18 UTC ( #11113757=perlquestion: print w/replies, xml ) Need Help??

baxy77bax has asked for the wisdom of the Perl Monks concerning the following question:

Hi,

I have an intriguing problem that looks like a travelling salesman problem but I want to see whether someone has a better solution. So what I have is an NxM matrix with both positive and negative numbers (ints):

NxM | b a --+------------------------- | 1 4 5 -1 9 ... | 0 3 0 17 -3 ... b>| 1 10 3 0 3 ... |-8 -3 2 1 -4 ... a>| 0 8 4 0 0 ...

My starting position is (a,a) = 0 My end position is (b,b) = 10

What Iam looking for is a path that has the highest total sum from aa > bb

pathA: left, up, left, left, up = 0+0+1+2+(-3)+10 = 10 pathB: left-slide + up-slide = 0+8+10 = 18 pathC: up-slide + left + up + left-slide+down = 0+3+0+17+3+10= 33 etc..

From the above it follows that I can slide or I can go by one position in any direction except the diagonal. Given a starting position (x - any random position) the task is to discover the value in the matrix (let say N=10, M=10) so that the number of moves (summing operations) from x to that position is the minimum possible and the total sum (summarized values) of the path is the maximum possible. In tha above example path C would be the best candidate but i haven't worked out all possible paths so I don't know. Is there a clever (meaning fast) way to compute this?

thank you

Replies are listed 'Best First'.
Re: Highest total sum path problem
by QM (Parson) on Mar 04, 2020 at 14:58 UTC
    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

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

Re: Highest total sum path problem
by LanX (Cardinal) on Mar 04, 2020 at 11:09 UTC
    > so that the number of moves (summing operations) from x to that position is the minimum possible and the total sum (summarized values) of the path is the maximum possible.

    Too fuzzy, as usual.

    You have two criteria to optimize, without telling us which one has to be prioritized.

    • the shortest among the max value path?
    • the max valued among the shortest path?

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

      good catch !! sorry for that :)

      -> the max valued among the shortest path? // WRONG BULLET POINT C/P

      PS

      as usual. -> was directed to me or a general comment :) I can take a critique, don't worry (speak your mind freely on this thread) :)

      UPDATE:

      I copy/past the wrong bullet point. The correct one is

      -> the shortest among the max value path!!

      First i need to figure out which one is the highest and then if many have the same value , pick the shortest

      @Rata , Thnx!

        Hello baxy77bax,

        you need to rethink your requirements. If you want to have the minimum number of moves, you only have two possibilities:

        • slide from aa to ba and then to bb
        • slide from aa to ab and then to bb
        any other solution would have a longer path. And calculating the maximum sum for these two paths is rather trivial ...

        HTH, Rata
        Can you clarify the problem statement?

        For instance, is it legal to try to do a tour of the matrix, to pick up as many high value cells as possible? If the priority is "max sum", followed by "min terms", then a "rook's tour" of the positive valued cells is in order.

        Another idea, can you revisit a cell? What's to keep you from circling through 4 positive value cells forever?

        Can you go "offline", by taking a longer tour than necessary?

        -QM
        --
        Quantum Mechanics: The dreams stuff is made of

        What does slide mean? If you slide A->D, skipping B and C, what is the path length?3 or 1? Also, does sliding mean that the points on the squares you slided over are not counted to your sum? Only the final square you landed on is counted?

Re: Highest total sum path problem
by tybalt89 (Prior) on Mar 05, 2020 at 18:07 UTC

    Maybe (or maybe not) slight cheating :)

    #!/usr/bin/perl use strict; # https://perlmonks.org/?node_id=11113757 use warnings; $_ = <<END; 1 4 5 -1 9 0 3 0 17 -3 1 10 3 0 3 -8 -3 2 1 -4 0 8 4 0 0 END my $destrow = 2; my $destcol = 1; my $startrow = 4; my $startcol = 4; my @m = map [split], split /\n/; my @visited; my $maxrow = $#m; my $maxcol = $#{ $m[0] }; my $maxscore; my $minlength; my $best; $visited[$startrow][$startcol] = 1; try( $startrow, $startcol, 0 ); my @best = split ' ', $best; my @values; print "best path:\n"; for ( my $i = 0; $i < @best - 4; $i += 3 ) { print directions(@best[$i, $i+1, $i+3, $i+4]), ' '; push @values, $m[$best[$i]][$best[$i+1]]; } print "\n= "; print join '+', @values, $m[$best[-3]][$best[-2]]; print "\n= $best[-1]\n"; sub try { my ($row, $col, $score) = @_[-3 .. -1]; if( $row == $destrow && $col == $destcol ) { if( $maxscore ) { if( $score > $maxscore or $score == $maxscore and $minlength > @_) { $maxscore = $score; $minlength = @_; $best = "@_"; } } else { $maxscore = $score; $minlength = @_; $best = "@_"; } return; } for my $r ( 0 .. $maxrow ) { if( ++$visited[$r][$col] == 1 ) { $m[$r][$col] > 0 and try( @_, $r, $col, $score + $m[$r][$col] ); } --$visited[$r][$col]; } for my $c ( 0 .. $maxcol ) { if( ++$visited[$row][$c] == 1 ) { $m[$row][$c] > 0 and try( @_, $row, $c, $score + $m[$row][$c] ); } --$visited[$row][$c]; } } sub directions { my ($rowfrom, $colfrom, $rowto, $colto) = @_; if( $rowfrom != $rowto ) { return +($rowfrom < $rowto ? 'down' : 'up') . (abs($rowfrom - $rowto) > 1 ? '-slide' : ''); } else { return +($colfrom < $colto ? 'right' : 'left') . (abs($colfrom - $colto) > 1 ? '-slide' : ''); } }

    Outputs:

    best path: up-slide down-slide left-slide up-slide right down right-slide down-sl +ide left up-slide down-slide down-slide left up-slide = 0+9+3+1+1+4+3+17+1+2+5+3+4+8+10 = 71

    "real matrix is 50000*50000" HaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHa

      Shouldn't this be unambiguous? How far is a "slide"?
      up-slide down-slide left-slide up-slide right down right-slide down-slide left up-slide down-slide down-slide left up-slide

      -QM
      --
      Quantum Mechanics: The dreams stuff is made of

        There were no examples of that in the original post.

        Sigh, yet another case of an incomplete spec.

        > Shouldn't this be unambiguous?

        Well, in this case it is, because the order of the added values is unique.

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

      > "real matrix is 50000*50000" HaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHaHa

      It's not that impossible if the approach was mathematical.

      Of course this would require cleanly defined rules and not these "oh good point I forgot to mention that ..." dialogs.

      How this?

      • I could imagine proving that a path covering n-x points is maximal possible and exists.
      • One would identify the x minimal points to be excluded.
      • I expect x to be just the non positive weight cells in most cases anyway.
      • There are most likely many equally short paths possible, which could be proven, too.
      • Now picking one minimal path should be sufficient.

      In short, no need to brute force all possible paths if there are plenty optimal ones and picking one is sufficient.

      Of course I might have misunderstood the "rules", but why should I risk to invest more efforts for vain ? ;)

      For instance:

      • is it really allowed to slide back a way you just slid forward? (Like your first two moves a0-up9-down3)
      • is it allowed to slide over positive weights? (Like your third move -left1 ignoring 3 positive cells in between)

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

      ) read "I have no real clue what I need"

      update

      Your solution demonstrates my approach pretty well:

      • you are visiting all positive cells
      • the only non positive one is your starting point
      • the shortest path must have the same amount of moves when you avoid revisiting a cell.
      • There are certainly many paths meeting that criterion
      • most probably automatically constructed from smaller segments like: "finish a column/line before switching to the next one"
        > There are certainly many paths meeting that criterion most probably automatically constructed from smaller segments like

        OK not trivial, but well studied and becoming easier with growing number of possible moves (i.e. low number of non-positive cells here)

        see Hamiltonian Path

        But the general case is NP complete ... hmm ...

        ... well ... HaHaHaHaHaHaHaHaHaHa .... HaHaHaHaHaHaHaHaHaHa

        ;)

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

Re: Highest total sum path problem
by LanX (Cardinal) on Mar 08, 2020 at 18:26 UTC
    Your example has 36 cells with only 11 non positive ones. That means only one third of the cells need to be skipped.

    After excluding start and stop it's obvious that the best theoretical result is to pass by all remaining 24=34-10 positive ones exactly one time, hence in minimal 25 moves.

    tybalt89 has demonstrated that such a path exists, provided his "slides" were legal. (I already expressed my doubt. Please clarify!!! )

    Now the following is based on the assumption these slides were correct.

    If your 50000x50000 matrix has the same density of > 2/3 positive ones, than the likelihood to find a trivial but optimal solution is very high.

    To achieve this I'd reshuffle the matrix by putting the start and end cell at opposing corners.

    The rows and columns in between then need to be sorted ascending by number of positive cells.

    The trivial solution is based on the fact that you can always reach all positive cells inside your actual row (or column in a dual approach).

    What really matters is the jump to the next row with a positive cell in the same column.

    (NB: That approach is symmetric by swapping rows and columns)

    This is hardest with rows with low density and becomes easier afterwards, hence the pre-sorting.

    If this trivial solution fails, you'll still be able to construct a nearly optimal solution by including some non positive cells.

    That's a pragmatic approach to ignore the possibility of a slightly better solution, which is much harder to compute.

    But this should finish in reasonable time.

    HTH!

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

A reply falls below the community's threshold of quality. You may see it by logging in.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://11113757]
Approved by marto
Front-paged by haukex
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (8)
As of 2020-12-04 14:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    How often do you use taint mode?





    Results (60 votes). Check out past polls.

    Notices?