Artificial Intelligence

Question 1

Admissable heuristic

Answer 1

Incomputer science, specifically inalgorithmsrelated topathfinding, aheuristic functionis said to beadmissibleif it never overestimates the cost of reaching the goal, i.e. the cost it estimates to reach the goal is not higher than the lowest possible cost from the current point in the path.

It is related to the concept ofconsistent heuristics. While all consistent heuristics are admissible, not all admissible heuristics are consistent.

Question 2

Hamming distance

Answer 2

Ininformation theory, theHamming distancebetween twostringsof equal length is the number of positions at which the correspondingsymbolsare different. In other words, it measures the minimum number ofsubstitutionsrequired to change one string into the other, or the minimum number oferrorsthat could have transformed one string into the other.

Question 3

Consistent heuristic

Answer 3

In the study ofpath-finding problemsinartificial intelligence, aheuristic functionis said to beconsistent, ormonotone, if its estimate is always less than or equal to the estimated distance from any neighbouring vertex to the goal, plus the cost of reaching that neighbour.

Formally, for every nodeNand eachsuccessorPofN, the estimated cost of reaching the goal fromNis no greater than the step cost of getting toPplus the estimated cost of reaching the goal fromP.

Question 4

Heuristic

Answer 4

A heuristic function, also simply called a heuristic, is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow. For example, it may approximate the exact solution.

Question 5

Taxicab geometry (Manhattan distance)

Answer 5

A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their Cartesian coordinates.