MATLAB Answers

Info

이 질문은 마감되었습니다. 편집하거나 답변을 올리려면 질문을 다시 여십시오.

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

조회 수: 1(최근 30일)
JamJan
JamJan 2019년 7월 28일
마감: 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

답변(1개)

John D'Errico
John D'Errico 2019년 7월 28일
편집: 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.)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by