虽然A*搜索产生了最小耗费的解，但是搜索空间可能会过大以至于无法继续计算。增强A*搜索和处理这些巨大规模的问题的改进思想主要包括：
迭代加深
这个策略重复迭代有深度限制的深度优先搜索，每次迭代都会增加深度限制。这种方法能够选择出在下次迭代中优先被处理的节点，因此减少了不必要的搜索，增加了快速收敛到获胜走法的可能性。同时，由于搜索空间被切分成离散的部分，实时算法能够在尽可能多的空间限制下，在时限内寻找到一个较优解。最先应用到A*搜索算法的是Korf（1985），他发明了IDA*。
转移表
为了避免重复计算，程序员可以对局面状态进行散列，在一个转移表中存储路径长度。如果状态在后面的搜索中会出现，而且当前深度大于先前的深度，那么搜索将会终止。这种方法能够避免搜索一棵低效的子树。
层次化
如果局面状态能够层次化地表示，那么我们可以重新构建一下搜索空间。层次化寻路A*（HPA*）就应用了这种方法（Botea等，2004）。
内存限制
与其在计算时限制搜索空间，程序员可以执行一种“有损”搜索，在搜索的过程中舍弃一些节点，专注于搜索那些被认为和结果相关的区域。简化内存限制A*（SMA*）就是一个例子（Russel，1992）。
Reinefeld和Marsland（1994）总结了一系列的A*的有趣的扩展。更多的在AI系统中使用A*搜索的信息在教科书和大量的在线资源可以找到相关信息（Barr和Feigenbaum，1981）。