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
| [reply] |
|
| [reply] |
|
| [reply] |
Re: Highest total sum path problem
by LanX (Saint) 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?
| [reply] |
|
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!
| [reply] |
|
| [reply] |
|
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
| [reply] |
|
|
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?
| [reply] |
|
|
|
Re: Highest total sum path problem
by tybalt89 (Monsignor) on Mar 05, 2020 at 18:07 UTC
|
#!/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
| [reply] [d/l] [select] |
|
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
| [reply] [d/l] |
|
| [reply] |
|
|
|
| [reply] |
|
> "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)
°) 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"
| [reply] |
|
>
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
;)
| [reply] |
Re: Highest total sum path problem
by LanX (Saint) 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!
| [reply] |
A reply falls below the community's threshold of quality. You may see it by logging in. |