{"id":235,"date":"2023-12-31T18:45:48","date_gmt":"2023-12-31T18:45:48","guid":{"rendered":"https:\/\/alandix.com\/aibook\/?page_id=235"},"modified":"2025-04-21T14:47:19","modified_gmt":"2025-04-21T14:47:19","slug":"chap04","status":"publish","type":"page","link":"https:\/\/alandix.com\/aibook\/second-edition\/toc2e\/chap04\/","title":{"rendered":"Chapter 4 \u2013 Search"},"content":{"rendered":"<div class=\"embedurl\" data-url=\"https:\/\/alandix.com\/books\/aibook\/content\/chaps\/chap04.html\" ><!--  Chapter 4 Search  -->\n\n<script>\nvar chapnos = 4;\nvar json_url = \"https:\\\/\\\/alandix.com\\\/books\\\/aibook\\\/content\\\/chaps\\\/chap04.json\";\n<\/script>\n\n\n\n\n\t<object style=\"width:100%; aspect-ratio: 10 \/ 7;\" type=\"application\/pdf\" data=\"https:\/\/alandix.com\/books\/aibook\/content\/slides-pdf\/AI-chap-04.pdf\"><\/object>\n\t<p> Download <a href=\"https:\/\/alandix.com\/books\/aibook\/content\/slides-pptx\/AI-chap-04.pptx\" download>chapter slides<\/a><\/p>\n\n\n<h3> Contents <\/h3>\n<div class=\"toc\">\n<dl>\n<dt>4.1&nbsp;&nbsp;Introduction<\/dt><dd><dl>\n<dt>4.1.1&nbsp;&nbsp;Types of Problem<\/dt>\n<dt>4.1.2&nbsp;&nbsp;Structuring the Search Space<\/dt>\n<\/dl><\/dd>\n<dt>4.2&nbsp;&nbsp;Exhaustive Search and Simple Pruning<\/dt><dd><dl>\n<dt>4.2.1&nbsp;&nbsp;Depth and Breadth First Search<\/dt>\n<dt>4.2.2&nbsp;&nbsp;Comparing Depth and Breadth First Searches<\/dt>\n<dt>4.2.3&nbsp;&nbsp;Programming and Space Costs<\/dt>\n<dt>4.2.4&nbsp;&nbsp;Iterative Deepening and Broadening<\/dt>\n<dt>4.2.5&nbsp;&nbsp;Finding the Best Solution -- Branch and Bound<\/dt>\n<dt>4.2.6&nbsp;&nbsp;Graph Search<\/dt>\n<\/dl><\/dd>\n<dt>4.3&nbsp;&nbsp;Heuristic Search<\/dt><dd><dl>\n<dt>4.3.1&nbsp;&nbsp;Hill Climbing and Best First -- Goal-directed Search<\/dt>\n<dt>4.3.2&nbsp;&nbsp;Finding the Best Solution -- The {A${}^*$} Algorithm<\/dt>\n<dt>4.3.3&nbsp;&nbsp;Inexact Search<\/dt>\n<\/dl><\/dd>\n<dt>4.4&nbsp;&nbsp;Knowledge-rich Search<\/dt><dd><dl>\n<dt>4.4.1&nbsp;&nbsp;Constraint Satisfaction<\/dt>\n<\/dl><\/dd>\n<dt>4.5&nbsp;&nbsp;Summary<\/dt>\n<\/dl><\/div>\n\n\n<h3> Glossary items referenced in this chapter <\/h3>\n<div class=\"toc\">\n<strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/a%2A%20algorithm\">A* algorithm<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/adversarial%20search\">adversarial search<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/backtracking\">backtracking<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/best%20first%20search\">best first search<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/blind%20search\">blind search<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/branch%20and%20bound%20search\">branch and bound search<\/a><\/strong>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/branching%20factor\">branching factor<\/a><\/strong>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/breadth%20first%20search\">breadth first search<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/closed%20list\">closed list<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/combinatorial%20explosion\">combinatorial explosion<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/computer%20chess\">computer chess<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/constraint%20propagation\">constraint propagation<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/constraint%20satisfaction\">constraint satisfaction<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/constraints\">constraints<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/depth%20first%20search\">depth first search<\/a><\/strong>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/depth%20of%20search%20tree\">depth of search tree<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/deterministic\">deterministic<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/deterministic%20search\">deterministic search<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/directed%20graph\">directed graph<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/domain-independent%20knowledge\">domain-independent knowledge<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/domain-specific%20knowledge\">domain-specific knowledge<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/eight%20queens%20problem\">eight queens problem<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/euclidean%20distance\">Euclidean distance<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/exponential%20growth\">exponential growth<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/feasible%20solution\">feasible solution<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/feasible%20state\">feasible state<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/firewalls\">firewalls<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/fitness%20landscape\">fitness landscape<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/forgetful%20hill%20climbing\">forgetful hill climbing<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/game%20playing\">game playing<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/game%20tree\">game tree<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/game%20tree%20search\">game tree search<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/generate%20and%20test\">generate and test<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/generations\">generations<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/genes\">genes<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/genetic%20algorithm\">genetic algorithm<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/genotype\">genotype<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/global%20minimum\">global minimum<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/go\">Go<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/goal%20state\">goal state<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/godel%2C%20kurt\">G&amp;ouml;del, Kurt<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/graph%20search\">graph search<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/hardy%2C%20thomas\">Hardy, Thomas<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/heuristic%20evaluation%20function\">heuristic evaluation function<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/heuristic%20search\">heuristic search<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/hill%20climbing%20algorithm\">hill climbing algorithm<\/a><\/strong>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/hill%20climbing%20with%20backtracking\">hill climbing with backtracking<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/hybrid%20problems\">hybrid problems<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/inexact%20search\">inexact search<\/a><\/strong>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/iterative%20broadening\">iterative broadening<\/a><\/strong>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/iterative%20deepening\">iterative deepening<\/a><\/strong>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/knowledge-rich%20search\">knowledge-rich search<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/local%20minimum\">local minimum<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/logic\">logic<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/lower%20bound\">lower bound<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/magic%20square\">magic square<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/manhattan%20block%20distance\">Manhatten block distance<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/mathematical%20optimisation\">mathematical optimisation<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/means-ends%20analysis\">means&amp;ndash;ends analysis<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/minimax%20search\">minimax search<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/natural%20selection\">natural selection<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/noughts%20and%20crosses\">noughts and crosses<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/open%20list\">open list<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/optimal\">optimal<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/optimisation\">optimisation<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/partial%20state\">partial state<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/phenotype\">phenotype<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/plateau\">plateau<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/probability\">probability<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/prolog\">Prolog<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/pruning\">pruning<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/random%20walk\">random walk<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/ridge\">ridge<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/satisficing\">satisficing<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/search%20horizon\">search horizon<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/search%20space\">search space<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/search%20strategies\">search strategies<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/search%20tree\">search tree<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/search%21optimisation\">search!optimisation<\/a>, <strong><a href=\"https:\/\/alandix.com\/glossary\/aibook\/simulated%20annealing\">simulated annealing<\/a><\/strong>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/solution%20path\">solution path<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/solution%20state\">solution state<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/stuttering%20in%20search%20trees\">stuttering in search trees<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/towers%20of%20hanoi\">Towers of Hanoi<\/a>, <a href=\"https:\/\/alandix.com\/glossary\/aibook\/travelling%20salesman%20problem\">travelling salesman problem<\/a><\/div>\n\n\n\n<h3> Prolog examples (from 1st ed.) <\/h3>\n<!--  Chapter 4 - Search  -->\n\n<table class=\"prolog-listing\">\n\n<tr valign=\"top\"><td class=\"filename\"><a href=\"https:\/\/alandix.com\/code\/ai96\/prolog\/view\/ch3\/gentest.p\">gentest.p<\/a><\/td><td>generate and test<\/td>\n<\/tr>\n\n<tr valign=\"top\"><td class=\"filename\"><a href=\"https:\/\/alandix.com\/code\/ai96\/prolog\/view\/ch3\/prune.p\">prune.p<\/a><\/td><td>search tree pruning<\/td>\n<\/tr>\n\n<tr valign=\"top\"><td class=\"filename\"><a href=\"https:\/\/alandix.com\/code\/ai96\/prolog\/view\/ch3\/hanext.p\">hanext.p<\/a><\/td><td>hanoi search graph 1<\/td>\n<\/tr>\n\n<tr valign=\"top\"><td class=\"filename\"><a href=\"https:\/\/alandix.com\/code\/ai96\/prolog\/view\/ch3\/hanint.p\">hanint.p<\/a><\/td><td>hanoi search graph 2<\/td>\n<\/tr>\n\n<tr valign=\"top\"><td class=\"filename\"><a href=\"https:\/\/alandix.com\/code\/ai96\/prolog\/view\/ch3\/proof.p\">proof.p<\/a><\/td><td>addition proof graph<br>closed lists<\/td>\n<\/tr>\n\n<\/table\n\n\n\n\n<\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":2,"featured_media":0,"parent":221,"menu_order":4,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_themeisle_gutenberg_block_has_review":false,"footnotes":""},"class_list":["post-235","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/pages\/235","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/comments?post=235"}],"version-history":[{"count":2,"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/pages\/235\/revisions"}],"predecessor-version":[{"id":344,"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/pages\/235\/revisions\/344"}],"up":[{"embeddable":true,"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/pages\/221"}],"wp:attachment":[{"href":"https:\/\/alandix.com\/aibook\/wp-json\/wp\/v2\/media?parent=235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}