tailieunhanh - Artificial Intelligence - Lecturer 4: Search

Outline: Graph search, Best-first search, A* search. If the state space is finite and we avoid repeated states, the search is complete, but in general is not optima. If the state space is finite and we do not avoid repeated states, the search is in general not complete. If the state space is infinite, the search is in general not complete. | Artificial Intelligence For HEDSPI Project Lecturer 4 - Search Lecturers Dr. Le Thanh Huong Dr. Tran Due Khanh Dr. Hai V. Pham School of ICT HUST Outline Graph search Best-first search A search 1 Get from Arad to Bucharest as quickly as possible 2 Graph search function Graph-Search proi tem fringe returns a solution or failure fringe - lnsert Make-Node lnitial-State pro tem fringe closed - an empty set while fringe not empty node - RemoveFirst frfnge if Goal-Test problem state noơe then return Solution noơe if State nocte is not in closed then add State node to closed fringe - lnsertAII Expand nocfe problem fringe end if end return failures Never expand a node twice Straight Line Distances Straight-line distance to Bucharest Arad 366 Bucharest 0 Craiova 160 Dobreta 242 Eforie 161 Fagaras 178 Glurglu 77 Hlrsova 151 Iasi 226 Lugoj 244 Mehadla 241 Neamt 234 Gradea 380 Pi test 98 Ri milieu Vilcea 193 Sibiu 253 Timisoara 329 Urzlcenl 80 Vaslui 199 Zerind 374