-
Notifications
You must be signed in to change notification settings - Fork 0
/
optimal_search.tex
110 lines (98 loc) · 4.23 KB
/
optimal_search.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
\section{Nets and Optimal Search}
\subsection{British Museum procedure}
Find all possible paths and select the best one from them.
\subsection{Branch and Bound}
\begin{itemize}
\item Form a one-element queue consisting of a zero-length path
that contains only the root node
\item Until the first path in the queue terminates at the
goal node or the queue is empth:
\begin{itemize}
\item Remove the first path from the queue; create new paths
by extending the first path to all the neighbors
of the terminal node
\item Reject all new paths with loops
\item add the remaining new paths, if any, to the queue
\item Sort the entire queue by path length with
least-cost paths in front
\end{itemize}
\item If the goal node is gound, annouce success; otherwise,
annouce failure
\end{itemize}
\subsection{Branch and Bound with lower-bound estimate}
\begin{itemize}
\item Form a one-element queue consisting of a zero-length path
that contains only the root node
\item Until the first path in the queue terminates at the
goal node or the queue is empth:
\begin{itemize}
\item Remove the first path from the queue; create new paths
by extending the first path to all the neighbors
of the terminal node
\item Reject all new paths with loops
\item Add the remaining new paths, if any, to the queue
\item Sort the entire queue by \textbf{the sum of the path
length and a lower-bound estimate of the cost
remaining, with least-cost paths in front}
\end{itemize}
\item If the goal node is gound, annouce success; otherwise,
annouce failure
\end{itemize}
\subsection{Branch and Bound with dynamic programming}
\begin{itemize}
\item Form a one-element queue consisting of a zero-length path
that contains only the root node
\item Until the first path in the queue terminates at the
goal node or the queue is empth:
\begin{itemize}
\item Remove the first path from the queue; create new paths
by extending the first path to all the neighbors
of the terminal node
\item Reject all new paths with loops
\item Add the remaining new paths, if any, to the queue
\item \textbf{if two or more paths reach a common node,
delete all those paths except the one that reaches the
common node with the minimum cost}
\item Sort the entire queue by \textbf{the sum of the path
length with least-cost paths in front}
\end{itemize}
\item If the goal node is gound, annouce success; otherwise,
annouce failure
\end{itemize}
\subsection{A* procedure - Branch and bound with Underestimates
and Dynamic Programming}
\begin{itemize}
\item Form a one-element queue consisting of a zero-length path
that contains only the root node
\item Until the first path in the queue terminates at the
goal node or the queue is empth:
\begin{itemize}
\item Remove the first path from the queue; create new paths
by extending the first path to all the neighbors
of the terminal node
\item Reject all new paths with loops
\item Add the remaining new paths, if any, to the queue
\item \textbf{if two or more paths reach a common node,
delete all those paths except the one that reaches the
common node with the minimum cost}
\item Sort the entire queue by \textbf{the sum of the path
length and a lower-bound estimate of the cost
remaining, with least-cost paths in front}
\end{itemize}
\item If the goal node is gound, annouce success; otherwise,
annouce failure
\end{itemize}
\subsection{Which optimal search method is good for me?}
\begin{itemize}
\item The British Museum procedure is good only when the
search tree is small
\item Branch-and-bound search is good when the tree is big
and bad paths turn distinctly bad quickly
\item Branch-and-bound search with a guess is good when
there is a good lower-bound estimate of the distance
remaining to the goal
\item Dynamic programming is good when many paths convers
on the same place
\item The A* procedure is good when both branch-and-bound
search with a guess and dynamic programming are good
\end{itemize}