Help for finding a solution to my path planning problem

Question

arjun ramanujam 2015-8-28

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/237512-help-for-finding-a-solution-to-my-path-planning-problem

编辑： Cedric 2015-8-29

I am trying to solve a path planning problem with the following pseudo code Input a matrix using random number generator(randi(4,4)) Hence the maximum value is 4 This contains the following data

0-No damage
1,2-Damage but a path can be taken
3-Considerable Damage but only limited steps can be taken
4-Total damageNow what i am trying to do is reach from the first point to the last point taking these constraints in mindI am looking for methods and suggestions with which i can attempt to solve this problem and this is what i came up with

    randi(4,4);
start=a(1,1);
dest=a(4,4);
path_row=1;
path_column=1;
risk_cost=0;
while(start~=dest)
for m=1:length(a)
    for n=1:length(a)
        if(a(m,n)==4)
        treenew=[m n]
  end

Here i am first trying to find the index of the matrix that stores the value 4 so that i can avoid it
I am clueless on how to proceed further any suggestions or methods to be adapted to get the results would be really helpfulThank you in advance

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

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

Answer 1

John D'Errico 2015-8-28

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/237512-help-for-finding-a-solution-to-my-path-planning-problem#answer_190664

编辑：John D'Errico 2015-8-28

I fail to see the problem with brute force on this. There are only a very limited number of paths for such a small problem. Just chase down all the possible paths, and take the best one. You need only retain the information of the best path you have found to date. If the current path you search is better, keep it.

In fact, there are better methods, but why bother, unless you have a seriously large problem? For a 4x4 matrix, you have what, a few dozen possible paths? (Note that I recall a Project Euler problem that was quite similar, where those matrices were considerably larger. In that case, you needed to use a more intelligent algorithm.)

If you really wanted to think of a better method, consider the progress diagonally across the matrix. At each step, just keep a record of the most efficient way to reach a given point on the diagonal at that step. As such, no matter how large the matrix is, your algorithm becomes quite a simple one, so for an order nxn matrix, the run time would be something like O(2*n^2) tests.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Walter Roberson 2015-8-28

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/237512-help-for-finding-a-solution-to-my-path-planning-problem#answer_190666

https://en.wikipedia.org/wiki/Dijkstra's_algorithm

You should assign a relative cost corresponding to each of your labels 0 to 4. Label 0 would probably correspond to cost 1. Beyond that you have to decide how much aversion there is to using each label. If something is labeled 3, then how many label 2 steps around it should be taken in preference? Is a label 3 more difficult to travel than two label 2? More difficult than three label 1? The costs do not have to be linear: for example you could use a cost of 2^(the label) for labels 0, 1, 2, 3, and you could use a cost of infinity for label 4. But you have to choose some fixed relative costs to the labels in order to figure out what the least expensive route is.