Unit 2, Topic 19, Search Optimality Answer

Unit 2, Topic 19, Search Optimality Answer

• Category

  Howto & Style

[Raymond Grier]

Ran out of letters above.

I applaud your efforts but recommend that these videos should be reviewed periodically and replaced by more polished ones. I also want to note that a lot of what I see in the first two lessons ( haven't gone past) should have been covered in precursor courses such as Data Structures.

[Raymond Grier]

I'm a little concerned by how optimal was defined and how execution of the depth-first was expressed. If I write a depth-first program and it comes to a goal, why wouldn't I just drop the remaining branch points? I'm not required to keep going past the goal and this is implementation dependent. You seem to consider optimal to mean that all paths ending exactly on goals must be found, usually optimal would mean finding the best goal and realizing it as the best goal in the quickest time.

[s0lidmetal]

For the breadth-first search I'm confused about the ordering. If the distance between all nodes is equal and you are using a random metric to determine the first node to pop off the frontier, can't the left or right nodes both be 2 or 3? Or is it a convention to order from left-to-right when randomness is involved?

[samruby82]

the dfs answer is ambiguous.

legitimate answers could be preorder, inorder and postorder.

[Martin Griswold]

I think that the numbering is wrong for the cheapest-first search. Both paths on the right should be explored before the path on the left. The next path to expand is chosen based on the cost of the path, not the cost of the path plus the next action.

[Charles Strahan]

And to elaborate, let's say you have 4 different routes that are all the same number of paths away from your goal. Let's also say that those 4 routes are all the closest to the goal in terms of # paths. In this case, you don't care which one you take - just take the first one. So, while you do randomly choose which path to explore (so long as it is [one of] the least furthest away), you always arrive at your goal [possibly tied] with the least number of nodes traversed. HTH.

[Charles Strahan]

It (Breadth-first) is considered optimal in terms of # of paths (connections from node to node) - but definitely not cost (sum of weights for each path - in the case of a map, that might # of miles). It's all about context - which question is it your trying to answer: "How many legs?" vs "How many miles?".