Scribd
Importer
0 vues2 pages

Solution Samples

Le document présente plusieurs états initiaux d'un problème de recherche, en utilisant deux heuristiques différentes : Manhattan et DB. Pour chaque état, il fournit la séquence de mouvements effectués, le coût du chemin et le nombre de nœuds explorés. Les résultats montrent des variations dans le coût du chemin et le nombre de nœuds en fonction de l'heuristique utilisée.

Transféré par

maateonicolas1997
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
0 vues2 pages

Solution Samples

Le document présente plusieurs états initiaux d'un problème de recherche, en utilisant deux heuristiques différentes : Manhattan et DB. Pour chaque état, il fournit la séquence de mouvements effectués, le coût du chemin et le nombre de nœuds explorés. Les résultats montrent des variations dans le coût du chemin et le nombre de nœuds en fonction de l'heuristique utilisée.

Transféré par

maateonicolas1997
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Heuristic: Manhattan

initial state: (2, 0, 3, 1, 7, 4, 5, 8, 6)

[(2, 0, 3, 1, 7, 4, 5, 8, 6), 'LEFT', (0, 2, 3, 1, 7, 4, 5, 8, 6), 'DOWN', (1, 2, 3, 0, 7, 4, 5, 8, 6), 'RIGHT', (1, 2, 3,
7, 0, 4, 5, 8, 6), 'RIGHT', (1, 2, 3, 7, 4, 0, 5, 8, 6), 'DOWN', (1, 2, 3, 7, 4, 6, 5, 8, 0), 'LEFT', (1, 2, 3, 7, 4, 6, 5,
0, 8), 'LEFT', (1, 2, 3, 7, 4, 6, 0, 5, 8), 'UP', (1, 2, 3, 0, 4, 6, 7, 5, 8), 'RIGHT', (1, 2, 3, 4, 0, 6, 7, 5, 8), 'DOWN',
(1, 2, 3, 4, 5, 6, 7, 0, 8), 'RIGHT', (1, 2, 3, 4, 5, 6, 7, 8, 0)] path cost = 11

node count: 54

path cost: 11

Heuristic: DB

initial state: (2, 0, 3, 1, 7, 4, 5, 8, 6)

[(2, 0, 3, 1, 7, 4, 5, 8, 6), 'LEFT', (0, 2, 3, 1, 7, 4, 5, 8, 6), 'DOWN', (1, 2, 3, 0, 7, 4, 5, 8, 6), 'RIGHT', (1, 2, 3,
7, 0, 4, 5, 8, 6), 'RIGHT', (1, 2, 3, 7, 4, 0, 5, 8, 6), 'DOWN', (1, 2, 3, 7, 4, 6, 5, 8, 0), 'LEFT', (1, 2, 3, 7, 4, 6, 5,
0, 8), 'LEFT', (1, 2, 3, 7, 4, 6, 0, 5, 8), 'UP', (1, 2, 3, 0, 4, 6, 7, 5, 8), 'RIGHT', (1, 2, 3, 4, 0, 6, 7, 5, 8), 'DOWN',
(1, 2, 3, 4, 5, 6, 7, 0, 8), 'RIGHT', (1, 2, 3, 4, 5, 6, 7, 8, 0)] path cost = 11

node count: 34

path cost: 11

Heuristic: DB

initial state: (3, 1, 0, 8, 4, 2, 5, 6, 7)

