A*搜索算法改进
目录
前言
一、A*加搜索算法
二、A*随机搜索算法
代码如下：
结果分析：
最优解：
次优解：
三、A*去重随机搜索算法
A*去重搜索算法代码如下：
结果分析：
A*去重随机搜索算法代码如下：
结果分析：
最优解：
次优解：
展望
前言
在上文《A*搜索算法之8数码问题》后面提到了想找到一个完美可采纳的启发函数是很难得事情，如果能够在不可采纳的区间进行跳出，那么A*算法性能和适用面将会得到优化。
本文针对上面的几个问题提出几种改进方案。
特别声明：
本文出现的改进方案为作者自主独立原创，如果引用的话还请声明出处。
建议阅读本文之前先阅读 《A*搜索算法之8数码问题》
一、A*加搜索算法
我们知道启发函数是从当前节点n到目标节点的预估代价，对于一个复杂问题，需要进行深度抽象才有可能找到启发函数，为了降低获取启发函数的难度，我提出了多权重启发函数（Multi-weight heuristic function）。暂且先命名为A*加搜索算法
评估函数改为
可以根据问题找到多种启发函数，是权重值，位于[0, 1]。可以简单抽象出几种启发函数，再估计出各启发函数对目标的指引代价设计为权重值。从而得到全面的评估函数。
这种优化需要结合具体问题去设计，目前没有好的实例验证，暂时停在理论上。
二、A*随机搜索算法
A*随机搜索算法（A* Random Search Algorithm）是在基础的A*搜索算法代码上加入了随机状态选择功能，A*搜索算法会根据评估函数选取评估值最小的一批状态，A*随机搜索算法会在该基础上从剩余状态中随机选取一个状态共同组成子代，在该子代生成的下一代中继续按上面这种选取方案。重复允许，直至找到解。
括号里的数代表估计值，流程图如下：
代码如下：
% 设置初始状态和目标状态 initial_state = [2 0 8; 1 6 3; 7 5 4]; % 一个可解的初始状态 goal_state = [1 2 3; 8 0 4; 7 6 5]; % 目标状态 % 将3x3矩阵转换为1x9向量便于处理 initial_vec = initial_state(:)'; goal_vec = goal_state(:)'; % 检查问题是否可解 if ~is_solvable(initial_vec, goal_vec) error('该八数码问题无解'); end % 使用结构体栈记录搜索信息 stack = struct('state', {initial_vec},'parent', {initial_vec},... 'p_pointer',{0},'move', {0}, 'f', {7}, 'depth', {0}); stack_top = 1; depth = 0; % 初始深度 % 记录路径的变量 found = false; goal_index = 0; enable = 1; % 检查初始状态和目标状态是否相同 if isequal(initial_vec, goal_vec) found = true; goal_index = stack_top; enable = 0; end % A*搜索算法主循环 while enable % 对下一层所有的后代统计到son_stack中 stack_top = length(stack); son_stack = nowtier_son(stack, goal_vec, stack_top); % 对son_stack的状态按照估价值排序 for i = 1:length(son_stack) for j = i+1:length(son_stack) if son_stack(j).f < son_stack(i).f copy_stack = son_stack(j); son_stack(j) = son_stack(i); son_stack(i) = copy_stack; end end end % 将son_stack中估价值最小的状态存入stack中 depth = depth + 1; stack_top2 = length(stack); for i = 1:length(son_stack) if son_stack(i).f == son_stack(1).f stack_top2 = stack_top2+1; stack(stack_top2).state = son_stack(i).successors; stack(stack_top2).parent = son_stack(i).parent; stack(stack_top2).p_pointer = son_stack(i).p_pointer; stack(stack_top2).move = son_stack(i).moves; stack(stack_top2).f = son_stack(i).f; stack(stack_top2).depth = depth; % 检查是否达到目标状态 if isequal(stack(stack_top2).state, goal_vec) found = true; goal_index = stack_top2; break; end else r = randi([i, length(son_stack)]); stack_top2 = stack_top2+1; stack(stack_top2).state = son_stack(r).successors; stack(stack_top2).parent = son_stack(r).parent; stack(stack_top2).p_pointer = son_stack(r).p_pointer; stack(stack_top2).move = son_stack(r).moves; stack(stack_top2).f = son_stack(r).f; stack(stack_top2).depth = depth; % 检查是否达到目标状态 if isequal(stack(stack_top2).state, goal_vec) found = true; goal_index = stack_top2; break; end break; end end if found == true break; end end % 显示结果 if found solution_path = uncoil_path(stack, goal_index); step = solution_path(end); disp('初始状态'); disp(reshape(step.state, 3, 3)); for i = 1:length(solution_path)-1 step = solution_path(end-i); disp(['第', num2str(i), '步,',step.move]); disp(reshape(step.state, 3, 3)); end disp(['总步数: ', num2str(length(solution_path)-1)]); else disp(['在最大深度 ', num2str(max_depth), ' 内未找到解']); end disp(['当前遍历了 ', num2str(goal_index), ' 种状态']); %********************************************************* %功能：对当前层估计值最小的状态生成后代 %调用格式：function son_stack = nowtier_son(stack, goal_vec, stack_top) %输入参数：stack:状态的结构体，goal_vec：目标状态，stack_top：当前层的最大下标 %输出参数：son_stack: 后代的结构体 %********************************************************* function son_stack = nowtier_son(stack, goal_vec, stack_top) i = stack_top; son_stack = struct('successors', {},'parent', {},'p_pointer',{},'moves',{},'f', {}); while stack(i).depth == stack(stack_top).depth son_stacki = get_successors(stack, i , goal_vec); son_stack_num = length(son_stack); for j = 1:length(son_stacki) son_stack(son_stack_num+j) = son_stacki(j); end i = i - 1; if i < 1 break; end end end %********************************************************* %功能：获取所以子代的状态和子代的估价函数值 %调用格式：successors_stack = get_successors(current, stacki, goal) %输入参数：current:stack结构体, stacki:结构体的下标，goal:目标状态 %输出参数：successors_stack:子代的结构体 %********************************************************* function successors_stack = get_successors(current, stacki, goal) board = reshape(current(stacki).state, 3, 3); % 转换为3x3矩阵 P_board = reshape(current(stacki).parent, 3, 3); % 转换为3x3矩阵 successors_stack = struct('successors', {0},'parent', {0},'p_pointer',{0},'moves',{0},'f', {0}); [zero_row, zero_col] = find(board == 0); % 找到空格位置 % 可能的移动方向: 上, 下, 左, 右 % 注意：顺序会影响搜索行为，这里使用上、下、左、右 directions = [-1, 0; 1, 0; 0, -1; 0, 1]; direction_names = {'上', '下', '左', '右'}; j = 1; for i = 1:size(directions, 1)%查询行数 n