A* 알고리즘

최단 경로 탐색 알고리즘

 최단 경로를 탐색하는 알고리즘의 종류는 여러가지가 존재합니다. 그 종류 중 하나인 a* 알고리즘에 대해 알아보겠습니다. a* 알고리즘은 bfs 알고리즘의 한 예로, 휴리스틱(h) 값을 이용해 최단 경로를 추정해나가는 방식입니다. 아래의 설명을 보시면 아시겠지만 휴리스틱 값이 0이라고 생각하면 결국 최단 경로가 되는데요. 휴리스틱 값이 0 이라면 bfs 와 똑같은 알고리즘이 됩니다. 따라서, 이 알고리즘은 결국 bfs 알고리즘이 최단 경로를 발견한다는 것을 다시 입증해주는 예시입니다. 개념과 예시는 아래에서 설명하도록 하겠습니다.

A* 알고리즘?

 한 지점에서 목표 지점으로 가는 방법 중 가장 짧은 길을 찾는 것을 최단 경로 탐색이라 하며, 지점을 노드라고 표현합니다. a* 알고리즘에서 최적의 경로는 초기 노드에서 목표 노드로 가는 경로 중 가장 최단 경로를 말합니다. 이 때, 최단 경로를 찾아내는 과정에서 휴리스틱(h) 이라는 개념을 사용합니다. 휴리스틱은 현재 노드에서 목표 노드까지 가는 최단 경로의 비용을 추정하는 것입니다. 그 값은 추정값이기 때문에 실제로 이동해보면 그 값처럼 되지 않을수도 있습니다. 

 a* 알고리즘은 아래의 평가함수를 통해 최적의 경로를 탐색합니다.

  평가함수 f(N) 은 g(N) 과 h(N) 의 합입니다. 

• g(N) : 초기 노드에서 현재 노드까지의 실제 최단거리(비용)
• h(N) : 아직 탐색하지 않았기 때문에 알 수는 없지만, 현재 노드에서 목표 노드로 가는 최단거리(비용) 추정치
• f(N)  : g(N) 과 h(N) 을 합한 최단거리(비용)

아직 이해가 잘 되지 않아도 괜찮습니다. 이제부터 살펴볼 예시에서 자세히 알아보도록 하겠습니다.

8-puzzle 문제

 옛날에 해보신 분들도 있으실 겁니다. 8-puzzle 문제는 목표의 퍼즐에 맞게 숫자를 세팅하기 위해 한칸씩 이동시키는 게임입니다. 우선 목표 퍼즐은 아래와 같습니다.

 왼쪽에 있는 초기 상태 퍼즐을 오른쪽에 있는 목표 상태 퍼즐의 숫자들의 자리배치와 똑같이 만들어야하는 게임입니다. 이 게임에 a* 알고리즘을 적용해볼까요?

 초기 상태에서 퍼즐을 움직일 수 있는 경우의 수는 위에 보시는 것처럼 3가지 방법이 있습니다. 가운데 그림을 예로 설명하겠습니다. 가운데 그림은 숫자 8 을 움직인 모습입니다. 1칸 움직였기 때문에 g(1) = 1이고, 목표 상태에 있는 자리 배치와 같지 않는 숫자의 개수는 총 3개 (1, 2, 8) 이므로 h(1) = 3 입니다. 앞으로 자리를 수정해야 될 숫자의 개수를 h(N) 으로 생각하시면 됩니다. 따라서 f(1) = g(1) + h(1) = 4 가 되는 것입니다. 이런식으로 3가지의 경우를 모두 계산해보면 가운데의 경우가 평가함수의 값이 가장 작습니다. a* 알고리즘은 평가함수의 값이 가장 작은 곳을 따라 탐색하기 때문에 가운데의 퍼즐에서 다시 진행합니다.

 가장 작은 평가함수 결과값을 가진 퍼즐에서 다시 탐색을 해보면 2가지의 경우로 퍼즐을 움직일 수 있습니다. 숫자 1과 2를 움직일 수 있지만 2는 움직였기 때문에 그 과정을 생략합니다 (아래의 코드를 보시면 아시겠지만 closedList 에 존재하는 노드는 검사하지 않습니다). 따라서 1을 움직이는 경우만 계산해보면 됩니다. 그리고 자식의 g(N) 은 부모의 g(N) 의 값과 합쳐야 한다는 거 기억해주세요! 그러면 숫자 1 을 움직였고, 부모 노드의 g 값이 1이므로 g(2) 는 2가 됩니다. 목표 상태의 자리배치에 없는 숫자들을 세어 휴리스틱 값을 계산하면 평가함수의 값이 나오겠죠? 그 값은 3이 됩니다. 이런 식으로 한 단계 더 진행해보면 목표 상태에 도달할 수 있게 됩니다. 참고로 평가함수의 결과값이 같은 퍼즐이 2개 이상 존재한다면, 이 때는 그 자식 퍼즐들을 모두 계산해본 후 그 중에서 가장 작은 평가함수 결과값을 가진 퍼즐에서 탐색을 더 진행해야 합니다. 

 위의 퍼즐게임에서의 최단 경로는 2 -> 1 -> 8 이 됩니다. 이제 a* 알고리즘에 대해 조금은 이해가 되시나요? 게임으로 이해해보는 것을 마무리하고 코드로 설명드리겠습니다.

