2

If a heuristic is not admissible, can it be consistent? No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency. In other words, an admissible heuristic is not necessarily consistent. Definitions Given a graph $G=(V, E)$ representing the search space, ...


2

For a heuristic to be admissible, it must never overestimate the distance from a state to the nearest goal state. For a heuristic to be consistent, the heuristic's value must be less than or equal to the cost of moving from that state to the state nearest the goal that can be reached from it, plus the heurstic's estimate for that state. What this means is ...


2

In the A* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the evaluation function, which, in the case of A*, is defined as $$f(n)=g(n)+h(n)$$ where $g(n)$ is the length (or cost) of the cheapest path from the start node to the current node $n$ and $h(n)$ is the heuristic function that estimates the cost of the ...


2

What is the difference between the heuristic function and the evaluation function in A*? The evaluation function, often denoted as $f$, is the function that you use to choose which node to expand during one iteration of A* (i.e. decide which node to take from the frontier, determine the next possible actions and which next nodes those actions lead to, and ...


1

You can easily find a counterexample. Suppose that there are three nodes $s$, $p$, and $goal$ such that $s \rightarrow p \rightarrow goal$. The real cost of going from $s$ to $p$ is $c(s,p) = 10$ and $c(p, goal) = 10$. Also, $h_1(s) = 18$, $h_1(p) = 9$, $h_1(goal) = 0$, $h_2(s) = 17$, $h_2(p) = 1$.On the other hand, $h^*(s) = 19$ and $h^*(p) = 10$. Now, $...


1

The sketch of the proof for your first question: for an open node $n$, if $f_1(n) = g(n) + h_1(n)$, in the same situation in using $h_2$, it will be $f_2(n) = g(n) + 3 h_1(n)$. Hence, all the time for any node $n$, $f_2(n) \leqslant 3f_1(n)$. On the other hand, we know that A* with the admissible husritic function $h_1$ will be admissible (from Theorem 2 of ...


1

I'm not familiar with your game so I can't tell you what a good heuristic woul be in your specific case, but I can give you some advice on how to look for a good heuristic function. As a rule of thumb, the heuristic function for a MiniMax algorithm is best kept simple and efficient, so you can get deeper into the tree. But it depends on how costly it is to ...


1

The issue is that you must include assumptions about hopping into your heuristic. In particular, if you are considering individual cars then you must assume that they might be able to hop all of the way to the goal. Thus, your heuristic for each car should be Manhattan distance divided by 2. That's guaranteed to be admissible when you take the max. If you ...


1

I will use the 8-puzzle game to show you why Nilson's sequence score heuristic function is not admissible. In the 8-puzzle game, you have a $3 \times 3$ board of (numbered) squares as follows. +---+---+---+ | 0 | 1 | 2 | +---+---+---+ | 7 | 8 | 3 | +---+---+---+ | 6 | 5 | 4 | +---+---+---+ The numbers in these squares are just used to refer to the ...


Only top voted, non community-wiki answers of a minimum length are eligible