Defination of IDFS
I think all of you guys know what depth first search is, while, the IDFS is an advanced version of it. In the real life, the depth of a specific situation is hard to estimate, thus, we give a depth limitation to the DFS. If we can't find the goal after a DFS, a fixed increment should be here. This kind of iteration(迭代) will be executed until we can find the goal.
Exercise
Like the last time, there are two birds, one is red another is yellow. The red wants to eat the yellow one. let us help it find the closest way in the shortest time.
def solve( problem ) :
def detection_recursion(state, current_depth, lower_bound, list_visited_node):
successor_list = problem.get_successors(state) # generate successors
for index in range(0,len(successor_list)):
action_info = successor_list[index] # obtain a successor from successors
if action_info[0] in path_location:
continue
path_info.push(action_info) # push the successor into path stack
path_location.append(action_info[0])
current_depth += 1 # jump to next layer
if current_depth == lower_bound: # if touch the depth bound, have goal_test
if action_info[0] not in list_visited_node:
list_visited_node.append(action_info[0]) # record the visited node
if problem.goal_test(action_info[0]):
for index_2 in range(0, current_depth - 1): # if it arrived the destination
path.push(path_info.pop()[1]) # record the actions in pash
return path # get the output
else: # if it has not reached the destination
path_info.pop() # delete this action
current_depth -= 1 # go back to last layer
else:
path_info.pop() # delete this action
current_depth -= 1 # go back to last layer
else:
state = action_info[0]
detection_recursion(state, current_depth,lower_bound, list_visited_node)
if not path.is_empty(): # get the output
return
if action_info[0] not in list_visited_node:
list_visited_node.append(action_info[0]) # record the visited node
if problem.goal_test(action_info[0]):
for index_2 in range(0, current_depth): # if it arrived the destination
path.push(path_info.pop()[1]) # record the actions in pash
path.push(current_depth)
else: # if it has not reached the destination
path_info.pop() # delete this action
current_depth -= 1 # go back to last layer
else:
path_info.pop() # delete this action
current_depth -= 1 # go back to last layer
current_depth = 0
path_info = frontiers.Stack() # a stack to store the all info about path
path = frontiers.Stack() # a stack to store the path(only action) of the travelsuccessor_queue_1 = problem.get_successors(state)
state = problem.initial_state # initialize the start point
list_visited_node = [(0, 0)] # store the node visited so that they would not be tested more than once
path_location = [] # record the locations in the path_info so that that will not be visited again
list_action = [] # record the path stack in a list
lower_bound_list = [] # Initialize depth bound
for index in range(100, 1000, 3):
lower_bound_list.append(index)
for lower_bound in lower_bound_list: # increase the low_bound if it needs
detection_recursion(state, current_depth, lower_bound, list_visited_node)
if not path.is_empty(): # find the goal
break
if not path.is_empty():
lower_bound = path.pop()
print("the optimal lower_bound is ", lower_bound)
while not path.is_empty():
list_action.append(path.pop())
return list_action # return the actions
Conclusion
I used the python to solve it, by the way, there is a recursion( 递归 ), which could be the most critical part of this module. In order to get over it, the scope of variables and order of recursion are supposed to be covered in the early stage of consideration.
Effect of this module
I record it into the photo and It really works, while an optimal may be found(it depends on the random selection of optional branches). Besides, the time spent is short, as there are many ways to the destination.Therefore, the effect should be better than Breath first search.
The shade of color means the frequency of visiting by the algorithm.
