Shortest Cityblock Path with Multiple Nodes (Goals) with Still Obstacles

Question

Pyro 2015-10-31

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/251979-shortest-cityblock-path-with-multiple-nodes-goals-with-still-obstacles

评论： Image Analyst 2015-11-1

I have spent a great deal of time reading about A* search, Dijkstra’s, and Best-First-Search algorithms. I did an exhausutive search of all m-file exhanges, toolboxes, and whatnot, but I couldn't find a solution to my problem.

As the title suggests, I have a square map (you may call it a grid, or a matrix). I have a predefined starting point, and there are predefined still obstacles. There could be as few as one goal, or there could be multiple nodes.

What I need:

I need to find the shortest cityblock path (moving diagonally isn't allowed) that passes through all goals, and plots the path on the original grid with obstacles and starting point indicated.

To help you visualize the problem, see the image

In this image, the numbers one through eight represent the only possible nodes. The blue blocks are obstacles, and the path cannot pass through it. The gray squares are equivalent to the white ones. I used color just to make it easier to understand the map.

Let me give an example with the desired solution. Assume there are only 2 desired nodes we want to pass by: node 2 and node 8. The output map should look something like this: