1
$\begingroup$

I'm working on a problem where we are given a graph and asked to perform various search algorithms (BFS, DFS, UCS, A*, etc.) and the goal state is to visit all nodes in the graph. After all nodes are visited, we need to print out the "solution path." However, I am a bit confused on what "path" means in AI.

For simplicity, let's just consider a graph of 3 nodes: A, B and C with 2 undirected edges (A, B) (A, C). If we perform BFS on this graph starting at node A and traversing alphabetically, we'd visit A, then B, then C. So, in this case, is the solution path A -> B -> C, i.e. the order in which the nodes are visited? Or is the solution path A -> B -> A -> C? Basically saying that we go from A to B, but to go from B to C, we must go through A again.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

Defining Path

You are right to be confused if your professors did not clarify (see warning at end). The term "path" can mean a few things:

"Concrete" Path: Recall, a graph is a collection of vertices and edges. A path on the graph is then:

$$v_1\xrightarrow{e_1} v_2\xrightarrow{e_2} \cdots \xrightarrow{e_{n-1}} v_n$$

Where $v_i$ are vertices on the graph and the arrows denote the direction traversed over the undirected edges $e_j$. Observe, this definition explicitly defines some "chain" of vertices connected by specific edges.

"Abstract" Path: Say there is some task that involves a serious of repeated actions but does not depend on specific objects. We can define this as a chain of composed functions:

$$f_n\circ\cdots \circ f_1$$

The idea, is that this definition is little more abstract. Though, there are many other ways one could define "path."

"Solution Path"

A Subtlety

So, in this case, is the solution path A -> B -> C, i.e. the order in which the nodes are visited? Or is the solution path A -> B -> A -> C? Basically saying that we go from A to B, but to go from B to C, we must go through A again.

BFS does not "go through A again." Considering you are using a queue based implementation, once A has been visited there will be no need to "visit" it again. That is, we have added all nodes we need to the queue and marked A as being seen. This leads into:

How to report the solution path of a search algorithm on a graph?

Since, these algorithms do not revisit nodes, what is most likely being asked of you is for you to report the order of the visits - this is what my professors wanted in my AI & Algorithms courses.

A Warning: I can only answer what my professors wanted. Please clarify this with your instructors.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .