RBFS 알고리즘 - A* 알고리즘이 메모리를 너무 많이 사용할 때는 어떻게 해야 할까요?

안녕하세요. 오늘은 A* 알고리즘의 변형인 Recursive Best First Search(RBFS) 알고리즘을 공부해보려고 해요!

• A* 알고리즘 - 경로 계획 알고리즘 공부한다면 기본이죠...?

RBFS 알고리즘은 PEA* 알고리즘 공부하다가 알게 된 알고리즘입니다.

• YOSHIZUMI, Takayuki; MIURA, Teruhisa; ISHIDA, Toru. A* with Partial Expansion for Large Branching Factor Problems. In: AAAI/IAAI. 2000. p. 923-929.

요즘은 탐색 속도에만 집중하고 있었는데 A* 알고리즘의 메모리 사용량이 문제가 될수 있는 것도 챙겨가게 되네요 ㄷㄷㄷ
한번 자세히 알아볼까요?

---

1. RBFS 알고리즘과 A* 알고리즘의 차이점

A* 알고리즘은 앞으로 탐색해야 할 노드들을 큐에 저장합니다.

그리고 문제 상황에 알맞는 휴리스틱 함수를 사용하여 최선의 탐색 노드를 추출합니다.

 

이 때, 탐색해야 할 노드들이 너무 많으면 큐에 노드가 저장되면서 메모리 사용량이 치솟는 문제가 있습니다.

처음에는 "메모리 사용량 때문에 알고리즘 실행에 지장이 갈 정도의 그래프가 있나?" 궁금증이 떠올랐지만
SNS의 인간 관계, 단백질 서열 정리와 같은 문제들이 있더라고요!

이런 문제점을 해결하기 위해 RBFS 알고리즘이 고안되었습니다.

RBFS는 메모리 사용량을 크게 줄이면서도 A*의 성능을 보여줍니다.

작동 원리도 간단합니다! 바로 재귀 호출을 사용하는 것이죠!

 

2. RBFS 알고리즘 작동 방식

1. RBFS 알고리즘은 휴리스틱 함수와 f 값(경로 비용과 휴리스틱 값의 합)을 사용하여 탐색을 진행합니다.
2. 현재 노드에서 가능한 후계자 노드들의 f 값을 비교하여 가장 낮은 f 값을 가진 노드를 선택합니다.
3. 이 과정은 목표 노드에 도달할 때까지 재귀적으로 반복됩니다.

재귀적으로 반복한다는 것이 A*와의 차이점인데 글로 설명하는데 한계가 있네요 ^^;;;

예제 코드를 살펴볼까요?

3. 예제 코드

다음은 파이썬으로 작성한 RBFS 알고리즘의 예제 코드입니다.

재귀적으로 구현되었다는 것을 제외하면 A* 알고리즘과 똑같죠?

휴리스틱 함수는 h(x) = 0으로 설정했습니다!

from dataclasses import dataclass
from typing import List

@dataclass
class Node:
    id: int
    is_visited: bool = False

@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 set_node_visited(self, node_id: int):
        self.nodes[node_id].is_visited = True

    def get_connected_nodes(self, node_id: int) -> List[Node]:
        adjacent_edges = self.adjacent_edges.get(node_id, [])
        return [(edge.get_other_node(node_id), edge.get_weight()) for edge in adjacent_edges]

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

    def set_edge_weight(self, edge_id: int, weight: float):
        self.edges[edge_id].set_weight(weight)

def rbfs(graph, current_node_id, goal_node_id, f_limit):
    if current_node_id == goal_node_id:
        return [current_node_id], 0

    successors = []
    for child, cost in graph.get_connected_nodes(current_node_id):
        successors.append((child.id, cost))

    while len(successors) > 0:
        successors.sort(key=lambda x: x[1])
        best, best_f = successors.pop(0)
        if best_f > f_limit:
            return None, best_f
        alternative_f = successors[1][1] if len(successors) > 1 else float('inf')
        result, best_f = rbfs(graph, best, goal_node_id, min(f_limit, alternative_f))
        if result is not None:
            result.insert(0, current_node_id)
            return result, best_f
    return None, f_limit


if __name__ == "__main__":
    nodes = {}
    for i in range(10):
        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=10)]
    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=5)]
    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)]

    graph = Graph(nodes=nodes, adjacent_edges=adjacent_edges)
    print(rbfs(graph, 1, 10, float("inf")))

 

4. 예시

실행 결과

최단 경로: 1, 3, 8, 10!

---

이번에 공부한 RBFS 알고리즘은 어떠셨나요?
저는 경로 계획 알고리즘의 실행 시간에만 집중하고 있었는데 "메모리도 고려해야지" 라는 인식을 얻게 되어서 좋았습니다!

아쉬운 것은 예시로 준비한 그래프가 작아서 RBFS 알고리즘을 사용해서 얻는 이점을 실감하기에는 많이 부족했던 것 같습니다 ㅜ

아쉬움은 아쉬움대로 남겨두고 남은 알고리즘들을 정리하기 위해서 더 부지런히 공부하겠습니다 :)