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