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

[download]

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

[download]

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

[download]

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

In reply to Highest total sum path problem by baxy77bax

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.