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
$\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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.