# Best-First Search

## Introduction

Best-first search is a graph search algorithm that aims to find the optimal path between two nodes in a graph. It is commonly used in artificial intelligence and computer science, particularly in the field of pathfinding. The algorithm works by exploring the most promising nodes first, based on a heuristic function that estimates the distance to the goal node. Best-first search can be used in a variety of applications, such as route planning, game AI, and logistics.

## Implementation

Here is an implementation of Best-first search in OCaml:

```
type 'a node = {
state: 'a;
parent: 'a node option;
cost: float;
heuristic: float;
}
let best_first_search initial_state goal_state successors heuristic =
let is_goal n = n.state = goal_state in
let rec search frontier visited =
match frontier with
| [] -> None
| n :: _ when is_goal n -> Some n
| n :: ns ->
let successors = successors n.state in
let add_node frontier node =
if List.exists (fun n -> n.state = node.state) visited then frontier
else List.merge (fun n1 n2 -> compare n1.cost n2.cost)
frontier [node] in
let nodes = List.map (fun (state, cost) ->
let heuristic = heuristic state in
{state; parent = Some n; cost; heuristic}) successors in
let frontier' = List.fold_left add_node ns nodes in
let visited' = n :: visited in
search frontier' visited'
in
let initial_node = {state = initial_state; parent = None; cost = 0.; heuristic = heuristic initial_state} in
search [initial_node] []
```

Here, `type 'a node`

represents a node in the search tree. Each node has a state, a parent node, a cost (i.e., the cumulative cost from the initial state), and a heuristic value (i.e., the estimated distance to the goal state). The `best_first_search`

function takes as input the initial state, the goal state, a function that generates the successors of a given state, and a heuristic function that estimates the distance to the goal state. The function returns an optional node that represents the goal state, or `None`

if no path was found.

## Example

Here’s an example of using Best-first search to find the shortest path between two cities in a graph:

```
let graph = [
("A", [("B", 7.); ("C", 3.)]);
("B", [("A", 7.); ("C", 1.); ("D", 2.)]);
("C", [("A", 3.); ("B", 1.); ("D", 2.)]);
("D", [("B", 2.); ("C", 2.); ("E", 4.)]);
("E", [("D", 4.)])
]
let successors state =
let rec find_node state = function
| [] -> failwith "Node not found"
| (s, _) :: _ when s = state -> []
| _ :: rest -> find_node state rest
in
let (_, edges) = List.find (fun (s, _) -> s = state) graph in
List.map (fun (s, c) -> (s, c)) edges @ find_node state graph
let heuristic state =
match state with
| "A" -> 6.
| "B" -> 2.
| "C" -> 4.
| "D" -> 2.
| "E" -> 0.
| _ -> failwith "Invalid state"
let path = best_first_search "A" "E" successors heuristic
let print_path path =
let rec print_node node =
match node.parent with
| None -> print_endline node.state
| Some parent ->
print_node parent;
print_endline node.state
in
match path with
| None -> print_endline "No path found"
| Some node -> print_node node
let () = print_path path
```

This code defines a graph as a list of nodes, where each node is a tuple of a state and a list of edges to other nodes, each with a cost. The `successors`

function generates the successors of a given state by looking up the corresponding node in the graph and returning its edges. The `heuristic`

function estimates the distance to the goal state based on a predefined heuristic value for each state.

The `path`

variable contains the result of running Best-first search on the graph, starting from state “A” and ending at state “E”. Finally, the `print_path`

function prints out the path from the initial state to the goal state.

When we run this code, we should see the following output:

```
A
C
D
E
```

This indicates that the shortest path from “A” to “E” is “A” -> “C” -> “D” -> “E”, with a total cost of 9.

## Step-by-step Explanation

- Create a node that represents the initial state, with a cost of 0 and a heuristic value based on the initial state.
- Create an empty list of visited nodes and a list that contains only the initial node as the frontier.
- If the frontier is empty, return
`None`

(i.e., no path was found). - Otherwise, take the node at the front of the frontier and check if it is the goal node. If so, return it.
- Otherwise, generate the successors of the current node, create nodes for each of them, and add them to the frontier.
- Sort the frontier based on the cost of each node (i.e., the cumulative cost from the initial state).
- Add the current node to the list of visited nodes.
- Repeat from step 3.

The key idea behind Best-first search is to explore the most promising nodes first, based on a heuristic function that estimates the distance to the goal node. This allows the algorithm to quickly converge to the optimal path, while avoiding exploring unpromising paths.

## Complexity Analysis

The time complexity of Best-first search depends on the quality of the heuristic function. In the worst case, where the heuristic function is not informative (i.e., it always returns 0), the algorithm degenerates to a breadth-first search, with a time complexity of O(b^d), where b is the branching factor of the graph and d is the depth of the goal node. In the