Questions tagged [graph-search]

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.

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2 votes
0 answers
301 views

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 ...
  • 21
1 vote
0 answers
194 views

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 ...
0 votes
0 answers
39 views

Why can we prune superset of a reached belief-state performing a graph search for conformant/sensorless problems?

With classic search algorithms (BFS, DFS, UCS, A* with consistent heuristic,...) redundant paths are avoided by performing a graph search instead of a tree-like search, with the guarantee that if a ...