ZeroCho Blog

 오랜만에 알고리즘 포스팅을 남기는 것 같습니다. 요즘 날마다 더 멍청해지는 것 같아서 뇌를 깨우기 위해 공부를 다시 시작했습니다.

그래서 기존 알고리즘 포스팅 중에 포스팅 하지 않았던 개념들을 자바스크립트로 다시 구현해볼까 합니다.

A*(에이스타) 알고리즘부터 시작하도록 하겠습니다. A* 알고리즘은 최단경로를 찾는 알고리즘 중 하나인데요. 다익스트라에 비해서 효율적인 경우가 많아서(100%는 아니지만 효율적인 경우가 많습니다) 실무에서 더 자주 쓰이는 알고리즘 중 하나입니다.

다익스트라와 매우 유사하지만 출발점과의 거리만 고려하는 다익스트라 알고리즘과는 다르게 A* 알고리즘은 목표점(또는 도착점)과의 예상 거리(예상 거리라는 게 중요합니다)를 고려합니다.

따라서 다익스트라 예제와는 다르게, 좌표 평면이 있어 목표점의 좌표가 있는 문제들이 A* 알고리즘을 적용하는 데 더 적합합니다. 목표점의 좌표가 없다 하더라도 각 점과 목표점 사이의 예상 거리를 제공하면 그것을 활용해 A* 알고리즘을 적용할 수 있습니다.

위와 같은 좌표를 준비해보았습니다. 저희는 A에서 F까지의 최단 거리를 구하고 싶습니다. 기존 그래프 코드로는 좌표 평면 위에 있는 그래프를 표현하지 못하므로 새롭게 그래프를 작성해보겠습니다. 기존 Vertex에 좌표평면에 따른 x, y가 추가되었고, Arc에서는 capacity를 제거했습니다. Arc의 data는 두 점 사이의 거리가 됩니다. 나머지 코드는 Graph 강좌와 다익스트라 알고리즘 강좌를 보시면 됩니다.

function EuclideanDistance(from, to) {
  return Math.sqrt((from.x - to.x) ** 2 + (from.y - to.y) ** 2);
}
function ManhattanDistance(from, to) {
  return Math.abs(from.x - to.x) + Math.abs(from.y - to.y);
}

나중에 쓰일 유클리드 거리와 맨해튼 거리 코드를 미리 작성했습니다.

var Graph = (function() {
  function Vertex(key, x, y) {
    this.next = null;
    this.arc = null;
    this.key = key;
    this.x = x;
    this.y = y;
    this.inTree = null;
  }
  function Arc(data, dest) {
    this.nextArc = null;
    this.destination = dest;
    this.data = data;
    this.inTree = null;
  }
  function Graph() {
    this.count = 0;
    this.first = null;
  }
  Graph.prototype.insertVertex = function(key, x, y) {
    var vertex = new Vertex(key, x, y);
    var last = this.first;
    if (last) {
      while (last.next !== null) {
        last = last.next;
      }
      last.next = vertex;
    } else {
      this.first = vertex;
    }
    this.count++;
  };
  Graph.prototype.deleteVertex = function(key) {
    var vertex = this.first;
    var prev = null;
    while (vertex.key !== key) {
      prev = vertex;
      vertex = vertex.next;
    }
    if (!vertex) return false;
    if (!vertex.arc) return false;
    if (prev) {
      prev.next = vertex.next;
    } else {
      this.first = vertex.next;
    }
    this.count--;
  };
  Graph.prototype.insertArc = function(fromKey, toKey) {
    var from = this.first;
    var to = this.first;
    while (from && from.key !== fromKey) {
      from = from.next;
    }
    while (to && to.key !== toKey) {
      to = to.next;
    }
    if (!from || !to) return false;
    var arc = new Arc(EuclideanDistance(from, to), to);
    var fromLast = from.arc;
    if (fromLast) {
      while (fromLast.nextArc != null) {
        fromLast = fromLast.nextArc;
      }
      fromLast.nextArc = arc;
    } else {
      from.arc = arc;
    }
  };
  Graph.prototype.deleteArc = function(fromKey, toKey) {
    var from = this.first;
    while (from !== null) {
      if (from.key === fromKey) break;
      from = from.next;
    }
    if (!from) return false;
    var fromArc = from.arc;
    var preArc;
    while (fromArc !== null) {
      if (toKey === fromArc.destination.key) break;
      preArc = fromArc;
      fromArc = fromArc.next;
    }
    if (!fromArc) return false;
    if (preArc) {
      preArc.nextArc = fromArc.nextArc;
    } else {
      from.arc = fromArc.nextArc;
    }
  };
  return Graph;
})();
function insertTwoWayArc(graph, from, to) {
  graph.insertArc(from, to);
  graph.insertArc(to, from);
}

