---

Algorithm

The steps of generic search on \(G = (V, E)\), given

• a starting vertex \(v_1 \in V\) and
• a goal predicate \(g : (v_1, \ldots, v_k) \to \mathbb{B}\)

are:

1. start with the frontier \(F = \{(v_1)\}\) and seen vertices \(S = \{v_1\}\)
2. if \(|F| = 0\), return empty-handed (\(\bot\))
3. remove some path \(p = (v_1, \ldots, v_k)\) from \(F\)
4. when the goal predicate \(g(p)\) is true ⁷, return \(p\) as the solution
5. select \(N = \{(v_1, v_2, \ldots, v_k, v^*) : v^* \notin S \land (v_k, v^*) \in E\}\)
6. for each \(n \in N\), insert \(n\) to \(F\)
7. for each \((v_1, v_2, \ldots, v_k, v^*) \in N\), insert \(v^*\) to \(S\)
8. go to step 2.