Revision f0122a5c2e423926ee41eace62d2d8a583157c14 (click the page title to view the current version)

Heuristic Search

Changes from f0122a5c2e423926ee41eace62d2d8a583157c14 to e6282a32273e1e766ac9da00df2fea0d7ae737df

---
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

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.

My advice is that you focus on the following questions, when you read it the
first time.

1.  What is a heuristic function? (page 102)
    - Whas 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?

# Briefing
# Briefing $A^*$

## 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 . 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? (i) $D(i,j)$; (ii) 
$2\cdot D(i,j)$; (iii) $D(i,j)/2$.
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? (i) $D(i,j)$;
   (ii) $2\cdot D(i,j)$; (iii) $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?
   same city twice?

# Exercises

 
+ [Blunder Episode 2](https://www.codingame.com/training/hard/blunder-episode-2)
    - see [Search]() last week
+ [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)
    + 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?
+ If you want a challenge, there are two more puzzles
  [tagged with A$^*$](https://www.codingame.com/learn/a*).