# Tree search Algorithm

• Blind search algorithms (e.g. “Breadth-first” and “Depth-first”) use a fixed strategy to methodically traverse the search tree. Blind search is not suitable for complex problems as the the large search space makes them impractical given time and memory constraints.
• Best-first search algorithms (e.g. “Greedy” and “A*”) use a heuristic function to determine the order in which nodes are traversed, giving preference to states that are judged to be most likely to reach the required goal. Using a “heuristic” search strategy reduces the search space to a more manageable size.

# Formula

• G — G is the cost of moving from one node to the other node. This parameter changes for every node as we move up to find the most optimal path.
• H — H is the heuristic/estimated path between the current code to the destination node. This cost is not actual but is, in reality, a guess cost that we use to find which could be the most optimal path between our source and destination.

# A * Search Explanation

• Add start node to list
• For all the neighbouring nodes, find the least cost F node
• Switch to the closed list
• For 8 nodes adjacent to the current node
• If the node is not reachable, ignore it. Else
• If the node is not on the open list, move it to the open list and calculate f, g, h.
• If the node is on the open list, check if the path it offers is less than the current path and change to it if it does so.
• Stop working when
• You find the destination
• You cannot find the destination going through all possible points
`1. let the openList equal empty list of nodes2. let the closedList equal empty list of nodes3. put the startNode on the openList (leave it's f at zero)4. while the openList is not empty5.                    let the currentNode equal the node with the least f value6.                    remove the currentNode from the openList7.                    add the currentNode to the closedList8.                    if currentNode is the goal10.9.                           You've found the end!10.                 let the children of the currentNode equal the adjacent nodes11.                  for each child in the children12.                         if child is in the closedList13.                               continue to beginning of for loop14.                         child.g = currentNode.g + distance between child and current15.                        child.h = distance from child to end16.                        child.f = child.g + child.h17.                        if child.position is in the openList's nodes positions18.                            if the child.g is higher than the openList node's g19.                                        continue to beginning of for loop20.                            add the child to the openList`

# Jobs

--

--

--

## More from Santosh Pandey

AI subject matter expert

Love podcasts or audiobooks? Learn on the go with our new app.

## Santosh Pandey

AI subject matter expert