IDA* 알고리즘 - A* 변형은 끝이 없는 것 같습니다.

안녕하세요. 오늘은 A* 알고리즘의 변형 중 하나인 Iterative Deepning A*(IDA*) 알고리즘을 공부해보려고 해요!

• Stuart Russell. 1992. Efficient memory-bounded search methods. In Proceedings of the 10th European conference on Artificial intelligence (ECAI '92). John Wiley & Sons, Inc., USA, 1–5.

저번에 SMA* 알고리즘을 공부했던 논문에서 IDA* 알고리즘을 봐버려서 넘길수가 없었습니다...

 

IDA* 알고리즘을 간단하게 설명하면 탐색 깊이를 제한함으로써 메모리를 아끼는 것인데요.

자세히 알아보도록 하겠습니다.

---

1. IDA* 알고리즘 동작 방식

1. 시작 노드 s의 f ` 값을 계산합니다.
2. 노드 s의 f` 값을 LIMIT에 대입합니다.
3. 노드 s에 대해서 LIMIT값과 함께 DFS 알고리즘을 실행합니다.
4. DFS 알고리즘의 반환값에 SUCCESS가 있다면 알고리즘을 종료합니다..
5. DFS 알고리즘의 반환값이 FAILED라면 같이 반환된 f`값을 LIMIT으로 갱신합니다.
6. 3로 돌아갑니다.

DFS 알고리즘

1. 주어진 노드 n의 f` 값이 LIMIT 값보다 크다면 (FAILED, f`(n)) 을 반환합니다.
2. 만약 노드 n이 goal 노드라면 (SUCCESS, -) 을 반환합니다.
3. Connected(n)에 포함된 c들에 대해서 DFS(c, LIMIT)을 실행하고, 가장 작은 f` 값을 반환합니다.

 

동작 방식을 보면 IDA* 알고리즘이 대략적으로 어떻게 동작하는지 아시겠죠?

이제 최단 경로를 찾을 수 있도록 조금 더 구체적인 예제 코드를 준비하겠습니다.

2. 예제 코드

from dataclasses import dataclass
from typing import List


@dataclass
class Node:
    id: int
    is_visited: bool = False
    f_val: float = float("inf")
    parent_id: int = None

@dataclass
class Edge:
    start_node: Node
    end_node: Node
    weight: float

    def get_weight(self) -> float:
        return self.weight

    def get_other_node(self, node_id: int) -> Node:
        if self.start_node.id == node_id:
            return self.end_node
        else:
            return self.start_node

@dataclass
class Graph:
    nodes: dict
    adjacent_edges: dict

    def get_node(self, node_id: int) -> Node:
        return self.nodes[node_id]
    
    def get_node_f_val(self, node_id: int) -> int:
        return self.nodes[node_id].f_val
    
    def set_node_f_val(self, node_id: int, f_val: int):
        self.nodes[node_id].f_val = f_val

    def get_adjacent_edges(self, node_id: int) -> List[Edge]:
        return self.adjacent_edges.get(node_id, [])

    def trace(self, node_id):
        parent_id = self.nodes[node_id].parent_id
        if parent_id != None:
            return self.trace(parent_id)+ [node_id]
        return [node_id]


def ida(graph, start_node_id, end_node_id):
    success = False
    limit = 0
    graph.set_node_f_val(start_node_id, 0)
    while True:
        old_limit = limit
        visited = {start_node_id:0}
        (success, f_val) = dfs(graph, start_node_id, end_node_id, limit, visited)
        if success:
            return graph.trace(end_node_id)
        limit = f_val
        if limit == old_limit:
            return "Failed to find path"
        
def dfs(graph, node_id, goal_node_id, limit, visited):
    f_val = graph.get_node_f_val(node_id)
    if f_val > limit:
        return (False, f_val)
    if node_id == goal_node_id:
        return (True, f_val)
    
    result = []
    for connected_edge in graph.get_adjacent_edges(node_id):
        connected_node = connected_edge.get_other_node(node_id)
        if not connected_node.is_visited or connected_node.f_val > f_val + connected_edge.weight: 
            connected_node.is_visited = True
            connected_node.parent_id = node_id
            graph.set_node_f_val(connected_node.id, f_val + connected_edge.weight)
        r = dfs(graph, connected_node.id, goal_node_id, limit, visited)
        result.append(r)
    result = sorted(result, key=lambda x:(x[0]==False, x[1]))
    try:
        return result[0]
    except:
        return (False, float("inf"))



if __name__ == "__main__":
    if __name__ == "__main__":
    nodes = {}
    for i in range(11):
        nodes[i+1] = Node(id=i+1)

    adjacent_edges = {}
    adjacent_edges[1] = [Edge(start_node=nodes[1], end_node=nodes[2], weight=1)]
    adjacent_edges[1] += [Edge(start_node=nodes[1], end_node=nodes[3], weight=2)]
    adjacent_edges[1] += [Edge(start_node=nodes[1], end_node=nodes[4], weight=1)]
    adjacent_edges[2] = [Edge(start_node=nodes[2], end_node=nodes[6], weight=1)]
    adjacent_edges[2] += [Edge(start_node=nodes[2], end_node=nodes[11], weight=1)]
    adjacent_edges[3] = [Edge(start_node=nodes[3], end_node=nodes[5], weight=1)]
    adjacent_edges[3] += [Edge(start_node=nodes[3], end_node=nodes[6], weight=4)]
    adjacent_edges[3] += [Edge(start_node=nodes[3], end_node=nodes[8], weight=3)]
    adjacent_edges[5] = [Edge(start_node=nodes[5], end_node=nodes[7], weight=2)]
    adjacent_edges[5] += [Edge(start_node=nodes[5], end_node=nodes[8], weight=1)]
    adjacent_edges[7] = [Edge(start_node=nodes[7], end_node=nodes[9], weight=1)]
    adjacent_edges[8] = [Edge(start_node=nodes[8], end_node=nodes[10], weight=1)]
    adjacent_edges[9] = [Edge(start_node=nodes[9], end_node=nodes[10], weight=1)]
    adjacent_edges[11] = [Edge(start_node=nodes[11], end_node=nodes[8], weight=1)]

    graph = Graph(nodes=nodes, adjacent_edges=adjacent_edges)
    print(ida(graph, 1, 10))

3. 예시

예시 그래프

 

실행 결과

최단 경로를 찾아주네요!

---

IDA*알고리즘은 어떠셨나요?

저는 IDA* 알고리즘이 SMA* 알고리즘보다 훨씬 직관적이고, 구현이 쉽더라구요!

SMA* 알고리즘 예제 코드는 언제 준비할 수 있을지...

읽어야 할 논문이 너무 많습니닷...

 

요즘 일이 바빴는데 여유가 생기면 꼭 마무리 하도록 하겠습니다!

다들 바쁘시겠지만 화이팅입니다!