logo标签列表

跨平台最快的A*算法实现？

c++iphonealgorithma-star
14

有这么多可用的实现，使用小网格的C++ A*算法中，跨平台（Linux、Mac、Windows、iPhone）中最快执行（最小CPU占用，最小二进制文件）的实现是什么？

实现

Google返回：

还有其他的吗？

结论

所问问题涉及重用（插入游戏），而非重新实现（至少在性能没有问题之前不是）。这可能导致Dijkstra算法或通用路径搜索算法更加合适，或者最快的实现并不够快。我感谢替代算法的建议，但问题不是“我应该自己实现A*算法吗？”

5个回答
6

看看其他寻路算法（如BFS、DFS、Minimax、Negmax等），权衡它们在你的情况下的优缺点。

Boost也有一个A星实现。尝试按照这些说明在iPhone上构建boost，但可能不适用于您：这不是boost的“完整移植”，可能会出错。

以下内容来自《算法简介》（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 );
}
1
如果您使用仅包含头文件的库，则无需构建Boost。如果您不使用Dot文件，则Boost.Graph是仅包含头文件的库。我在iPhone上使用了几个仅包含头文件的Boost库，它们可以直接使用且运行良好。 - Emile Cormier
6
当你有特定的边界可以使用时，通常最好自己编写算法。特别是当你的状态空间很小时，它适合于预先花费内存以减少CPU时间的优化。而且，你使用网格而不是任意状态空间，这使得你可以做一些事情，比如优化后继节点生成，或者能够将所有以同一网格方格结尾的部分路径视为等效的（正常的A*搜索不能假设这一点）。
（附注：OpenSteer是一组转向行为，与搜索算法A*没有任何关系，除了你可以概念上使用其中一个、另一个或两者来遍历空间。在大多数合理的情况下，一个并不能取代另一个。）
6

我有两点通用建议：

  • 如果您的领域受到网格限制，也许在搜索时使用“路径查找”而不是更通用的A*算法会得到更好的结果。
  • 如果您的领域不仅仅是沿着表面搜索路径，那么如果您花时间改进启发式算法而不是尝试优化算法本身，您将获得更多收益。
1
我投票支持第二个观点。我认为第一个观点有些令人困惑，因为我认为“路径规划”可以比“A*”更通用。 - San Jacinto
1
A*可以用于任何类型的搜索问题，路径规划是一个明确定义的领域：从一个点导航到另一个表面上的点。 - fortran
1
第二点加1。启发式非常关键，可以优化A*算法。 - lalitm
5

我建议你自己实现这个算法。按照A*搜索算法的伪代码进行操作，应该很简单。"openset"可以使用最小堆来实现，这也很容易；或者你可以使用STL中的priority_queue。

同意。A*算法本身并不是很复杂，通常可以针对特定情况进行优化。 - David Thornley
1
你不能使用STL中的priority_queue，因为它不允许更改已插入元素的优先级（并且强制进行堆重建非常低效）。对于像我这样的凡人来说，实现一个高效的A*算法并不容易，因为它不能在列表中浪费大量时间，并保持合理的内存消耗（例如通过避免在关闭列表中存储完整节点）。 - kuroi neko
1
@kuroineko 实际上你可以使用 priority_queue，因为当你改变优先级时并不需要删除旧节点。你只需要在开放集合中再次插入具有更高优先级的节点，它会被首先选择并放入封闭集合（然后在封闭集合中的“旧”节点将稍后被丢弃，因为它已经在封闭集合中了）。 - cyril
2
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接