In this chapter, we'll look at how to perform a search, and we will cover the basic requirements of implementing a search algorithm. We'll then practice by implementing Dijkstra's algorithm, before moving on to heuristics, showing how they can be used in search algorithms to improve the accuracy of search results.
Let's look at what it means to search. If we want to apply a search to any problem, we will need four pieces of input, which are referred to as the state space, and are as follows:
[S, s, O, G]
The preceding types of input can be described as follows:
- S: A set of implicitly given states—all of the states that might be explored in a search process.
- s: The start symbol—the starting point of the search.
- O: The state transition operators, which indicate how a search should proceed from one node to the next and what transitions are available to the search. This is an exhaustive list. Therefore, the state transition operator keeps track of these exhaustive lists.
- G: The goal node, pointing to where the search should end.
With the preceding information, we can find the following values:
- The minimum cost transaction for a goal state
- A sequence of transitions to a minimum cost goal
- A minimum cost transaction for a minimum cost goal
Let's consider the following algorithm, which assumes that all operators have a cost:
- Initialize: Set OPEN = {s},
CLOSE = {}, Set C(s) = 0
- Fail: If OPEN = {}, Terminate with Failure
- Select: Select the minimum cost state, n, form OPEN, and Save n in CLOSE
- Terminate: If n ∈ G, Terminate with Success
- Expand: Generate the successors of n using 0
For each successor, m, insert m in OPEN only if m ∉ [OPEN ∪ CLOSE]
Set C(m) = C(n) + C(n,m)
and insert m in OPEN
if m ∈ [OPEN ∪ CLOSE]
Set C(m) = min{ C(m), C(n) + C(m,n)}
If C(m) has decreased and m ∈ CLOSE move it to OPEN
- Loop: Go to Step 2
Each state of the preceding algorithm can be described as follows:
- Initialize: We initialize the algorithm and create a data structure called OPEN. We put our start state, s, into this data structure, and create one more data structure, CLOSE, which is empty. All of the states that we'll be exploring will be taken from OPEN and put into CLOSE. We set the cost of the initial start state to 0. This will calculate the cost incurred when traveling from the start state to the current state. The cost of traveling from the start state to the start state is 0; that's why we have set it to 0.
- Fail: In this step, if OPEN is empty, we will terminate with a failure. However, our OPEN is not empty, because we have s in our start state. Therefore, we will not terminate with a failure.
- Select state: Here, we will select the minimum cost successor, n, and we'll take it from OPEN and save it in CLOSE.
- Terminate: In this step, we'll check whether n belongs to the G. If yes, we'll terminate with a success.
- Expand: If our n does not belong to G, then we need to expand G by using our state transition operator, as follows:
- If it is a new node, m, and we have not explored it, it means that it is not available in either OPEN or CLOSE, and we'll simply calculate the cost of the new successor (m) by calculating the cost of its predecessor plus the cost of traveling from n to m, and we'll put the value into OPEN
- If it is a part of both OPEN and CLOSE, we'll check which one is the minimum cost—the current cost or the previous cost (the actual cost that we had in the previous iteration)—and we'll keep that cost
- If our m gets decreased and it belongs to CLOSE, then we will bring it back to OPEN
- Loop: We will keep on doing this until our OPEN is not empty, or until our m does not belong to G.
Consider the example illustrated in the following diagram:
Initially, we have the following algorithm:
n(S) = 12 | s = 1 | G = {12}
In the preceding algorithm, the following applies:
- n(S) is the number of states/nodes
- s is the start node
- G is the goal node
The arrows are the state transition operators. Let's try running this, in order to check that our algorithm is working.
Iteration 1 of the algorithm is as follows:
Step 1: OPEN = {1}, C(1) = 0 | CLOSE = { }; here C(1) is cost of node 1
Step 2: OPEN ≠ { }; go to Step 3
Step 3: n = 1 | OPEN = { } | CLOSE = {1}
Step 4: Since n ∉ G; Expand n=1
We get m = {2, 5}
{2} ∉ [OPEN ∪ CLOSE] | {5} ∉ [OPEN ∪ CLOSE]
C(2) = 0 + 2 = 2 | C(5) = 0 + 1 = 1 | OPEN = {2,5}
Loop to Step 2
Iteration 2 is as follows:
Step 2: OPEN ≠ { } so Step 3
Step 3: n = 5 since min{C(2),C(5)}...
