Посмотрите на другие алгоритмы поиска пути (например, Breath-First, Depth-First, Minimax, Negmax и т. Д.) И взвесьте позитивы и негативы для вашего сценария.
Повышение также имеет A-star реализацию . Попробуйте выполнить эти инструкции для создания надстройки на iPhone, но она может не сработать для вас: это не «полный порт» надстройки и может произойти ошибка.
Следующее от Алгоритмы в двух словах (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 );
}