3 added 144 characters in body
source | link

When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

enter image description here

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $d(a,b)+d(b,c) < d(a,c)$ $$d(a,b)+d(b,c) < d(a,c)$$ is true, we must visit $b$ first.

When does $A*$ ensure this?

The neccessary condition to ensure $A*$ visits We can add $b$ first, is$h(c)$ on both sides without changing anything. $$d(a,b)+h(b) < d(a,c)+h(c)$$$$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$ WithIf the monotonic constraint is fulfilled, we can replace $h(b)\le d(b,c)+h(c)$$d(b,c)+h(c)$ by $h(b)$, this becomes $$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$since it's less or equal. The equation $$d(a,b)+d(b,c) < d(a,c)$$$$d(a,b)+h(b) < d(a,c)+h(c)$$ Thisis still true. This also happens to be the test the $A*$ algorithm uses do decide whether or not it will visit $b$ before $c$. If it is true, it visits $b$ first. This is exacly what we wanted to ensure in the paragraph aboveachive.

When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

enter image description here

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $d(a,b)+d(b,c) < d(a,c)$, we must visit $b$ first.

When does $A*$ ensure this?

The neccessary condition to ensure $A*$ visits $b$ first, is $$d(a,b)+h(b) < d(a,c)+h(c)$$ With the monotonic constraint $h(b)\le d(b,c)+h(c)$, this becomes $$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$ $$d(a,b)+d(b,c) < d(a,c)$$ This is exacly what we wanted to ensure in the paragraph above.

When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

enter image description here

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $$d(a,b)+d(b,c) < d(a,c)$$ is true, we must visit $b$ first. We can add $h(c)$ on both sides without changing anything. $$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$ If the monotonic constraint is fulfilled, we can replace $d(b,c)+h(c)$ by $h(b)$, since it's less or equal. The equation $$d(a,b)+h(b) < d(a,c)+h(c)$$ is still true. This also happens to be the test the $A*$ algorithm uses do decide whether or not it will visit $b$ before $c$. If it is true, it visits $b$ first. This is exacly what we wanted to achive.

2 added 3 characters in body
source | link

When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

enter image description here

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $d(a,b)+d(b,c) < d(a,c)$, we must visit $b$ first.

When does $A*$ ensure this?

The neccessary condition to ensure $A*$ visits $b$ first, is $$d(a,b)+h(b) < d(a,c)+h(c)$$ With the monotonic constraint $h(b)<d(b,c)+h(c)$$h(b)\le d(b,c)+h(c)$, this becomes $$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$ $$d(a,b)+d(b,c) < d(a,c)$$ This is exacly what we wanted to ensure in the paragraph above.

When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

enter image description here

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $d(a,b)+d(b,c) < d(a,c)$, we must visit $b$ first.

When does $A*$ ensure this?

The neccessary condition to ensure $A*$ visits $b$ first, is $$d(a,b)+h(b) < d(a,c)+h(c)$$ With the monotonic constraint $h(b)<d(b,c)+h(c)$, this becomes $$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$ $$d(a,b)+d(b,c) < d(a,c)$$ This is exacly what we wanted to ensure in the paragraph above.

When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

enter image description here

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $d(a,b)+d(b,c) < d(a,c)$, we must visit $b$ first.

When does $A*$ ensure this?

The neccessary condition to ensure $A*$ visits $b$ first, is $$d(a,b)+h(b) < d(a,c)+h(c)$$ With the monotonic constraint $h(b)\le d(b,c)+h(c)$, this becomes $$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$ $$d(a,b)+d(b,c) < d(a,c)$$ This is exacly what we wanted to ensure in the paragraph above.

1
source | link

When is a node visited twice?

Consider the following graph, where the heuristic satisfies the condition to always underestimate the length, but is not monotonic because $h(b) > d(b,c) + h(c)$.

enter image description here

When we visit $a$, we add $b$ and $c$ to the priority queue with priorities $$p(b) = d(a,b)+h(b) = 1+8 = 9$$ $$p(c) = d(a,c)+h(c) = 3+1 = 4$$ Obviously, $c$ is visited first despite the shortest path to $c$ is actually via $b$. Later, when we visit $b$, $c$ is visited again from $b$ and has it's total weigth updated to $2$.

Strategy to find the shortest path without visiting a node twice.

If $a\rightarrow b\rightarrow c$ is shorter than $a\rightarrow c$, we want to visit $b$ first, so we reach $c$ from $b$ before reaching it from $a$. If we can ensure this, we don't even need to visit it from $a$ later on, because $a\rightarrow b\rightarrow c$ is shorter anyway.

This boils down to: If $d(a,b)+d(b,c) < d(a,c)$, we must visit $b$ first.

When does $A*$ ensure this?

The neccessary condition to ensure $A*$ visits $b$ first, is $$d(a,b)+h(b) < d(a,c)+h(c)$$ With the monotonic constraint $h(b)<d(b,c)+h(c)$, this becomes $$d(a,b)+d(b,c)+h(c) < d(a,c)+h(c)$$ $$d(a,b)+d(b,c) < d(a,c)$$ This is exacly what we wanted to ensure in the paragraph above.