A* 알고리즘을 위한 우선순위 큐 구현

 

알고리즘 그래프 이론을 들어가면, 가장 끝판왕은 역시나 A* 알고리즘이라고 생각합니다.

A* 알고리즘은 게임 프로그래밍에서도 많이 쓰이는 기법이니, 알아두는 것이 좋지 않을까 하네요.

 

A* 알고리즘을 적용할 때, 방문해야할 노드 수가 많을 때, 속도에 영향을 미치는 부분은 두가지가 있습니다.

 

첫번째는 가장 작은 에너지 함수값을 갖는 노드를 찾는 것입니다.

두번째는 방문한 셋에 포함되어 있는지 찾는 것입니다.

 

제 경우에는 작은 에너지 함수값을 갖는 노드를 찾는 것은 힙을 이용한 우선순위 큐를 사용합니다.  힙을 이용하게 되면, 삽입과 삭제의 경우  $O(\log n)$의 점근적 시간이 필요합니다.  선형으로 찾는 것보다 훨씬 빠르게 삽입 삭제를 할 수 있습니다.

 

방문한 셋에 포함되어있는지 검사하는 방법은 해시 테이블을 사용하고 있습니다.  해시 테이블 크기를 적당하게 늘려준다면 상수시간안에 검사가 완료됩니다.

 

우선순위 큐를 헤더 파일만 가지고 구현을 했습니다.  뭐 별도로 함수 부분을 빼도 될 수 있도록 하였습니다.  템플릿 클래스로 설계를 할까 하다가, Node만 상속받아서 사용하면 되도록 설계를 했습니다.

 

프로그램 설명은 코멘트를 참조하시면 됩니다.

 

 

//-------------------------------------------------------------------
//	File:		PQueue.h
//	Author:		Edan Choi
//	Date:		2014.11.24.
//	Contact:	http://sdev.tistory.com
//	Comment:	This class module is made for graph algorithm.
//	Update:
//
//-------------------------------------------------------------------

#pragma once
#ifndef _PQUEUE_H_
#define	_PQUEUE_H_
#include <memory.h>

///	@brief	Priority queue class.
///	@note	Class T must be derived from TPQueue::Node.
class PQueue
{
public:
	///	@brief	Priority queue node.
	class Node
	{
	friend PQueue;
	public:
		///	@brief	Constructor.
		Node() : index(-1) { }

		///	@brief	Compare priority value.
		virtual bool Compare(const Node *node) = 0;

	private:
		int index;								//<	heap index
	};

public:
	///	@brief	Constructor.
	PQueue() : maxCount(1024), curCount(0)
	{
		heap = new Node *[maxCount];
	}

	///	@brief	Destructor.
	~PQueue()
	{
		Empty();

		if( heap ) delete[] heap;
	}

	///	@brief	Add a value into heap.
	///	@param	node							[IN] node to be added
	void Add(Node *node)
	{
		int current;

		if( node->index == -1 )
		{
			current = curCount++;
			if( curCount > maxCount ) Increase();
		}
		else
		{
			current = node->index;
		}
	
		while( current > 0 )
		{
			int parent = (current-1)/2;
			if( !node->Compare(heap[parent]) ) break;
			heap[current] = heap[parent];
			heap[current]->index = current;
			current = parent;
		}

		heap[current] = node;
		node->index = current;
	}

	///	@brief	Get top node.
	Node *GetTop()
	{
		//	If heap is empty, return NULL.
		if( curCount == 0 ) return (Node *)0;

		Node *top = heap[0];
		Node *last = heap[--curCount];
		int s = 0, l = 1, r = 2, t = l;

		while( l < curCount )
		{
			if( r < curCount && heap[r]->Compare(heap[l]) ) t = r;
			if( last->Compare(heap[t]) ) break;
			heap[s] = heap[t];
			heap[s]->index = s;
			l = 2*t + 1, r = 2*t + 2, s = t, t = l;
		}
		heap[s] = last;
		last->index = s;

		return top;
	}

	///	@brief	Get element by index.
	Node *Get(int i)
	{
		if( i >= curCount ) return (Node *)0;
		return heap[i];
	}

	///	@brief	Check if this queue is empty.
	bool IsEmpty() const
	{
		return curCount == 0;
	}

	///	@brief	Empty queue.
	void Empty()
	{
		//for( int i = 0 ; i < curCount ; i++ )
		//{
		//	if( heap[i] ) delete heap[i];
		//}
		curCount = 0;
	}

	///	@brief	Increase queue size.
	void Increase()
	{
		maxCount <<= 1;
		Node **lastHeap = heap;
		heap = new Node *[maxCount];
		memcpy(heap, lastHeap, curCount*sizeof(Node *));
		delete[] lastHeap;
	}

private:
	Node **heap;								//<	heap data
	int maxCount;								//<	maximum count
	int curCount;								//<	current count
};

#endif