# 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

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

### 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é
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)

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