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

[shivajikobardan]

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.

Uniform Cost Search Algorithm

Uniform cost search algorithms make it possible to explore unknown problem spaces. Learn how to solve complex problems using these techniques.

www.analyticsvidhya.com

Uninformed Search Algorithms - Javatpoint

Uninformed Search Algorithms with AI, Artificial Intelligence, Tutorial, Introduction, History of Artificial Intelligence, AI Overview, Application of AI, Types of AI, What is AI, etc.

www.javatpoint.com

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)

 

[blamocur]

You cannot check for the standard failure if the graph is deeper than your search. If you want the same function to check for both types of failure you can modify your code so that it keeps track of the depth continues the search even when the depth is exceeded. The program would exit when either "shallow" match is found or the whole graph has been traversed.

 

[shivajikobardan]

You cannot check for the standard failure if the graph is deeper than your search. If you want the same function to check for both types of failure you can modify your code so that it keeps track of the depth continues the search even when the depth is exceeded. The program would exit when either "shallow" match is found or the whole graph has been traversed.

thanks got it.