CODEWITHSUNDEEP
algorithmsearch
Jakob Nielsen
Jakob Nielsen

Reputation: 5198

Implement A*-Search as Breadth-First-Search / Depth-First-Search

For an assignment in "Introduction to artificial intelligence" I need to solve the following question:

Let f(n) = c1*g(n) + c2*h(n) be an evaluation function, where c1,c2 be constants.
1. Define c1,c2,h(.),g(.) such that A* with this evaluation function is bfs.
2. Define c1,c2,h(.),g(.) such that A* with this evaluation function is dfs.

For BFS I had the following idea: Let g(n) be the cost from the start node to the current node and h(n) the estimated cost from current node to goal. If I set c2 = 0 it should actually be Breadth First Search.

For DFS I thought of setting c2 = 0 and c1 = (-1)

Any ideas, tips or feedback you can give me?

Upvotes: 0

Views: 1005

Answers (1)

Honza Brabec
Honza Brabec

Reputation: 37608

I think your answers are the ones that are expected. However I think the question is a bit wrong because I don't find it possible to make BFS and DFS (in the terms I understand them).

The problem is that both DFS and BFS don't care about the path lengths. They just care about the node order.

Your BFS solution is actually a uniform-cost search (or dijkstra algorithm) which is an improvement to basic BFS.

Your DFS solution expands the farthest node, which is not how the actual DFS (with stack) works.

The answers will be right if there was somewhere stated that the arc cost is always the same.

Upvotes: 2

Related Questions