
The answer is exhausting the frontier won't work,

because the frontier might be infinite.

In this particular problem, there's only a finite number of states,

but in some problems there might be an infinite number.

If we kept on generating new elements onto the frontier

we may never get to the end.

Doing one step won't do it either.

In this case, if once we found the solution from this 14,

we then gave all the other guys one step, it would work in this case.

But it might be that it took two steps.

Maybe from the 15 there'd be one step that costs 1 and another step that cost 2.

I might not just be one step, so that's not going to work.

The test later part will work.

The reason it works is because now we've guaranteed

that everybody on the frontier is sorted,

and we're pulling off the shortest one first.

If we put it back onto the frontier rather than recognizing immediately that it's a goal,

then since we're pulling them off in order of increasing cost,

then we know that the first one we pull off the frontier that is a goal

that must be the cheapest path to the goal.