Is there a clever (meaning fast) way to compute this?

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.

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

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?

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?

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' : '');
    }
  }
[download]

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
[download]

"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}

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!