[(3, 1, 0, 8, 4, 2, 5, 6, 7), 'LEFT', (3, 0, 1, 8, 4, 2, 5, 6, 7), 'DOWN', (3, 4, 1, 8, 0, 2, 5, 6, 7), 'LEFT', (3, 4, 1, 0,
8, 2, 5, 6, 7), 'UP', (0, 4, 1, 3, 8, 2, 5, 6, 7), 'RIGHT', (4, 0, 1, 3, 8, 2, 5, 6, 7), 'RIGHT', (4, 1, 0, 3, 8, 2, 5, 6, 7),
'DOWN', (4, 1, 2, 3, 8, 0, 5, 6, 7), 'LEFT', (4, 1, 2, 3, 0, 8, 5, 6, 7), 'DOWN', (4, 1, 2, 3, 6, 8, 5, 0, 7), 'RIGHT',
(4, 1, 2, 3, 6, 8, 5, 7, 0), 'UP', (4, 1, 2, 3, 6, 0, 5, 7, 8), 'LEFT', (4, 1, 2, 3, 0, 6, 5, 7, 8), 'LEFT', (4, 1, 2, 0, 3, 6,
5, 7, 8), 'DOWN', (4, 1, 2, 5, 3, 6, 0, 7, 8), 'RIGHT', (4, 1, 2, 5, 3, 6, 7, 0, 8), 'RIGHT', (4, 1, 2, 5, 3, 6, 7, 8, 0),
'UP', (4, 1, 2, 5, 3, 0, 7, 8, 6), 'LEFT', (4, 1, 2, 5, 0, 3, 7, 8, 6), 'LEFT', (4, 1, 2, 0, 5, 3, 7, 8, 6), 'UP', (0, 1, 2, 4,
5, 3, 7, 8, 6), 'RIGHT', (1, 0, 2, 4, 5, 3, 7, 8, 6), 'RIGHT', (1, 2, 0, 4, 5, 3, 7, 8, 6), 'DOWN', (1, 2, 3, 4, 5, 0, 7,
8, 6), 'DOWN', (1, 2, 3, 4, 5, 6, 7, 8, 0)] path cost = 24

node count: 1542

path cost: 24

Heuristic: Manhattan

initial state: (3, 1, 0, 8, 4, 2, 5, 6, 7)


[(3, 1, 0, 8, 4, 2, 5, 6, 7), 'LEFT', (3, 0, 1, 8, 4, 2, 5, 6, 7), 'DOWN', (3, 4, 1, 8, 0, 2, 5, 6, 7), 'LEFT', (3, 4, 1, 0,
8, 2, 5, 6, 7), 'UP', (0, 4, 1, 3, 8, 2, 5, 6, 7), 'RIGHT', (4, 0, 1, 3, 8, 2, 5, 6, 7), 'RIGHT', (4, 1, 0, 3, 8, 2, 5, 6, 7),
'DOWN', (4, 1, 2, 3, 8, 0, 5, 6, 7), 'LEFT', (4, 1, 2, 3, 0, 8, 5, 6, 7), 'DOWN', (4, 1, 2, 3, 6, 8, 5, 0, 7), 'RIGHT',
(4, 1, 2, 3, 6, 8, 5, 7, 0), 'UP', (4, 1, 2, 3, 6, 0, 5, 7, 8), 'LEFT', (4, 1, 2, 3, 0, 6, 5, 7, 8), 'LEFT', (4, 1, 2, 0, 3, 6,
5, 7, 8), 'DOWN', (4, 1, 2, 5, 3, 6, 0, 7, 8), 'RIGHT', (4, 1, 2, 5, 3, 6, 7, 0, 8), 'RIGHT', (4, 1, 2, 5, 3, 6, 7, 8, 0),
'UP', (4, 1, 2, 5, 3, 0, 7, 8, 6), 'LEFT', (4, 1, 2, 5, 0, 3, 7, 8, 6), 'LEFT', (4, 1, 2, 0, 5, 3, 7, 8, 6), 'UP', (0, 1, 2, 4,
5, 3, 7, 8, 6), 'RIGHT', (1, 0, 2, 4, 5, 3, 7, 8, 6), 'RIGHT', (1, 2, 0, 4, 5, 3, 7, 8, 6), 'DOWN', (1, 2, 3, 4, 5, 0, 7,
8, 6), 'DOWN', (1, 2, 3, 4, 5, 6, 7, 8, 0)] path cost = 24

node count: 4235

path cost: 24

Heuristic: DB

initial state: (4, 5, 1, 6, 8, 7, 3, 0, 2)