var graph = new Graph();
graph.insertVertex('A', 0, 0);
graph.insertVertex('B', 3, 3);
graph.insertVertex('C', 3, 0);
graph.insertVertex('D', 8, 7);
graph.insertVertex('E', 8, 4);
graph.insertVertex('F', 11, 8);
insertTwoWayArc(graph, 'A', 'B');
insertTwoWayArc(graph, 'A', 'C');
insertTwoWayArc(graph, 'B', 'C');
insertTwoWayArc(graph, 'B', 'D');
insertTwoWayArc(graph, 'C', 'D');
insertTwoWayArc(graph, 'C', 'E');
insertTwoWayArc(graph, 'D', 'E');
insertTwoWayArc(graph, 'D', 'F');
insertTwoWayArc(graph, 'E', 'F');

여기서 최단 거리를 구하는 shortest를 A* 알고리즘 방식대로 구현해보겠습니다. 다익스트라와 다른 점이 목표점까지와의 예상 거리가 있다는 것입니다. 예상 거리를 준다면 그것을 그대로 사용하면 되고, 주지 않는다면 예상 거리를 구해야 합니다. A* 알고리즘은 예상 거리가 짧은 쪽을 먼저 탐색합니다.

지금 상황은 목표점의 좌표만 알고 있으므로 저희가 직접 각각의 점들과의 예상 거리를 구해야겠습니다.

예상 거리를 구하는 방법으로는 대표적으로 맨하탄 거리와 유클리드 거리를 쓸 수 있습니다. 맨하탄 거리는 단순히 좌표들의 차이의 절댓값을 더해서 구하면 되고, 유클리드 거리는 실제 직선 거리를 구하면 됩니다. 예를 들어 A(0, 0)와 B(3, 3)의 유클리드 거리는 피타고라스의 정리를 이용해서 루트(3^2 + 3^2)이므로 대략 4.2가 나옵니다. 반대로 맨하탄 거리는 공식이 |Bx-Ax| + |By-Ay|이므로 |3-0|+|3-0|해서 6이 됩니다. 맨하탄 거리를 쓰냐 유클리드 거리를 쓰냐에 따라서 A* 알고리즘이 다르게 작동할 수 있습니다. 예상 거리가 정확하지 않으면 알고리즘이 판단을 엉뚱하게 내릴 수 있거든요. 저희는 두 거리재기 방식을 모두 사용해보겠습니다.

참고로 A* 알고리즘은 우선순위 큐를 사용하므로 저희는 힙 자료구조를 사용합니다. 힙 자료구조는 우선 순위 큐처럼 사용할 수 있습니다. 다만, 저희가 예전 강좌에서 구현했던 힙 자료구조는 단순히 숫자값들만 정렬해주므로, 객체 내부의 값을 정렬할 수 있도록 다시 구현해야 합니다. reheapUp과 reheapDown만 다시 구현하면 됩니다.

