Самая быстрая кросс-платформенная реализация A *?

Ответ 1

Посмотрите на другие алгоритмы поиска пути (например, Breath-First, Depth-First, Minimax, Negmax и т.д.) и взвесьте положительные и отрицательные значения для вашего сценария.

Boost также имеет реализацию A-star. Попробуйте выполнить эти инструкции, чтобы повысить уровень поддержки iPhone, но это может не сработать для вас: это не "полный порт" повышения, и он может произойти ошибка.

Ниже приведено Алгоритмы в двух словах (Java, а не С++, но, возможно, вы хотите его портировать):

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 );
}

Ответ 2

Я предлагаю вам реализовать алгоритм самостоятельно. Следуйте псевдокоду: A * Search Algorithm, и он должен быть прямым. "Openset" должен быть реализован как мини-куча, что также тривиально; или вы можете использовать priority_queue из STL.

Ответ 3

Когда у вас есть определенные ограничения, с которыми вы можете работать, вам обычно лучше писать алгоритм самостоятельно. В частности, ваше пространство с небольшим состоянием позволяет оптимизировать работу, направленную на то, чтобы сократить время работы процессора, а тот факт, что вы используете сетку, а не произвольное пространство состояний, позволяет вам делать такие вещи, как оптимизация вашего преемника node поколения, или иметь возможность обрабатывать все частичные пути, которые заканчиваются на том же квадрате сетки, что и эквивалент (который обычный поиск A * не будет и не может принять).

(PS. OpenSteer, набор рулевых поведений, не имеет ничего общего с A *, который является алгоритмом поиска, за исключением того, что вы можете использовать один, другой или оба для перемещения пробела. замена другого в самых разумных обстоятельствах.)

Ответ 4

У меня есть два общих совета:

• Если ваш домен ограничен сеткой, возможно, вы найдете лучшие результаты, выполнив поиск "pathfinding", а не более общий A *.
• Если ваш домен не является строго поисковым путем вдоль поверхности, вы можете получить больше преимуществ для своих усилий, если потратите свое время на улучшение своей эвристики, а не на оптимизацию самого алгоритма.

Ответ 5

Существует общая реализация С++ A * в http://www.ceng.metu.edu.tr/~cuneyt/codes.html. Похоже, что это кросс-платформенный стандарт С++.