看看其他的路徑尋找算法(如呼吸優先,深度優先,Minimax,Negmax等),並衡量您的情況的積極和消極。
Boost也has an A-star implementation。嘗試遵循these instructions以在iPhone上提升效果,但它可能無法適用於您:它不是提升的「完整端口」,可能會出錯。
以下是Algorithms in a Nutshell(Java中,不C++,但也許你想將它移植):
public Solution search(INode initial, INode goal) {
// Start from the initial state
INodeSet open = StateStorageFactory.create(StateStorageFactory.TREE);
INode copy = initial.copy();
scoringFunction.score(copy);
open.insert(copy);
// Use Hashtable to store states we have already visited.
INodeSet closed = StateStorageFactory.create(StateStorageFactory. HASH);
while(!open.isEmpty()) {
// Remove node with smallest evaluation function and mark closed.
INode n = open.remove();
closed.insert(n);
// Return if goal state reached.
if(n.equals(goal)) { return new Solution(initial, n); }
// Compute successor moves and update OPEN/CLOSED lists.
DepthTransition trans = (DepthTransition)n.storedData();
int depth = 1;
if(trans ! = null) { depth = trans.depth + 1; }
DoubleLinkedList<IMove> moves = n.validMoves();
for(Iterator<IMove> it = moves.iterator(); it.hasNext();) {
IMove move = it.next();
// Make move and score the new board state.
INode successor = n.copy();
move.execute(successor);
// Record previous move for solution trace and compute
// evaluation function to see if we have improved upon
// a state already closed
successor.storedData(new DepthTransition(move, n, depth));
scoringFunction.score(successor);
// If already visited, see if we are revisiting with lower
// cost. If not, just continue; otherwise, pull out of closed
// and process
INode past = closed.contains(successor);
if(past ! = null) {
if(successor.score() >= past.score()) {
continue;
}
// we revisit with our lower cost.
closed.remove(past);
}
// place into open.
open.insert(successor);
}
}
// No solution.
return new Solution(initial, goal, false);
}
來源
2010-01-21 17:25:04
slf
如果您使用僅標頭庫,則不需要構建Boost。如果您不使用Dot文件,則Boost.Graph僅爲標題。我在iPhone上使用了幾個Boost頭文件庫,它們可以很好地工作。 – 2011-10-24 18:33:33