How to check if search problem has no solution in depth limit search?

[shivajikobardan]

Summary:: standard failure in depth limit search.

Depth-limited search can be terminated with two Conditions of failure:

Standard Failure: it indicates that the problem does not have any solutions.

Cutoff Failure Value: It defines no solution for the problem within a given depth limit.

https://www.analyticsvidhya.com/blog/2021/02/uninformed-search-algorithms-in-ai/

https://www.javatpoint.com/ai-uninformed-search-algorithms

I checked for cut off failure. But I don't know how to check for standard failure. Can you guide me a bit?

# Python dictionary to act as an adjacency list
graph = {
  '7' : ['19','21', '14'],
  '19': ['1', '12', '31'],
  '21': [],
  '14': ['23', '6'],
  '1' : [],
  '12': [],
  '31': [],
  '23': [],
  '6' : []
}

goal='6'
visited = [] # List of visited nodes of graph.
def dls(visited, graph, node,depth):
    if(depth>=0):
        if node not in visited:
            visited.append(node)
       
        if(node==goal):
            print("goal found")
            print("path to goal=",visited)
            exit()

        for neighbor in graph[node]:
            dls(visited, graph, neighbor,depth-1)       

        print(node)

# Driver Code
print("Following is the Depth-First Search")
res=dls(visited, graph, '7',1)
if(res):
    print("Path to goal node available")
    print("Path",path)
else:
    print("No path available for the goal node in given depth limit ie cut off failure")

print("visited=",visited)

 

[Mark44]

I checked for cut off failure. But I don't know how to check for standard failure. Can you guide me a bit?

Standard failure -- the item you're searching for isn't in the data structure. See what happens if you search for '15'.
Cutoff failure -- the item you're searching for is in the data structure, but you have specified a goal that is deeper in the structure than you are allowing. For example, if you search only to the 2nd level you won't find any of the nodes at the 3rd level.

 

[pbuk]

Remember I said before that that algorithm performs a traversal not a search? It doesn't search for anything, it simply prints what is there.

If it did perform a search then a 'standard failure' simply means it looked through the whole tree and didn't find the item you are searching for.

Note that I have used the word tree rather than graph: you can't really apply the terms depth-first or breadth-first to a graph that is not connected or is cyclic because there is no ordering.