有一些算法使用了双向搜索（Kaindl和Kainz，1997），而不仅仅是从初始状态向前搜索。一开始这种方法由于不能工作，被早期的AI研究人员放弃，Kaindl和Kainz提出了强有力的理由，认为这种方法应该被重新考虑。
一种广为人知的A*搜索变种叫做迭代加深A*(IDA*)，由Korf（1985）提出。它依赖于一系列逐渐扩展的有限制的深度优先搜索。对于每次后继迭代，搜索深度限制都会在前次的基础上增加。IDA*比单独的深度优先搜索或者广度优先搜索要高效得多，因为每次计算出的开销值都是基于实际的走法序列而不是启发式函数的估计。Korf（2000）描述了高效的启发式信息是如何和IDA*结合起来，用于解决十五数码问题，在整个搜索过程中，会对超过4亿个棋面状态进行评估。
Barr和Feigenbaum（1981）提出了一些改进方法，在不能高效地得到一个可接受的h*(n)函数时使用。