Finding the lowest cost for moving from right to left in a matrix

I have the following Matrix F:

F = [4.06594492133924 3.91392782934169 3.86257243431977 3.83958417146083 3.87248241841441;3.72609624731091 3.65008770131213 3.67474085228899 3.68791657846109 3.69446337307048;3.56426661862652 3.64027516462530 3.76763910564599 3.94264446050249 4.09792729457750;3.53860459077350 3.61461313677228 3.74197707779298 3.91698243264947 4.07226526672448;3.35761919958582 3.43362774558459 3.56099168660529 3.73599704146179 3.89127987553679;3.06832658863894 3.14433513463771 3.27169907565841 3.44670443051491 3.60198726458992;2.75424247643088 2.83025102242966 2.95761496345035 3.13262031830685 3.28790315238186;2.46936077603974 2.54536932203852 2.67273326305921 2.84773861791571 3.00302145199072;2.27551181481029 2.35152036080907 2.47888430182977 2.65388965668626 2.80731560867382;2.17149062109275 2.24749916709153 2.37486310811223 2.54801158088127 2.70236597391256;2.14205851916150 2.21806706516028 2.34357412409352 2.51765103790629 2.67200543093758;2.13961561581285 2.21376727972418 2.34020277970115 2.51427969351392 2.66863408654520;2.13868717476913 2.21469572076790 2.34205966178860 2.51706501664510 2.67234785072011;2.11255469272728 2.18856323872606 2.31592717974676 2.49093253460325 2.64621536867826;2.05437863029193 2.13038717629071 2.25775111731140 2.43275647216790 2.58803930624291;1.94441279266752 2.02042133866629 2.14778527968699 2.32279063454349 2.47807346861849;1.79210871282624 1.86811725882501 1.99548119984571 2.17048655470221 2.32625129388475;1.57373143534853 1.64973998134731 1.77710392236800 1.95259118233204 2.19509645327124;1.28640436853593 1.36241291453471 1.49025876066295 1.75248655238363 1.99499182332283;0.943907106796631 1.02039755790295 1.23498393578783 1.49721172750852 1.72051997532553;0.608574717322655 0.771805700185623 0.986392078070512 1.22942284666900 1.26224200175917;0.448761400102450 0.611992382965419 0.807381737728113 0.859923413599767 0.882942044618221;0.536539702785447 0.592795359843224 0.597695621879082 0.640436773679021 0.663455404697475;1.29291637952257 1.55906047423917 1.77384917393385 1.94099645979273 2.12786626643309;2.32004926332893 2.78334118195338 3.19527770555592 3.55957281532265 3.94359044587087;2.65697409136578 3.17642014799637 3.64451080960504 4.06496005737792 4.50513182593228;2.85556518792511 3.40759114857953 3.90826171421204 4.36129086600875 4.83404253858694;3.01856219481769 3.59464631028462 4.11937503072964 4.59646233733885 5.09327216472955;3.04757753742075 3.62796483031244 4.15699672818221 4.63838721221619 5.13950021703165;3.05532583301236 3.63682002527428 4.16695882251428 4.64945620591848 5.15167611010417;3.05532583301236 3.63682002527428 4.16695882251428 4.64945620591848 4.84469635482352;3.05532583301236 3.63682002527428 4.16695882251428 4.34247645063783 4.36219897141931;3.05532583301236 3.63682002527428 4.07353298543575 3.85997906723362 3.87970158801511;3.05532583301236 3.54339418819575 3.71097158068000 3.37748168382942 3.39720420461091;2.96189999593383 3.29353290219134 3.18083278344000 2.89498430042522 2.91470682120670;2.71203870992942 2.90747096130960 2.65069398620000 2.41248691702102 2.43220943780250;2.38911444921179 2.32597676904768 2.12055518896000 1.92998953361681 1.94971205439830;1.90546445095672 1.74448257678576 1.59041639172000 1.44749215021261 1.46721467099409;1.31385286167053 1.16298838452384 1.06027759448000 0.964994766808406 0.984717287589892;0.657502738260698 0.581494192261920 0.530138797240000 0.482497383404203 0.502219904185689]

I want to find the most efficient route (with the lowest costs through this matrix starting from the right top going down towards the left. The choices you have is either:

[F(i+1, j-1), F(i+1, j), F(i, j-1)]

So that means: Left from the value, left/down from the value, down from the value.

How to do this? Since in the real matrix, in theory, there should be an option to go left all the time (never going to happen but anyways) without running out of indices.

Thank you!

[madhan ravi]

Could you show how your desired output should look like?

[JamJan]

Fout = [3.8725 3.6879 3.6747 3.6501 3.5643 3.5386 ...]

And then continue choosing the values straight all the way down.

[madhan ravi]

Why is it hard to write down a clear explicit output?

[JamJan]

   [3.8725
    3.6879
    3.6747
    3.6501
    3.5643
    3.5386
    3.3576
    3.0683
    2.7542
    2.4694
    2.2755
    2.1715
    2.1421
    2.1396
    2.1387
    2.1126
    2.0544
    1.9444
    1.7921
    1.5737
    1.2864
    0.9439
    0.6086
    0.4488
    0.5365
    1.2929
    2.3200
    2.6570
    2.8556
    3.0186
    3.0476
    3.0553
    3.0553
    3.0553
    3.0553
    3.0553
    2.9619
    2.7120
    2.3891
    1.9055
    1.3139
    0.6575]

[Star Strider]

Define ‘cost’.

Answer 1

[John D'Errico]

This is a fairly classic problem, posed for homework, etc. (In fact, it is the basis for at least one Project Euler problem, easily solved.)

The trick is, if you start at the top right cell, the cost to get to that point is simple. Now, you can simply compute the cost to go to ANY of the three neighbors of that cell, left, down, or left/down.

Store those costs in the new matrix, in the corresponding cells, as long as the new cost to get to that cell is less than the cost to get to it from any of its neighbors.

Now, you have three new start points. For each of them, you can compute the cost to get to any of the three neighbors of that cell. You will just work down the matrix. The time required will not be large, since you keep a record of the cost required to get to each cell from its neighbors. What you do not need to do is compute all possible paths, because you are computing at each step, the cheapest cost to get to the front that you have examined so far.

As I said, the idea is simple, but you need to avoid brute force, computing all paths, as that would quickly become uncountably huge. And that is why they posed it as one of the Project Euler problems. (Admittedly, an early, easy one.)