[Official] Assignment 2

Master / Vertiefung Künstliche Intelligenz
21

So whats the case now with 2.3?

Does greedy search here refer to finding the shortest path out of all?
Or just use using the shortest as a decision rule when deciding the next node to visit? This would not necessarily lead to the shortest all over solution.

1 „Gefällt mir“
22

There was some confusion about the details of A2.3, but that was by design. It serves two purposes:

  • It makes you think more deeply about the contents of the course - What detailed design choices are there that the slides gloss over? What are the pros and cons of each choice? etc.
  • Together with A2.2, it shows the contrast of how practical programming situations are described. (Sadly A2.3 is often a more realistic approximation of how programming happens in practice than A2.2 is.)

Regarding the questions:

The edge(from,to,distance) formulation indeed implies directed edges. The course notes imply undirected edges. Both make sense, and noticing these issues is part of the learning experience.
Grading will accept anything that is a reasonable interpretation of the problem.

Greedy algorithms are generally prone to failing by running off in the wrong direction.
The notes do not say clearly if greedy search performs loop checking. (Loops can be a problem both with directed and with undirected edges.)
Typically, a search algorithm will keep the set of expanded nodes to ensure not to expand the same node twice; that prevents loops.

Greedy algorithms generally are not guaranteed to find the optimal solution (here: the overall shortest path).
In fact, many search algorithms (e.g., DFS, BFS) will not necessarily find the optimal solution first. A* is an exception.

23

I have posted the solutions in the usual place.