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

Question

JamJan 2019-7-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/473787-finding-the-lowest-cost-for-moving-from-right-to-left-in-a-matrix

关闭： MATLAB Answer Bot 2021-8-20

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!

5 个评论
显示 3更早的评论隐藏 3更早的评论

JamJan 2019-7-28

编辑：JamJan 2019-7-28

Star Strider 2019-7-28

Define ‘cost’.

请先登录，再回答此问题。

Answer 1

John D'Errico 2019-7-28

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/473787-finding-the-lowest-cost-for-moving-from-right-to-left-in-a-matrix#answer_385145

编辑：John D'Errico 2019-7-28

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