## Revision 0c68f46a3a43966ac49ca9ae7ca5e85e5fa2b864 (click the page title to view the current version)

# Heuristic Search

## Changes from 0c68f46a3a43966ac49ca9ae7ca5e85e5fa2b864 to current

--- title: Heuristic Search categories: session --- # Reading + R&N Chapter 3.5: The *A$^*$ Algorithm* + R&N Chapter 3.6: Design of heuristic function + plus the summary of Chapter 3 You may want to focus on Question 1-2 below when you k + Watch the Videoes 1. [The State Machine](heuristic01.mp4) (or [OGG format](heuristic01.ogg)) 2. [The Heuristic Function & Greedy Search](heuristic02.mp4) (or [OGG format](heuristic02.ogg)) 3. [A*](heuristic03.mp4) (or [OGG format](heuristic03.ogg)) + Read the text book + R&N Chapter 3.5: The *A$^*$ Algorithm* + R&N Chapter 3.6: Design of heuristic function + plus the summary of Chapter 3 Note that these two sections of the chapter really only gives you *one* (1) algorithm, the *A$*$* Algorithm. Howeever, it exists in many different variants, and it depends on a heuristic function which also has to be designed and varied. on the heuristic function which also has to be designed and varied. My advice is that you focus on the following questions, when you read it the first time. # Briefing ## Evaluation as Reference Group (postponed from [last session](Search)) 1. Generic Questions + Are you comfortable with the goals of the module? + Do you make progress when you do exercises? + Are you able to complete exercises? + Do you gain skills that you feel that you can use in the future? 2. Alter-Begin-Continue (Yellow Stickers Exercise) ## Review Discussion We discuss the following questions in class: 1. What is a heuristic function? (page 102) - What is an *admissible* heuristic function? (page 103) 2. How can you use A$^*$ to solve one problem? Consider either the travel to Bucharest from the textbook, or a problem you have already studied. In class, and when you reread the chapter, you may focus on the following questions. 3. How can you vary A$^*$ to solve other problems? 4. How can you vary the heuristic function $h(x)$ for different problems? # Video Briefing 1. [The State Machine](heuristic01.mp4) 2. [The Heuristic Function & Greedy Search](heuristic02.mp4) 3. [A*](heuristic03.mp4) 5. How can we measure run time or time complexity for tree searches? # AIMA Exercise 3.5 # Discussion Exercise (AIMA Exercise 3.5) *Taken from the [exercises at github](https://aimacode.github.io/aima-exercises/search-exercises/).* Suppose two friends live in different cities on a map, such as the Romania map shown in the textbook. On every turn, we can simultaneously move each friend to a neighboring city on the map. The amount of time needed to move from city i to neighbor j is equal to the road distance d(i,j) between the cities, but on each turn the friend that arrives first must wait until the other one arrives (and calls the first on his/her cell phone) before the next turn can begin. We want the two friends to meet as quickly as possible. 1. Write a detailed formulation for this search problem. (You will find it helpful to define some formal notation here.) 2. Let $D(i,j)$ be the straight-line distance between cities $i$ and $j$. Which of the following heuristic functions are admissible? - $D(i,j)$; - $2\cdot D(i,j)$; - $D(i,j)/2$. 3. Are there completely connected maps for which no solution exists? 4. Are there maps in which all solutions require one friend to visit the same city twice? # Exercises # Programming Exercises + [Blunder Episode 2](https://www.codingame.com/training/hard/blunder-episode-2) - see [Search]() last week + [Train Passenger](https://www.codingame.com/ide/puzzle/train-passenger) is a shortest path problem + [A$^*$ Exercise](https://www.codingame.com/training/medium/a-star-exercise) - Implement A$^*$. The heuristic function is given. # Rebriefing - heuristic functions # Exercises + [11-puzzle](https://www.codingame.com/training/hard/11-puzzle) + The 11-Puzzle + It may be a good idea to test two different heuristics. + What is the search depth in the test cases? + How many nodes are created in the test cases? + [11-puzzle at CodingGame](https://www.codingame.com/training/hard/11-puzzle) + [pai-exercises](https://github.com/hgeorgsch/pai-exercises/tree/main/Puzzle) provides a framework to solve $N$-Puzzle for arbitrary $N$, with sample solutions. + If you want a challenge, there are two more puzzles [tagged with A$^*$](https://www.codingame.com/learn/a*). # Debrief Early debrief at 2.15 today. Discuss one programming exercises.