[(4, 5, 1, 6, 8, 7, 3, 0, 2), 'LEFT', (4, 5, 1, 6, 8, 7, 0, 3, 2), 'UP', (4, 5, 1, 0, 8, 7, 6, 3, 2), 'RIGHT', (4, 5, 1, 8, 0,
7, 6, 3, 2), 'RIGHT', (4, 5, 1, 8, 7, 0, 6, 3, 2), 'DOWN', (4, 5, 1, 8, 7, 2, 6, 3, 0), 'LEFT', (4, 5, 1, 8, 7, 2, 6, 0, 3),
'LEFT', (4, 5, 1, 8, 7, 2, 0, 6, 3), 'UP', (4, 5, 1, 0, 7, 2, 8, 6, 3), 'RIGHT', (4, 5, 1, 7, 0, 2, 8, 6, 3), 'UP', (4, 0, 1,
7, 5, 2, 8, 6, 3), 'RIGHT', (4, 1, 0, 7, 5, 2, 8, 6, 3), 'DOWN', (4, 1, 2, 7, 5, 0, 8, 6, 3), 'DOWN', (4, 1, 2, 7, 5, 3,
8, 6, 0), 'LEFT', (4, 1, 2, 7, 5, 3, 8, 0, 6), 'LEFT', (4, 1, 2, 7, 5, 3, 0, 8, 6), 'UP', (4, 1, 2, 0, 5, 3, 7, 8, 6), 'UP', (0,
1, 2, 4, 5, 3, 7, 8, 6), 'RIGHT', (1, 0, 2, 4, 5, 3, 7, 8, 6), 'RIGHT', (1, 2, 0, 4, 5, 3, 7, 8, 6), 'DOWN', (1, 2, 3, 4,
5, 0, 7, 8, 6), 'DOWN', (1, 2, 3, 4, 5, 6, 7, 8, 0)] path cost = 21

node count: 330

path cost: 21

Heuristic: Manhattan

initial state: (4, 5, 1, 6, 8, 7, 3, 0, 2)

[(4, 5, 1, 6, 8, 7, 3, 0, 2), 'LEFT', (4, 5, 1, 6, 8, 7, 0, 3, 2), 'UP', (4, 5, 1, 0, 8, 7, 6, 3, 2), 'RIGHT', (4, 5, 1, 8, 0,
7, 6, 3, 2), 'RIGHT', (4, 5, 1, 8, 7, 0, 6, 3, 2), 'DOWN', (4, 5, 1, 8, 7, 2, 6, 3, 0), 'LEFT', (4, 5, 1, 8, 7, 2, 6, 0, 3),
'LEFT', (4, 5, 1, 8, 7, 2, 0, 6, 3), 'UP', (4, 5, 1, 0, 7, 2, 8, 6, 3), 'RIGHT', (4, 5, 1, 7, 0, 2, 8, 6, 3), 'UP', (4, 0, 1,
7, 5, 2, 8, 6, 3), 'RIGHT', (4, 1, 0, 7, 5, 2, 8, 6, 3), 'DOWN', (4, 1, 2, 7, 5, 0, 8, 6, 3), 'DOWN', (4, 1, 2, 7, 5, 3,
8, 6, 0), 'LEFT', (4, 1, 2, 7, 5, 3, 8, 0, 6), 'LEFT', (4, 1, 2, 7, 5, 3, 0, 8, 6), 'UP', (4, 1, 2, 0, 5, 3, 7, 8, 6), 'UP', (0,
1, 2, 4, 5, 3, 7, 8, 6), 'RIGHT', (1, 0, 2, 4, 5, 3, 7, 8, 6), 'RIGHT', (1, 2, 0, 4, 5, 3, 7, 8, 6), 'DOWN', (1, 2, 3, 4,
5, 0, 7, 8, 6), 'DOWN', (1, 2, 3, 4, 5, 6, 7, 8, 0)] path cost = 21

node count: 504

path cost: 21

Vous aimerez peut-être aussi