42 lines
1.4 KiB
TeX
42 lines
1.4 KiB
TeX
\chapter{General Problem-Solving}
|
|
|
|
\section{Uninformed Search}
|
|
An \textbf{uninformed} search algorithm only uses the information available in the problem definition.
|
|
\subsection{Breadth-First Search}
|
|
In breadth first search the fringe of the graph is treated as a FIFO queue.
|
|
|
|
\begin{center}
|
|
\includegraphics[scale=0.5]{ressources/bfs.png}
|
|
\end{center}
|
|
\subsection{Uniform-Cost Search}
|
|
For Graphs with step costs the BFS strategy might choose a suboptimal path.
|
|
Instead, one should use uniform cost search, where the fringe is ordered by increasing step cost.
|
|
\begin{center}
|
|
\includegraphics[scale=1.5]{ressources/ucs.pdf}
|
|
\end{center}
|
|
\subsection{Depth-First Search}
|
|
In depth first search the fringe of the graph is organized as a LIFO stack.
|
|
|
|
\begin{center}
|
|
\includegraphics[scale=0.5]{ressources/dfs.png}
|
|
\end{center}
|
|
|
|
\subsection{Iterative Deepening Search}
|
|
Depth first search may diverge when considering infinite trees,
|
|
instead one can use iterative deepening search, where the search depth is iteratively increased,
|
|
thus yielding a mix of the BFS and DFS search strategies.
|
|
|
|
\section{Informed Search}
|
|
\textbf{Informed} search strategies try to guide the search by using heuristics.
|
|
|
|
\subsection{Heuristics}
|
|
|
|
\subsection{Greedy Search}
|
|
\subsection{A-Star Search}
|
|
|
|
\section{Adversarial Search}
|
|
\subsection{Minimax Search}
|
|
\subsection{Alpha-Beta Search}
|
|
\subsection{Monte-Carlo Tree Search}
|
|
|
|
\section{Constraint Satisfaction Problems}
|