1.2 반복 깊이 우선 탐색(경로 탐색)의 적용

IDFS의 정의

깊이우선탐색이 뭔지는 다들 아실거라 생각하는데 IDFS는 고급검색인데 실생활에서는 특정 상황의 깊이를 가늠하기 어렵기 때문에 DFS에 깊이 제한을 둡니다. DFS 후 목표를 찾을 수 없으면 여기에 고정 증분이 있어야 합니다. 이러한 종류의 반복은 목표를 찾을 때까지 실행됩니다.

운동

지난번처럼 두 마리의 새가 있는데 하나는 빨간색, 하나는 노란색입니다. 빨간색은 노란색을 먹고 싶어합니다. 가장 짧은 시간에 가장 가까운 길을 찾도록 도와주세요.

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

결론

파이썬으로 해결했는데, 재귀가 있는데 이 모듈에서 가장 핵심이 되는 부분이 있는데 이를 극복하기 위해서는 변수의 범위와 재귀의 순서에 대해 설명해야 합니다. 고려의 초기 단계.

이 모듈의 효과

사진에 기록하면 정말 효과가 있는 반면 최적의 지점을 찾을 수도 있습니다.(임의의 분기 선택에 따라 다릅니다.) 게다가 목적지까지 가는 방법이 다양하기 때문에 소요 시간이 짧습니다. Breath first search보다 나을 것입니다.







7A775BC8-928D-4D53-B121-9E07AEFC19CB.png








1BE014D6-EE81-4E07-94D1-AF2ADCF1830B.png



색상의 음영은 알고리즘에 의한 방문 빈도를 의미합니다.