1 00:00:00,000 --> 00:00:03,000 The answer is exhausting the frontier won't work, 2 00:00:03,000 --> 00:00:05,000 because the frontier might be infinite. 3 00:00:05,000 --> 00:00:08,000 In this particular problem, there's only a finite number of states, 4 00:00:08,000 --> 00:00:10,000 but in some problems there might be an infinite number. 5 00:00:10,000 --> 00:00:13,000 If we kept on generating new elements onto the frontier 6 00:00:13,000 --> 00:00:15,000 we may never get to the end. 7 00:00:15,000 --> 00:00:17,000 Doing one step won't do it either. 8 00:00:17,000 --> 00:00:21,000 In this case, if once we found the solution from this 14, 9 00:00:21,000 --> 00:00:25,000 we then gave all the other guys one step, it would work in this case. 10 00:00:25,000 --> 00:00:27,000 But it might be that it took two steps. 11 00:00:27,000 --> 00:00:33,000 Maybe from the 15 there'd be one step that costs 1 and another step that cost 2. 12 00:00:33,000 --> 00:00:36,000 I might not just be one step, so that's not going to work. 13 00:00:36,000 --> 00:00:38,000 The test later part will work. 14 00:00:38,000 --> 00:00:42,000 The reason it works is because now we've guaranteed 15 00:00:42,000 --> 00:00:44,000 that everybody on the frontier is sorted, 16 00:00:44,000 --> 00:00:46,000 and we're pulling off the shortest one first. 17 00:00:46,000 --> 00:00:52,000 If we put it back onto the frontier rather than recognizing immediately that it's a goal, 18 00:00:52,000 --> 00:00:56,000 then since we're pulling them off in order of increasing cost, 19 00:00:56,000 --> 00:01:00,000 then we know that the first one we pull off the frontier that is a goal 20 00:01:00,000 --> 99:59:59,999 that must be the cheapest path to the goal.