CODEWITHSUNDEEP
searchartificial-intelligence
Zaratruta
Zaratruta

Reputation: 2285

AI search problem solving with infinite state spaces: when do algorithms halt?

In classical artificial intelligence, there is an area of ​​problem solving by search. And there are several search algorithms, such as: Breadth-first search (BFS), Depth-first search (DFS), Iterative-deepening search (IDS), Uniform cost search (UCS), etc.

We consider that Depth-first search (DFS) is not complete, in infinite state spaces, even if the solution exists and can be found with a finite number of node expansions. That's the reason for introducing depth-first search (DFS) as a solution to this problem.

But, in this case, I was thinking the following, assuming that the graph starting from the initial node is infinite. And the objective node cannot be accessed from the initial state (we have a disconnected graph). In this case, the algorithm will not return failure, because it will always be able to expand the frontier. But soon after thinking about this issue, I realized that this problem occurs with all these search algorithms I mentioned. Because the classic criterion for returning failure is when the border is empty, and the solution has not yet been found, according to this book:

Is my reasoning correct?

Upvotes: 0

Views: 115

Answers (1)

Swati
Swati

Reputation: 124

Yes, your reasoning is correct to me.

For an infinite disconnected graph, the basic searching algorithms like BFS, DFS and so no will never terminate as the nodes will keep on expanding leading to never meeting failure condition.

In order to make these algorithms trigger the failure condition, you need to add another condition that detects the cycling of search or if the depth or cost is above the specified one.

This modification may help the infinite graphs to halt.

Upvotes: 0

Related Questions