The north wind blows the snow and the moon is like silver, the perseverance is never extinguished and the ambition is always new.
The mountain of books has roads and diligence as the path, and the sea of learning has no boundaries and true ambition.
The ocean of knowledge is boundless, and we must work hard to draw new pictures.
Keep chasing your dreams and create a brilliant road in life.
The pre-knowledge of the IDA* algorithm is the A* algorithm and the iterative deepening search algorithm
Article directory
- Primer
- text
-
- explorer’s approach
- IDA* algorithm
-
- analyze
- icon
- the code
Introduction
An explorer accidentally got stuck in a maze while exploring. This maze is very complex, assuming you are an explorer, with many dead ends and forks. The explorer needs to keep exploring in the maze, looking for the shortest path. But fortunately, you left a signal receiving device at the entrance before going down the maze. This device can let you know the straight-line distance from you to the entrance. With limited supplies, the explorer wanted to find the exit by the shortest route. Finally, this clever explorer came up with a brilliant idea…
Text
Explorer’s approach
He used a very long rope. Before setting off, he memorized the straight-line distance from himself to the entrance, and then he tied a large part of the rope to the pillar at the starting point, and tied the other end to himself. The distance that allows him to move freely is exactly the distance that he initially expected to reach the exit, that is, the straight-line distance. After setting off, he will confirm the straight-line distance from himself to the entrance every few dozen steps. If he finds that the number of steps he has taken + the current straight-line distance is more than the straight-line distance when he started If the distance is too large , then he judges that this route does not meet his expectations, so he returns to the starting point on the original road, chooses another road that meets his expectations and continues to find that it does not meet expectations , until all the roads are completed, and return to the starting point; next, he will untie some of the ropes tied to the pillars, so that he can move freely. Go . He repeats the process until he finds the entrance. In addition, When he reaches a dead end, he will return directly to the same place, and will not choose this road when he starts again next time.
IDA* algorithm
Analysis
There is no doubt that this is a clever explorer! At the same time, he may not realize that he is also an extremely talented programmer. The process of finding the entrance is a very classic pathfinding algorithm-the IDA* algorithm.
The IDA* algorithm, as the name suggests, is the process of implementing the A* algorithm by means of IDDFS (Iterative Deepening Search). The specific idea of this algorithm has been shown more clearly in the above example, but let’s explain it more formally.
The IDA* algorithm, like the A* algorithm, also requires an evaluation function: F=G + H, but it has an additional depth limit, which is the expected value of the explorer’s path length to find the exit.
- We initially set the F-value of the starting point to this depth limit, which is the straight-line distance from the entrance that the explorer initially remembers from himself.
- We do DFS from the starting point. In the above example, the explorer chooses a path until the rope on his body does not allow him to go any further, he does not consider other paths. At least not while following this path.
- Repeat this process until all exploreable roads are explored. At this time, we increase the depth limit of the path length to find the exit. For the explorer, it is to untie a part of the rope and increase his expectation of finding the exit.
- When a dead end is found, we go back the same way, the depth limit remains the same, and we won’t go that way again in the next search.
- Repeat this process until an exit is found.
This is the famous IDA* algorithm.
Icon
We still use the example we used in the A* algorithm. The yellow block represents the current search point, the red block represents the path being searched in the current deep search, the light blue block represents the end point, and the black block represents obstacles. Here is an extra green block to mark the path we have searched in the current deep search.
We still use the Manhattan heuristic to estimate
- In the original picture, we set the depth limit at the beginning to the Manhattan value of 8 at the beginning.
- We conduct a deep search in the way of bottom right and top left, first search the nodes below.
- Do a deep search.
- We found that if we go up to this step, the value of the evaluation function will exceed the depth limit, so we went back to the previous grid, but still did not find other paths, and went back to the starting point again, this time we found that the grid on the right did not exceed the depth limit , so search deeply to the right.
(Again, the green grid is the path searched in this round of deep search) - The block below was searched in the previous path, so the block to the right is searched.
- Continue to search deeply, and finally find such a path.
The operation process of the IDA* algorithm is very simple, paste the code below:
Code
#include<algorithm>
#include <iostream>
using namespace std;
typedef struct node {<!-- -->
int x;
int y;
int v;
}node;
node* G;
bool* visited;
int width;//The side length of the graph
int max_depth;
int over;//Mark whether the current path has searched beyond the depth, if so, return all the way to the starting point
int h(node A,node B)//definition point
{<!-- -->
int i, j;
if (B.x > A.x)i = B.x - A.x;
else i = A.x - B.x;
if (B.y > A.y)j = B.y - A.y;
else j = A.y - B.y;
return i + j;
}
void ini()//initialization function
{<!-- -->
scanf("%d", &width);
G = (node*)malloc(sizeof(node) * ((width) * (width)));
visited = (bool*)malloc(sizeof(bool) * (width) * (width));
for (int i = 0; i < (width) * (width); i ++ ) {<!-- -->
G[i].x = i / width;
G[i].y = i % width;
G[i].v = 0;
visited[i] = 0;
}
//Initialize a specific area, for example, the starting block is set to 1, the end block is set to 2, and the obstacle is set to -1
int x;
int y;
int v;
while (scanf("%d %d %d", & amp;x, & amp;y, & amp;v)) {<!-- -->
G[x * width + y].v = v;
}
}
bool blind_alley(node a){<!-- -->}//This function is used to judge whether it is a dead end. The general idea is to see if the surrounding blocks are all paths or obstacles that have been passed before, and if so, return true
bool IDA_star(int g,node a,node b)//g is G in the evaluation function, a is the current search point, b is the end point
{<!-- -->
if (a.v == 1)over = 0;
if (a.x == b.x & amp; & amp; a.y == b.y) return true;//find the end
if (over == 1) return false;
if (g + h(a, b) > max_depth) {<!-- -->
max_depth++;
over = 1;
return false;//Exceeded the evaluation function
}
if (blind_alley(a)) {<!-- -->//found to be a dead end
over = 1;
return false;
}
int self = a.x * width + a.y;
visited[self] = 1;
//Calculate the code by the order of bottom right top left
int below = (a.x + 1) * width + a.y;
int right = a.x * width + (a.y + 1);
int left = a.x * width + (a.y - 1);
int above = (a.x - 1) * width + (a.y);
if (visited[below]==0 & amp; & amp;G[below].v != -1)IDA_star(g + 1, G[below], b);
else if (visited[right] == 0 & amp; & amp; G[right].v != -1)IDA_star(g + 1, G[right], b);
else if (visited[left] == 0 & amp; & amp; G[left].v != -1)IDA_star(g + 1, G[left], b);
else if (visited[above] == 0 & amp; & amp; G[above].v != -1)IDA_star(g + 1, G[above], b);
visited[self] = 0;
}
The IDA* algorithm is over here, I am Shuang_ai, a newcomer working hard on the road of algorithm, thank you Your reading! If you think it is good, you can pay attention to it, and I will bring more and more comprehensive algorithm explanations in the future!