3 added 144 characters in body

## 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)$$.

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)$$.

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)$$.

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

## 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)$$.

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)$$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)$$.

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), 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)$$.

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

## 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)$$.

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), 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.