var Heap = (function() {
  function Heap() {
    this.arr = [];
  }
  function reheapUp(self, idx) {
    if (idx) {
      var parent = parseInt((idx - 1) / 2);
      if (self.arr[idx].distance > self.arr[parent].distance) {
        var temp = self.arr[idx];
        self.arr[idx] = self.arr[parent];
        self.arr[parent] = temp;
        reheapUp(self, parent);
      }
    }
  }
  function reheapDown(self, idx) {
    var left = 0;
    var right = 0;
    var large;
    if (idx * 2 + 1 < self.arr.length) { 
      left = self.arr[idx * 2 + 1];
      if (idx * 2 + 2 < self.arr.length - 1) {
        right = self.arr[idx * 2 + 2];
      }
      if (left > right) {
        large = idx * 2 + 1;
      } else {
        large = idx * 2 + 2;
      }
      if (!self.arr[large]) return;
      if (self.arr[idx].distance < self.arr[large].distance) {
        var temp = self.arr[idx];
        self.arr[idx] = self.arr[large];
        self.arr[large] = temp;
        reheapDown(self, large);
      }
    }
  }
  Heap.prototype.insert = function(vertex) {
    var last = this.arr.length;
    this.arr[last] = vertex;
    reheapUp(this, last);
    return true;
  };
  Heap.prototype.delete = function() {
    if (this.arr.length <= 1) {
      return this.arr.pop();
    }
    var del = this.arr[0];
    this.arr[0] = this.arr.pop();
    reheapDown(this, 0);
    return del;
  };
  Heap.prototype.sort = function() {
    var sort = [];
    var count = this.arr.length;
    for (var i = 0; i < count; i++) {
      sort.push(this.delete());
    }
    return sort;
  };
  return Heap;
})();

var heap = new Heap();
Graph.prototype.shortest = function(startKey, endKey) {
  var from = this.first;
  var to = this.first;
  while (from && from.key !== startKey) {
    from = from.next;
  }
  while (to && to.key !== endKey) {
    to = to.next;
  }
  console.log('시작점은 %s, 목표점은 %s입니다', from.key, to.key);
  var temp = this.first;
  var current;
  var arc;
  temp.g = 0;
  temp.distance = (temp.g + EuclideanDistance(temp, to)) * -1;
  temp.inTree = true;
  heap.insert(temp);
  while (heap.arr.length) { // 반복문을 돌며 최단 거리를 찾음
    current = heap.delete();
    current.inTree = false;
    console.log('%s를 거쳐갑니다', current.key);
    if (current === to) break;
    arc = current.arc;
    while (arc) {
      arc.destination.g = current.g + arc.data;
      arc.destination.distance = (arc.destination.g + EuclideanDistance(arc.destination, to)) * -1;
      arc.destination.inTree = true;
      heap.insert(arc.destination);
      arc = arc.nextArc;
    }
  }
  console.log('%s까지의 최단 거리는 %f입니다', current.key, current.distance * -1);
};

graph.shortest('A', 'F');

최단거리는 A->B->D->F로 13.8이 나옵니다. 맨하탄 거리를 사용해도 결과는 같습니다. shortest 내부의 EuclideanDistance를 ManHattanDistance로 바꿔서 실행하면 됩니다.

shortest 부분을 다익스트라의 shortest로 대체해보면, A* 알고리즘에서는 모든 버텍스(노드)의 최단 거리를 탐색하지 않았다는 것을 알 수 있습니다. console 메시지를 비교해보시면 됩니다. 즉, A* 알고리즘이 더 효율적이라는 의미이겠죠? 하지만 모든 케이스에서 그렇지는 않으니 반례도 찾아보세요. 

실제 내비게이션에서는 A* 알고리즘보다 더 진화한 D*(다이나믹 에이스타) 알고리즘을 사용한다고 하네요. 실제 환경에서는 기존에 알고 있는 최단 거리 데이터를 캐싱해두는 장치가 있으면 좋을 것 같고 실시간으로 바뀌는 장애물 위치와 도로 상황에 따른 가중치를 조절할 수 있는 시스템도 필요할 것 같습니다.