Implementation of A star algorithm

Posted by chunyang on April 9, 2014

a* 算法在人工智能领域应用比较广泛。这几天在USTC ACM上刷problem 1012,题中需要解决8-puzzle问题,有两种解法,一种是BFS,另外一种就是a*算法。之前在Java上实现过,但是当时是利用Princeton的一个类:MinPQ,最小的优先级队列。

在C++中,其实也有priority_queue。这个是一个接口封装,底层可以使用vector或者deque实现。priority_queue


priority_queue<T, Sequence, Compare>

其中T表示储存值的类型,Sequence表示底层的实现方式,Compare表示比较函数。这里需要注意的是,默认priority_queue是最大堆。

网上很多声音说这个优先级队列无法满足需求,因为无法满足动态修改优先级队列中的元素。不知道为什么priority_queue不提供迭代器,导致无法访问其内部元素。在a*算法中在某些场景中需要更新队列中的元素。

其实STL的算法中提供了三个函数,push_heap,pop_heap,make_heap。利用这三个函数,外加一个仿函数即可实现一个最小优先级队列。


struct Compare {
	bool operatro()(const Type &lhs, const Type &rhs)
	{
		//....
	}
};

make_heap(sequence.begin(), sequence.end(), Compare());

sequence.push_back(value);
push_heap(sequence.begin(), sequence.end(), Compare());

pop_heap(sequence.begin(), sequence.end(), Compare());
sequence.pop_back();

具体代码在:a* C++ implementation

本文完


Creative Commons License
This work is licensed under a CC A-S 4.0 International License.