Greedy Search
Greedy Search is a search algorithm that selects the frontier node with the lowest heuristic value , meaning the state it estimates to be closest to a goal. It uses a priority queue for its frontier, but unlike Uniform Cost Search, which prioritizes by actual path cost, Greedy prioritizes purely by heuristic values.
It is neither complete nor optimal: it may fail to find a solution even if one exists, and when it does find a solution, it is not guaranteed to be the least-cost path, hence the name. Its behavior is highly dependent on the quality of the heuristic: with a good heuristic, it can quickly reach a goal, but with a poor one, it may behave like a misled depth-first search. Its time and space complexities are in the worst case, where is the maximum search depth.
The following is an example of Greedy Search on a 5x5 grid. Note that since there are no obstacles, the optimal solution is not unique.
\usetikzlibrary{animations}
\begin{document}
\begin{tikzpicture}[scale=0.9, line cap=round, line join=round]
% ---------- Grid (5x5), coordinates, and markers ----------
% Draw grid lines
\foreach \x in {0,...,5} \draw[gray!60] (\x,0) -- (\x,5);
\foreach \y in {0,...,5} \draw[gray!60] (0,\y) -- (5,\y);
% Cell centers Pxy where x=1..5 (left->right), y=1..5 (bottom->top)
\foreach \x in {1,...,5} {
\foreach \y in {1,...,5} {
\coordinate (P\x\y) at (\x-0.5,\y-0.5);
}
}
% Start/Goal labels
\node (S) at (P11) {S};
\node (G) at (P55) {G};
% Convenience
\def\rvis{0.28} % highlight radius
\newcommand{\hbelow}[1]{\node[anchor=north, yshift=-6pt] at (#1.south) {$h=\ifnum#1= P11\relax8\fi$};} % (not used, see explicit labels below)
% ---------- Greedy path with Manhattan h to G(5,5) ----------
% Path: (1,1)->(2,1)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(5,4)->(5,5)
% h values along path: 8,7,6,5,4,3,2,1,0
% Step 0: S (1,1), h=8
\begin{scope}[animate = {myself:: = {:visible = {0s="true", 1s="false", 10s="false", repeats}}}]
\fill[teal, opacity=.35] (P11) circle (\rvis);
\node[anchor=north, yshift=-6pt] at (P11.south) {$h=8$};
\end{scope}
% Step 1: (2,1), h=7
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 1s="true", 2s="false", 10s="false", repeats}}}]
\fill[orange, opacity=.25] (P11) circle (\rvis);
\fill[teal, opacity=.35] (P21) circle (\rvis);
\node[anchor=east, xshift=-4pt, yshift=-2pt] at (P21.west) {$h=7$};
\end{scope}
% Step 2: (3,1), h=6
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 2s="true", 3s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P21} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P31) circle (\rvis);
\node[anchor=east, xshift=-4pt, yshift=-2pt] at (P31.west) {$h=6$};
\end{scope}
% Step 3: (4,1), h=5
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 3s="true", 4s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P21,P31} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P41) circle (\rvis);
\node[anchor=east, xshift=-4pt, yshift=-2pt] at (P41.west) {$h=5$};
\end{scope}
% Step 4: (5,1), h=4
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 4s="true", 5s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P21,P31,P41} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P51) circle (\rvis);
\node[anchor=west, xshift=4pt, yshift=-2pt] at (P51.east) {$h=4$};
\end{scope}
% Step 5: (5,2), h=3
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 5s="true", 6s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P21,P31,P41,P51} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P52) circle (\rvis);
\node[anchor=west, xshift=4pt, yshift=-2pt] at (P52.east) {$h=3$};
\end{scope}
% Step 6: (5,3), h=2
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 6s="true", 7s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P21,P31,P41,P51,P52} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P53) circle (\rvis);
\node[anchor=west, xshift=4pt, yshift=-2pt] at (P53.east) {$h=2$};
\end{scope}
% Step 7: (5,4), h=1
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 7s="true", 8s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P21,P31,P41,P51,P52,P53} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P54) circle (\rvis);
\node[anchor=west, xshift=4pt, yshift=-2pt] at (P54.east) {$h=1$};
\end{scope}
% Step 8: Goal (5,5), h=0
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 8s="true", 9s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P21,P31,P41,P51,P52,P53,P54} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.45] (P55) circle (\rvis);
\node[anchor=west, xshift=4pt, yshift=-2pt] at (P55.east) {$h=0$};
\end{scope}
\end{tikzpicture}
\end{document}\usetikzlibrary{animations}
\begin{document}
\begin{tikzpicture}[scale=0.9, line cap=round, line join=round]
% ===== Grid (5x5), coordinates, and markers =====
\foreach \x in {0,...,5} \draw[gray!60] (\x,0) -- (\x,5);
\foreach \y in {0,...,5} \draw[gray!60] (0,\y) -- (5,\y);
% Cell centers Pxy where x=1..5 (left→right), y=1..5 (bottom→top)
\foreach \x in {1,...,5} {
\foreach \y in {1,...,5} {
\coordinate (P\x\y) at (\x-0.5,\y-0.5);
}
}
% Start/Goal
\node at (P11) {S};
\node at (P55) {G};
% ===== Obstacles (black filled squares) =====
% A vertical wall with a single choke to force Greedy's unique up-first route
\fill[black] (1,1) ++(1-1,2-1) rectangle ++(1,1); % (2,2)
\fill[black] (1,1) ++(1-1,3-1) rectangle ++(1,1); % (2,3)
\fill[black] (1,1) ++(1-1,4-1) rectangle ++(1,1); % (2,4)
\fill[black] (1,1) ++(2-1,4-1) rectangle ++(1,1); % (3,4)
\fill[black] (1,1) ++(3-1,4-1) rectangle ++(1,1); % (4,4)
% (Gap at (2,5)) so top corridor is open; right edge open
% ===== Greedy (Manhattan to G at (5,5)); tie-break: Up over Right =====
% Path (unique under tie-break): (1,1)->(1,2)->(1,3)->(1,4)->(1,5)->(2,5)->(3,5)->(4,5)->(5,5)
% Manhattan h along this path: 8,7,6,5,4,3,2,1,0
\def\rvis{0.28}
% Step 0: (1,1), h=8
\begin{scope}[animate = {myself:: = {:visible = {0s="true", 1s="false", 10s="false", repeats}}}]
\fill[teal, opacity=.35] (P11) circle (\rvis);
\node[anchor=north, yshift=-6pt] at (P11.south) {$h=8$};
\end{scope}
% Step 1: (1,2), h=7 (Up preferred on tie)
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 1s="true", 2s="false", 10s="false", repeats}}}]
\fill[orange, opacity=.25] (P11) circle (\rvis);
\fill[teal, opacity=.35] (P12) circle (\rvis);
\node[anchor=east, xshift=-4pt, yshift=-2pt] at (P12.west) {$h=7$};
\end{scope}
% Step 2: (1,3), h=6
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 2s="true", 3s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P12} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P13) circle (\rvis);
\node[anchor=east, xshift=-4pt, yshift=-2pt] at (P13.west) {$h=6$};
\end{scope}
% Step 3: (1,4), h=5
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 3s="true", 4s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P12,P13} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P14) circle (\rvis);
\node[anchor=east, xshift=-4pt, yshift=-2pt] at (P14.west) {$h=5$};
\end{scope}
% Step 4: (1,5), h=4
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 4s="true", 5s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P12,P13,P14} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P15) circle (\rvis);
\node[anchor=east, xshift=-4pt, yshift=-2pt] at (P15.west) {$h=4$};
\end{scope}
% Step 5: (2,5), h=3 (right through the gap)
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 5s="true", 6s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P12,P13,P14,P15} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P25) circle (\rvis);
\node[anchor=north, yshift=-6pt] at (P25.south) {$h=3$};
\end{scope}
% Step 6: (3,5), h=2
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 6s="true", 7s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P12,P13,P14,P15,P25} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P35) circle (\rvis);
\node[anchor=north, yshift=-6pt] at (P35.south) {$h=2$};
\end{scope}
% Step 7: (4,5), h=1
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 7s="true", 8s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P12,P13,P14,P15,P25,P35} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.35] (P45) circle (\rvis);
\node[anchor=north, yshift=-6pt] at (P45.south) {$h=1$};
\end{scope}
% Step 8: (5,5), h=0 (Goal)
\begin{scope}[animate = {myself:: = {:visible = {0s="false", 8s="true", 9s="false", 10s="false", repeats}}}]
\foreach \n in {P11,P12,P13,P14,P15,P25,P35,P45} {\fill[orange, opacity=.25] (\n) circle (\rvis);}
\fill[teal, opacity=.45] (P55) circle (\rvis);
\node[anchor=west, xshift=4pt, yshift=-2pt] at (P55.east) {$h=0$};
\end{scope}
\end{tikzpicture}
\end{document}