어떤 그래프에서 무엇을 최소화하는지 정한다
그래프 탐색은 시작 node에서 목표 node까지 간선을 이어 가는 순서를 찾는다. 방향 간선은 한쪽 이동만 허용하며 A→B가 있다고 B→A가 자동으로 생기는 것은 아니다. 이 단위는 유한한 방향 그래프와 고정된 비음수 간선 비용을 사용한다. 경로 비용은 지나간 간선 비용의 합이다. 비용을 거리로 정했는지 시간이나 교육용 점수로 정했는지에 따라 '좋은 경로'의 뜻이 바뀐다.
작은 합성 그래프의 node는 S,A,B,G 네 개이며 S가 시작, G가 목표다. 모든 간선과 비용은 S→A:2, S→B:1, B→A:0.5, A→G:2, B→G:5다. 이외의 간선은 없다. 값은 같은 단위의 교육용 비용점수이며 실제 미터나 초가 아니다. 세 가능한 경로 S-A-G, S-B-A-G, S-B-G의 합은 각각 4, 3.5, 6이다. 간선이 적은 경로와 비용이 작은 경로는 같지 않을 수 있다.
간선을 후보로 만들기 전에 M17.01처럼 충돌과 연결 구간이 유효하다고 확인해야 한다. 탐색기는 잘못 승인한 간선을 단지 비용이 낮다는 이유로 선택할 수 있다. 이후 새 장애물로 간선이 무효가 되면 과거 최적 경로가 그대로 유효하다는 보장도 없다. 그래프·비용·지도 버전과 시작 상태를 결과에 함께 기록한다.
Dijkstra는 알려진 누적 비용이 가장 작은 후보부터 본다
g(v)는 시작 S에서 node v까지 지금까지 발견한 가장 작은 누적 비용이다. 처음 g(S)=0이고 다른 node는 아직 경로를 몰라 ∞로 둔다. ∞는 실제 무한 거리를 측정했다는 뜻이 아니라 미발견 표시다. parent는 그 비용을 만든 직전 node이며 최종 경로를 되짚을 때 사용한다.
그림 M17.02-1. 각 칸은 서로 다른 역할/근거다. 아래 방향은 자료/처리의 연결이며 실제 성공을 자동으로 보장하지 않는다. 직접 제작한 개념도이며 본문의 조건과 함께 읽는다.
node u에서 나가는 간선 u→v의 비용 c(u,v)를 조사할 때 새 후보는 g(u)+c(u,v)다. 이 값이 기존 g(v)보다 작으면 g(v)와 parent를 바꾼다. 이를 완화(relaxation)라고 한다. 후보를 보관하는 우선순위 대기열은 비용이 가장 작은 항목을 먼저 꺼내며 값이 줄면 순서도 갱신해야 한다. 단지 한 번 발견했다는 이유로 값을 고정하지 않는다.
합성 예에서 S를 꺼내면 g(A)=2, parent(A)=S와 g(B)=1, parent(B)=S가 된다. 다음은 B다. B를 통해 A로 가면 1+0.5=1.5로 기존 2보다 작으므로 A를 갱신한다. G도 1+5=6으로 처음 발견한다. 하지만 G를 찾았다고 중단하면 비용 6인 경로를 골라 버린다.
대기열에서 A의 1.5가 G의 6보다 작으므로 A를 먼저 꺼낸다. A→G를 조사하면 1.5+2=3.5로 G가 갱신되고 parent(G)=A다. 마지막으로 G를 최소 비용으로 꺼낼 때 종료한다. parent를 G→A→B→S로 되짚고 반대로 읽으면 S-B-A-G, 비용 3.5다. 오래된 대기열 항목을 남기는 구현이라면 갱신 전의 값으로 확장하지 않도록 검사해야 한다.
LaValle 저자 교재의 Dijkstra 설명은 비음수 비용과 비용 순서의 역할을 설명한다. 비음수 조건에서는 최소 g로 꺼낸 node보다 더 싼 우회 경로가 나중에 등장하지 않는다는 성질을 이용한다. 음수 간선이 있는 문제에 그대로 적용하지 않는다. 이 유한 예에서는 비용 0인 간선도 허용할 수 있지만 중복 상태와 갱신 규칙을 처리해야 한다.
A*는 남은 비용의 낙관적인 추정을 더한다
A*는 현재까지의 g에 목표까지 남은 비용 추정 h를 더해 후보 순서를 정한다. h는 heuristic이며 목표를 향해 어떤 후보를 먼저 조사할지 안내하는 함수다. f는 그 합이고 세 값은 같은 비용 단위를 가져야 한다.
합성 그래프에서 h(S)=3, h(A)=2, h(B)=2.5, h(G)=0을 주자. S를 확장한 뒤 A는 g=2, f=4이고 B는 g=1, f=3.5다. B를 먼저 확장하면 A의 g가 1.5로 줄어 f=3.5가 되고 G는 g=6, f=6이다. A를 거쳐 G는 g=f=3.5로 갱신된다. G를 꺼낼 때 얻는 경로와 비용은 Dijkstra와 같다. 이 작은 그래프에서는 확장 순서도 같으며 A*가 모든 입력에서 더 빠르다고 주장하지 않는다.
허용적(admissible) heuristic은 실제 최소 남은 비용을 과대평가하지 않는다. 이 그래프의 실제 남은 최소 비용은 S에서 3.5, A에서 2, B에서 2.5, G에서 0이다. 주어진 h는 모두 그 이하다. 원래 문제의 제약을 일부 없애 얻은 더 쉬운 문제의 비용이 하한이 되는 경우가 있다. 그러나 거리 비용이 아닌 점수에 미터 단위 직선거리를 그냥 더하면 그런 근거가 없다.
일관성(consistency)은 각 방향 간선에서 h(u)≤c(u,v)+h(v)가 성립하는 조건이다. h(G)=0도 둔다. 예를 들어 B→A에서는 2.5≤0.5+2로 같고 S→B에서는 3≤1+2.5다. 다른 세 간선도 조건을 만족한다. 이 조건에서는 앞에서 확장한 node를 영구 닫는 표준 그래프 탐색으로 최적성을 유지할 수 있다. 허용적이지만 비일관적인 h라면 더 싼 경로를 뒤늦게 발견한 node를 다시 여는 처리가 필요할 수 있다. '방문했으니 무조건 무시'는 모든 A* 구현에 적용하는 규칙이 아니다.
Modern Robotics 저자 Graph Search는 목표를 처음 발견한 때와 최소 우선순위로 꺼내는 때를 구분한다. Berkeley CS188 공식 교재는 더 작은 비용으로 재방문하는 경우를 처리해야 하는 그래프 탐색의 경계를 설명한다. 구현과 heuristic 조건을 함께 확인해야 최적이라는 말을 사용할 수 있다.
과대 heuristic과 비용 변경을 구별한다
같은 그래프에서 h(B)=10, 나머지 h=0으로 바꾸면 B의 f는 11, A의 f는 2다. A를 거쳐 G 비용 4를 얻고 G를 f=4로 먼저 꺼내 종료한다. 실제 최소는 3.5지만 B 방향을 과도하게 비싸다고 추정해 놓친 것이다. h(B)=10은 실제 남은 비용 2.5보다 크므로 허용 조건을 위반한다. h를 크게 하면 항상 더 좋은 탐색이라는 생각은 틀리다. h=0이면 A*의 순서는 Dijkstra와 같아진다.
반대로 B→A 비용 자체를 0.5에서 3으로 바꾸는 것은 heuristic 오류가 아니라 문제의 변경이다. 새 세 경로 비용은 4, 6, 6이므로 최소는 S-A-G의 4다. 위험 구간의 비용을 올렸다는 해석을 붙일 수 있지만 점수를 실제 충돌 확률로 부르면 안 된다. 위험을 더했는지 간선을 금지했는지도 구분한다. 금지 조건을 큰 유한 비용 하나로 대신하면 대안이 없을 때 그 간선을 선택할 수 있다.
최적성은 주어진 유효 그래프와 고정 비용, 알고리즘 조건 안에서의 성질이다. 실제 로봇의 속도·가속도, 위치 추정과 지도 변경, 통신 지연을 이 합성 비용이 포함하지 않는다. 기존 3.5 안전한 텔레오퍼레이션 루프의 실행 계층 점검과 6.6 평가 설계의 조건별 평가를 연결해 계획과 실행 근거를 분리하자. 활동의 계산 통과는 실제 최단 주행이나 안전 승인이 아니다.