Lecture - 4 Informed State Space Search

Lecture Series on Artificial Intelligence by Prof. P. Dasgupta, Department of Computer Science & Engineering, I.I.T,kharagpur. For More details on NPTEL visit http://nptel.iitm.ac.in

Category:

Education

Tags:

• Informed
• State
• Space
• Search

[sammysoil77]

@BobK5228 You can only move one tile at a time. If tiles are "perturbed" during the process of taking a tile X from its start to finish position, then it takes longer than the Manhattan distance D(X) between those positions to do so because you have to make D(X) moves, then a move for each "perturbation" of the other tiles. For each tile X, the time it takes to get from start to finish T(X) must therefore obey T(X) >= D(X). Therefore (time to finish game)_>= (sum over D(X))

[BobK5228]

...would yield an average total move count, but there will be initial conditions and tile move sequences which, whether by chance or exquisitely tuned execution plan, will yield a toal move count much smaller than the simple sum of all the initial distances to the final state.

[BobK5228]

The process of moving one tile from its starting position to its final position DOES perturb the original positions of other tiles. Tiles that have been perturbed from their original positions may now be either more or fewer manhattan distance steps away from their original positions. Unless I'm totally missing the point here, it seems possible to me that the average altered distance from original positions of those perturbed tiles could be lower. And it seems possible that the same would hold

[kaladze]

@mixmasterxp node7 = 11 ( the heuristic value of the node) + 1 + 3 + 2 (6) = 11+6=17 

[tarun7597]

cool eh

[mixmasterxp]

35:12 how is the g value for node7 = 6?

[thenetcowboy]

jaja si esta chistoso el tipo

[Daghead]

50 seconds: lol

[mertturkiye]

this movie is buyyed

[waqaswagan]

damn good