For questions related to the graph search. As opposed to a tree search, a graph search uses a list or set, called the closed list (or explored set), which contains the already visited and expanded nodes (or states) of the search space (which is usually represented as a graph, both in the case of tree and graph searches), so that not to revisit these already visited nodes.
Questions tagged [graph-search]
5 questions
19
votes
1 answer
What is the difference between tree search and graph search?
I have read various answers to this question at different places, but I am still missing something.
What I have understood is that a graph search holds a closed list, with all expanded nodes, so they don't get explored again. However, if you apply…
xava
- 423
- 1
- 3
- 9
2
votes
0 answers
Why do we use the tree-search version of breadth-first search or A*?
In Artificial Intelligence A Modern Approach, search algorithms are divided into tree-search version and graph-search version, where the graph-search version keeps an extra explored set to avoid expanding nodes repeatedly.
However, in breadth-first…
Gu Liqi
- 21
- 1
2
votes
1 answer
In the graph search version of A*, can I stop the search the first time I encounter the goal node?
I am going through Russel and Norvig's Artificial Intelligence: A Modern Approach (3rd edition). I was reading the part regarding the A* algorithm
A* graph search version is optimal when heuristic is consistent and tree search version optimal when…
Fenil
- 181
- 5
1
vote
1 answer
GREED - preservation theoretical properties in the GED(graph edit distance) pridiction
In this paper "GREED: A Neural Framework for Learning Graph Distance Functions", function F is defined to satisfy metric property and triangle inequality property.
I wonder how can I prove that these properties are maintained in actual forecasts? Or…
GH HONG
- 13
- 2
1
vote
0 answers
What is a example showing that the tree-based variant for the greedy best-first search is incomplete?
I understand that a tree-based variant will have nodes repeatedly added to the frontier. How do I craft an example where a particular goal node is never found. Is this example valid.
On the other hand, how do I explain that the graph-based version…
goldilocks
- 53
- 1
- 4