search

iridia-ulb / INFOH410

Material and code for the practical sessions for the course: Techniques of AI [INFOH410]
MIT License
9 stars 11 forks source link

TP1 - Q3 - h not so admissible? #8

Open loupwolf opened 3 months ago

loupwolf commented 3 months ago

Hi, it seems to me that, in the TP1, the "h" function of the Q3 is not admissible because it overestimates the remaining distance from B to G2. The A* algorithm can't find the shortest path "('SBEG2', 13)". Instead it converges towards "('SACDG1', 14)". bugTAI

Best regards, Loup

KenN7 commented 3 months ago

Hi :) Yes indeed, h is not admissible in this case, the exercise does not make any assumptions on this. In this case, A* does not find an optimal solution, congrats on finding the trick ;) I agree this could be more clear in the exercise, either by adding a disclaimer on the possible "non-admissibility" of h, or by making h admissible by e.g. changing the B-1->E to a B-3->E