What is the f score?
In the IDA* algorithm, F-score is a heuristic function that is used to estimate the cost of reaching the goal state from a given state. It is a combination of two other heuristic functions, g(n) and h(n).
It is used to determine the order in which the algorithm expands nodes in the search tree and thus, it plays an important role in how quickly the algorithm finds a solution. A lower F-score indicates that a node is closer to the goal state and will be expanded before a node with a higher F-score.
Simply it is nothing but g(n) + h(n).
How IDA* algorithm work?
Step 1: Initialization
Set the root node as the current node, and find the f-score.
Sep 2: Set threshold
Set the cost limit as a threshold for a node i.e the maximum f-score allowed for that node for further explorations.
Step 3: Node Expansion
Expand the current node to its children and find f-scores.
Step 4: Pruning
If for any node the f-score > threshold, prune that node because it’s considered too expensive for that node. and store it in the visited node list.
Step 5: Return Path
If the Goal node is found then return the path from the start node Goal node.
Step 6: Update the Threshold
If the Goal node is not found then repeat from step 2 by changing the threshold with the minimum pruned value from the visited node list. And Continue it until you reach the goal node.
Iterative Deepening A* algorithm (IDA*) – Artificial intelligence
Iterative deepening A* (IDA*) is a graph traversal and path-finding method that can determine the shortest route in a weighted graph between a defined start node and any one of a group of goal nodes. It is a kind of iterative deepening depth-first search that adopts the A* search algorithm’s idea of using a heuristic function to assess the remaining cost to reach the goal.
A memory-limited version of A* is called IDA*. It performs all operations that A* does and has optimal features for locating the shortest path, but it occupies less memory.
Iterative Deepening A Star uses a heuristic to choose which nodes to explore and at which depth to stop, as opposed to Iterative Deepening DFS, which utilizes simple depth to determine when to end the current iteration and continue with a higher depth.