---
# System prepended metadata

title: TD 4 -- Introduction a l'Intelligence Artificielle et à la Theorie des Jeux
tags: [M1 S1, IA, TD]

---

# TD 4 -- Introduction a l'Intelligence Artificielle et à la Theorie des Jeux

###### tags `TD` `M1 S1`  `IA`
[Sommaire](/8Sa-Z4QBS1ep0xPwtzigJA)
> [time= 9 oct 2020]

[TOC]

## Exercice 1
### Enoncer
![](https://i.imgur.com/SvXjXCs.png)

### Réponse

La distance de hamming donne juste le nombre de piece mal placé.

Heuristique en utilisant la distance de manhatan

$$
\begin{align}
h_1 &= |3 - 1| + | 2 - 3| = 2 + 1 = 3\\
h_2 &= 1\\
h_3 &= 2\\
h_4 &= 2\\
h_5 &= 2\\
h_6 &= 3\\
h_7 &= 3\\
h_8 &= 2\\
\\
h_{\text{start state}} &= h_1 + h_2 + h_3 + h_4 + h_5 + h_6 + h_7 + h_8\\
  &=  3  +  1  +  2  +  2  +  2  +  3  +  3  +  2 \\
  &= 18
\end{align}
$$

## Exercice 2
### Enoncer
![](https://i.imgur.com/CqAcLvy.png)
![](https://i.imgur.com/pDyQTXL.png)


### Réponse

#### heuritique
##### 1)
$$
\begin{align}
    Soit: \\
    v_{m} &= 60  km/h \: \text{vitesse dans les parties montante}\\
    v_{d} &= 120 km/h \: \text{vitesse dans les parties déscendante} \\
    v_{p} &= 90  km/h \: \text{vitesse dans les parties plates} \\
    Et: \\
    d_{Xm} &= \text{distance sur les partie montante a vol d'oiseau de X vers B}\\
    d_{Xd} &= \text{distance sur les partie déscendante a vol d'oiseau de X vers B}\\
    d_{Xp} &= \text{distance sur les partie plate a vol d'oiseau de X vers B}\\
    Donc:\\
    h_{X} &= \left(\frac{d_{Xm}}{v_{m}} +
             \frac{d_{Xd}}{v_{d}} + 
             \frac{d_{Xp}}{v_{p}}\right)\times 60\\
          &= \left(\frac{d_{Xm}}{60} +
             \frac{d_{Xd}}{120} + 
             \frac{d_{Xp}}{90}\right)\times 60\\
\end{align}
$$

|      |  A  |  B  |  C  |  D  |  E  |  F  |  G  |  I  |  J  |
|:----:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| h~t~ | 80  |  0  | 57  | 48  | 40  | 53  | 35  | 28  | 23  |
|  t   |     |     |     |     | 35  |     | 30  |     |     |

On a les contre exemple:
- EB ou 35 min (t) < 40 min(h~t~)
- GE ou 35 min (t) < 30 min(h~t~)

L'heuristique associant à X le temps de parcours du chemin à vol d'oiseau de  à B n'est donc pas admissible.

##### 2)
On prend toutes les distance comme des déscentes.
$$
h_{X} = \left(\frac{d_{Xm} + d_{Xd} + d_{Xp}}{120}\right)\times 60
$$
|      |  A  |  B  |  C  |  D  |  E  |  F  |  G  |  I  |  J  |
|:----:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| h~t~ | 55  |  0  | 39  | 31  | 20  | 31  | 25  | 16  | 16  |


|      | A->C | A->I | C->D | C->F | D->E | E->J | E->B | F->E | F->G | G->B | I->J | J->B |
|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:| ---- | ---- |:----:|
| c~t~ |  40  |  75  |  26  |  34  |  11  |  20  |  35  |  24  |  50  | 30   | 25   |  29  |

#### 3) recherche gloutone

```
# (node, parent, c, h)
      [(A, _, 0, 55)] - []
A, 0  [(I, A, 75, 16), (C, A, 40, 55)] [A]
I, 75 [(J, I, 100, 16), (C, A, 40, 57)] [A, I]
J, 100 [(B, J, 129, 0), (C, A, 40, 57), (E, J, 20, 20)] [A, I, J]
B 129

A -> I -> J -> B (cout 129 min- 2h09)
```

#### 4) A*
```
# (node, parent, c, h, f)
      [(A, _, 0, 55, 80)] - []
A, 0  [(C, A, 40, 39, 79), (I, A, 75, 16, 91)] [A]
C, 40 [(I, A, 75, 16, 91), (D, C, 66, 31, 97), (F, C, 74, 31, 105)], [A, C]
I, 75 [(D, C, 66, 31, 97), (F, C, 74, 31, 105), (J, I, 100, 16, 116)], [A, C, I]
D, 66 [(E, D, 77, 20, 97), (F, C, 74, 31, 105), (J, I, 100, 16, 116)], [A, C, I, D]
E, 77 [(F, C, 74, 31, 105), (B, E, 112, 0, 112), (J, I, 100, 16, 116)], [A, C, I, D, E]
F, 74 [(B, E, 112, 0, 112), (J, I, 100, 16, 116), (G, F, 124, 31, 155)], [A, C, I, D, E, F]
B, 112

A -> C -> D -> E -> B (cout 112 min - 1h52)
```

## Exercice 2
### Enoncé
![](https://i.imgur.com/e2S4OMn.png)
1. Donner l’ ́etat initial et l’ ́etat final du problème.
2. Appliquer l’algorithme de recherche à coût uniforme.
3. Donner une fonction heuristique h admissible pour ce problème.
4. Appliquer l’algorithme de recherche gloutonne utilisant h.
5. Appliquer l’algorithme A* utilisant h.
6. On considère la recherche locale qui utilise h pour évaluer les états, à partir de (g, {C}). Est-ce que la recherche termine sur un optimum local qui n’est pas la solution ?
### Réponse

#### 1)
- sommet initial \
    $(g, {\emptyset})$
- sommet final\
    $(d, \{ L, C, S \})$
    
#### 2)
```graphviz
Digraph g{
    edge [arrowhead=none]
    {
    rank = same;
    g [label = "(g, {}) - 5", color=green]
    }
    g -> {
    d [label = "(d, {}) - 6"]
    dl [label = "(d, {L}) - 4", color=red]
    dc [label = "(d, {C}) - 4"]
    ds [label = "(d, {S}) - 4", color=red]
    }
    
    dc -> 
    {
    gc [label="(g, {C}) - 3"]
    }
    
    gc ->
    {
    dlc [label = "(d, {L, C}) - 2"]
    dcs [label = "(d, {C, S}) - 2"]
    }
    dlc ->
    {
    glc [label = "(g, {L, C}) - 1", color=red]
    gl [label = "(g, {L}) - 3"]
    }
    
    dcs ->
    {
    gcs [label = "(g, {C, S}) - 3", color=red]
    gs [label="(g, {S}) - 3"]
    }
    
    gl -> 
    {
    dl [label="(d, {L}) - 4", color=red]
    dls [label="(d, {L, S}) - 2"]
    }
    
    gs ->
    {
    ds [label="(d, {S}) - 4", color=red]
    dls [label="(d, {L, S}) - 2"]
    }
    
    dls ->
    {
        gls [label="(g, {L, S}) - 1"]
    }
    
    gls ->
    {
        dlcs [label="(d, {L, C, S}) - 0", color=magenta]
    }
}
```

#### 3)
$$
\text{prenons comme heuristique} \\
h(d, S) = 6 - 2 * card(S) \\
h(g, S) = 6 - 2 * card(S) - 1
$$

#### 4)
recherche glotonne

```
[()"(g, {})", 1, 5)] []
"(g, {})" 1     [("(d, {C})", 2, 4), ("(d, {})", 2, 6)] ["(g, {})"]
"(d, {C})" 2    [("(g, {C})", 3, 3), ("(d, {})", 2, 6)] ["(g, {})", "(d, {C}) - 4"]
"(g, {C})" 3    [("(d, {L, C})", 4, 2), ("(d, {C, S}), 4, 2), ("(d, {})", 2, 6),] ["(g, {})", "(d, {C}) - 4", "(g, {C})"...]
"(d, {L, C})" 4 [("(d, {C, S}), 4, 2), ("(g, {L})", 5, 3), ("(d, {})", 2, 6),] ["(g, {})", ...]
"(d, {C, S})" 4 [("(g, {L})", 5, 3), ("(g, {S})", 5, 3), ("(d, {})", 2, 6)] ["(g, {})", ...]
("(g, {L})", 5 [("(g, {L, S}), 6, 2)"("(g, {S})", 5, 3), ("(d, {})", 2, 6)] ["(g, {})", ...]
"(g, {L, S})"6, [("(g, {L, S})", 7, 1)"), ("(g, {S})", 5, 3), ("(d, {})", 2, 6)] ["(g, {})", ...]
"(g, {L, S})" 7 ...
"(d, {L, S, C}") 8 

```