코드로 적용해보기

 위의 8-puzzle 예시를 보고 오셨다면 더 이해하기 편하실거예요. a* 알고리즘을 구현하는데에 필요한 2개의 리스트가 있습니다. 바로 openList 와 closedList 입니다. 평가함수 값을 검사해야 할 노드 (앞으로 방문해야 할 노드) 들은 openList에 넣습니다. 그리고 반복문을 돌며 openList 에서 노드들을 하나씩 꺼내어 그 노드가 목표 노드가 아니라면 해당 노드를 openList에서 closedList 로 옮긴 후 그 노드의 이웃 노드들을 탐색합니다. 이웃 노드가 closedList 에 존재하지 않는다면, 평가함수 값을 계산해 이전 평가함수 값보다 작으면 각 값들을 업데이트한 후 openList 에 이웃노드를 넣어줍니다. 예제 코드는 아래에 첨부하겠습니다.

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.PriorityQueue;
	public class AStar {
	private PriorityQueue<Node> openList;
	private ArrayList<Node> closedList;
	HashMap<Node, Integer> gMaps;
	HashMap<Node, Integer> fMaps;
	private int initialCapacity = 100;
	private int distanceBetweenNodes = 1;
	public AStar() {
	gMaps = new HashMap<Node, Integer>();
	fMaps = new HashMap<Node, Integer>();
	openList = new PriorityQueue<Node>(initialCapacity, new fCompare());
	closedList = new ArrayList<Node>();
	}
	public static void main(String[] args) {
	Node[] n = new Node[10];
	for (int i = 0; i < n.length; i++) {
	n[i] = new Node();
	n[i].setData("n-" + i);
	}
	/*
	* X = Walls
	* N1 => Start
	* N8 => Goal
	*
	N0 - N3 - N5 - N8
	| |
	N1 X N6 X
	| |
	N2 - N4 - N7 - N9
	*/
	n[0].setXY(0, 0);
	n[1].setXY(0, 1);
	n[2].setXY(0, 2);
	n[3].setXY(1, 0);
	n[4].setXY(1, 2);
	n[5].setXY(2, 0);
	n[6].setXY(2, 1);
	n[7].setXY(2, 2);
	n[8].setXY(3, 0);
	n[9].setXY(3, 2);
	n[0].addNeighbors(n[1], n[3]);
	n[1].addNeighbors(n[0], n[2]);
	n[2].addNeighbors(n[1], n[4]);
	n[3].addNeighbors(n[0], n[5]);
	n[4].addNeighbors(n[2], n[7]);
	n[5].addNeighbors(n[3], n[8]);
	n[6].addNeighbors(n[7], n[5]);
	n[7].addNeighbors(n[4], n[9], n[6]);
	n[8].addNeighbors(n[5]);
	n[9].addNeighbor(n[7]);
	new AStar().search(n[1], n[8]);
	}
	public void search(Node start, Node end) {
	openList.clear();
	closedList.clear();
	gMaps.put(start, 0);
	openList.add(start);
	while (!openList.isEmpty()) {
	Node current = openList.element();
	if (current.equals(end)) {
	System.out.println("Goal Reached");
	printPath(current);
	return;
	}
	closedList.add(openList.poll());
	ArrayList<Node> neighbors = current.getNeighbors();
	for (Node neighbor : neighbors) {
	int gScore = gMaps.get(current) + distanceBetweenNodes;
	int fScore = gScore + h(neighbor, current);
	if (closedList.contains(neighbor)) {
	if (gMaps.get(neighbor) == null) {
	gMaps.put(neighbor, gScore);
	}
	if (fMaps.get(neighbor) == null) {
	fMaps.put(neighbor, fScore);
	}
	if (fScore >= fMaps.get(neighbor)) {
	continue;
	}
	}
	if (!openList.contains(neighbor) || fScore < fMaps.get(neighbor)) {
	neighbor.setParent(current);
	gMaps.put(neighbor, gScore);
	fMaps.put(neighbor, fScore);
	if (!openList.contains(neighbor)) {
	openList.add(neighbor);
	}
	}
	}
	}
	System.out.println("FAIL");
	}
	private int h(Node node, Node goal) {
	int x = node.getX() - goal.getX();
	int y = node.getY() - goal.getY();
	return x * x + y * y;
	}
	private void printPath(Node node) {
	System.out.println(node.getData());
	while (node.getParent() != null) {
	node = node.getParent();
	System.out.println(node.getData());
	}
	}
	class fCompare implements Comparator<Node> {
	public int compare(Node o1, Node o2) {
	if (fMaps.get(o1) < fMaps.get(o2)) {
	return -1;
	} else if (fMaps.get(o1) > fMaps.get(o2)) {
	return 1;
	} else {
	return 1;
	}
	}
	}
	}
	class Node {
	private Node parent;
	private ArrayList<Node> neighbors;
	private int x;
	private int y;
	private Object data;
	public Node() {
	neighbors = new ArrayList<Node>();
	data = new Object();
	}
	public Node(int x, int y) {
	this();
	this.x = x;
	this.y = y;
	}
	public Node(Node parent) {
	this();
	this.parent = parent;
	}
	public Node(Node parent, int x, int y) {
	this();
	this.parent = parent;
	this.x = x;
	this.y = y;
	}
	public ArrayList<Node> getNeighbors() {
	return neighbors;
	}
	public void setNeighbors(ArrayList<Node> neighbors) {
	this.neighbors = neighbors;
	}
	public void addNeighbor(Node node) {
	this.neighbors.add(node);
	}
	public void addNeighbors(Node... node) {
	this.neighbors.addAll(Arrays.asList(node));
	}
	public Node getParent() {
	return parent;
	}
	public void setParent(Node parent) {
	this.parent = parent;
	}
	public int getX() {
	return x;
	}
	public void setX(int x) {
	this.x = x;
	}
	public int getY() {
	return y;
	}
	public void setY(int y) {
	this.y = y;
	}
	public void setXY(int x, int y) {
	this.x = x;
	this.y = y;
	}
	public Object getData() {
	return data;
	}
	public void setData(Object data) {
	this.data = data;
	}
	public boolean equals(Node n) {
	return this.x == n.x && this.y == n.y;
	}
	}

view raw a_star_algorithm.java hosted with ❤ by GitHub

참고

1. http://www.gisdeveloper.co.kr/?p=3897

2. http://itmining.tistory.com/66

3. https://ko.wikipedia.org/wiki/A*_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98