乐昌门户网站,中国十大设计院,北京建外贸网站公司,网站信息备案查询A*搜索(A Star)
不同于盲目搜索#xff0c;A算法是一种启发式算法(Heuristic Algorithm)。 上文提到#xff0c;盲目搜索对于所有要搜索的状态结点都是一视同仁的#xff0c;因此在每次搜索一个状态时#xff0c;盲目搜索并不会考虑这个状态到底是有利于趋向目标的#x…A*搜索(A Star)
不同于盲目搜索A算法是一种启发式算法(Heuristic Algorithm)。 上文提到盲目搜索对于所有要搜索的状态结点都是一视同仁的因此在每次搜索一个状态时盲目搜索并不会考虑这个状态到底是有利于趋向目标的还是偏离目标的。 而启发式搜索的启发二字看起来是不是感觉这个算法就变得聪明一点了呢正是这样启发式搜索对于待搜索的状态会进行不同的优劣判断这个判断的结果将会对算法搜索顺序起到一种启发作用越优秀的状态将会得到越高的搜索优先级。 我们把对于状态优劣判断的方法称为启发函数*通过给它评定一个搜索代价来量化启发值。 启发函数应针对不同的使用场景来设计那么在拼图的游戏中如何评定某个状态的优劣性呢粗略的评估方法有两种
可以想到某个状态它的方块位置放对的越多说明它能复原目标的希望就越大这个状态就越优秀优先选择它就能减少无效的搜索经过它而推演到目标的代价就会小。所以可求出某个状态所有方块的错位数量来作为评估值错位越少状态越优秀。假如让拼图上的每个方块都可以穿过邻近方块无阻碍地移动到目标位置那么每个不在正确位置上的方块它距离正确位置都会存在一个移动距离这个非直线的距离即为曼哈顿距离(Manhattan Distance)我们把每个方块距离其正确位置的曼哈顿距离相加起来所求的和可以作为搜索代价的值值越小则可认为状态越优秀。
其实上述两种评定方法都只是对当前状态距离目标状态的代价评估我们还忽略了一点就是这个状态距离搜索开始的状态是否已经非常远了亦即状态结点的深度值。 在拼图游戏中我们进行的是路径搜索假如搜索出来的一条移动路径其需要的步数非常多即使最终能够把拼图复原那也不是我们希望的路径。所以路径搜索存在一个最优解的问题搜索出来的路径所需要移动的步数越少就越优。 A*算法对某个状态结点的评估应综合考虑这个结点距离开始结点的代价与距离目标结点的代价。总估价公式可以表示为
f(n) g(n) h(n)n 表示某个结点f(n) 表示对某个结点进行评价值等于这个结点距离开始结点的已知价 g(n) 加上距离目标结点的估算价 h(n)。 为什么说 g(n) 的值是确定已知的呢在每次生成子状态结点时子状态的 g 值应在它父状态的基础上 1以此表示距离开始状态增加了一步即深度加深了。所以每一个状态的 g 值并不需要估算是实实在在确定的值。 影响算法效率的关键点在于 h(n) 的计算采用不同的方法来计算 h 值将会让算法产生巨大的差异。
当增大 h 值的权重即让 h 值远超 g 值时算法偏向于快速寻找到目标状态而忽略路径长度这样搜索出来的结果就很难保证是最优解了意味着可能会多绕一些弯路通往目标状态的步数会比较多。当减小 h 值的权重降低启发信息量算法将偏向于注重已搜深度当 h(n) 恒为 0 时A*算法其实已退化为广度优先搜索了。(这是为照应上文的方便说法。严谨的说法应是退化为 Dijkstra 算法在本游戏中广搜可等同为 Dijkstra 算法关于 Dijkstra 这里不作深入展开。)
以下是拼图状态结点 PuzzleStatus 的估价方法在实际测试中使用方块错位数量来作估价的效果不太明显所以这里只使用曼哈顿距离来作为 **h(n)** 估价已能达到不错的算法效率。
/// 估算从当前状态到目标状态的代价
- (NSInteger)estimateToTargetStatus:(idJXPathSearcherStatus)targetStatus {PuzzleStatus *target (PuzzleStatus *)targetStatus;// 计算每一个方块距离它正确位置的距离// 曼哈顿距离NSInteger manhattanDistance 0;for (NSInteger index 0; index self.pieceArray.count; index) {// 略过空格if (index self.emptyIndex) {continue;}PuzzlePiece *currentPiece self.pieceArray[index];PuzzlePiece *targetPiece target.pieceArray[index];manhattanDistance ABS([self rowOfIndex:currentPiece.ID] - [target rowOfIndex:targetPiece.ID]) ABS([self colOfIndex:currentPiece.ID] - [target colOfIndex:targetPiece.ID]);}// 增大权重return 5 * manhattanDistance;
}状态估价由状态类自己负责A算法只询问状态的估价结果并进行 f(n) g(n) h(b) 操作确保每一次搜索都是待搜空间里代价最小的状态即 f 值最小的状态。 那么问题来了在给每个状态都计算并赋予上 **f** 值后如何做到每一次只取 **f** 值最小的那个 前文已讲到所有扩展出来的新状态都会放入开放队列中的如果 A算法也像广搜那样只放在队列尾然后每次只取队首元素来搜索的话那么 f 值完全没有起到作用。 事实上因为每个状态都有 f 值的存在它们已经有了优劣高下之分队列在存取它们的时候应当按其 f 值而有选择地进行入列出列这时候需要用到优先队列(Priority Queue)它能够每次出列优先级最高的元素。 以下是 A*搜索算法的代码实现
- (NSMutableArray *)search {if (!self.startStatus || !self.targetStatus || !self.equalComparator) {return nil;}NSMutableArray *path [NSMutableArray array];[(idJXAStarSearcherStatus)[self startStatus] setGValue:0];// 关闭堆存放已搜索过的状态NSMutableDictionary *close [NSMutableDictionary dictionary];// 开放队列存放由已搜索过的状态所扩展出来的未搜索状态// 使用优先队列JXPriorityQueue *open [JXPriorityQueue queueWithComparator:^NSComparisonResult(idJXAStarSearcherStatus obj1, idJXAStarSearcherStatus obj2) {if ([obj1 fValue] [obj2 fValue]) {return NSOrderedSame;}// f值越小优先级越高return [obj1 fValue] [obj2 fValue] ? NSOrderedDescending : NSOrderedAscending;}];[open enQueue:self.startStatus];while (open.count 0) {// 出列id status [open deQueue];// 排除已经搜索过的状态NSString *statusIdentifier [status statusIdentifier];if (close[statusIdentifier]) {continue;}close[statusIdentifier] status;// 如果找到目标状态if (self.equalComparator(self.targetStatus, status)) {path [self constructPathWithStatus:status isLast:YES];break;}// 否则扩展出子状态NSMutableArray *childStatus [status childStatus];// 对各个子状进行代价估算[childStatus enumerateObjectsUsingBlock:^(idJXAStarSearcherStatus _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {// 子状态的实际代价比本状态大1[obj setGValue:[status gValue] 1];// 估算到目标状态的代价[obj setHValue:[obj estimateToTargetStatus:self.targetStatus]];// 总价已知代价未知估算代价[obj setFValue:[obj gValue] [obj hValue]];// 入列[open enQueue:obj];}];}NSLog(总共搜索: %, (close.count));return path;
}可以看到代码基本是以广搜为模块加入了 f(n) g(n) h(b) 的操作并且使用了优先队列作为开放表这样改进后算法的效率是不可同日而语。
