对于A*算法、alpha-beta算法的思考

jasongreen

A* 算法以估值函数为核心。
alpha-beta 以剪枝为核心。简单的说就是把比已知的一步棋更臭的棋剪掉。

现在我希望寻求某个问题接下来几步的最优解，蛮力计算是不可行的。A* 的准确性较差。但这本身不是一个博弈情况，所以alpha-beta不适用，只能期望于一种比较好的搜索算法。

正在构思一种逆A*算法。A*算法以价值为中心，逆A* 算法以代价(cost)为中心。
A* 算法采用宽度搜索获取最优解。逆A* 算法采用深度搜索。

部分代码冗余，在任何步骤都不足以满足目标价值时
一个lua的实现
local currentcost;local wantedvalue;local maxvalue,mincost,maxrate =0,0,0local statusmap;--状态图，棋盘local callcount;routes={};if table.getn == nil thenlocal fun, err = loadstring("return function(tb) return #tb end")table.getn = fun()end --depth 最大限制深度--value 目标价值-- cost 花费--return: min cost,max value--TODO: jstar(map,depth) return routes,状态空间对应的路由是确定的 function jstar(depth,needvalue,costed)     if(depth<=0)then--计算maxvalue，未实现，重要return 0endcallcount=callcount+1;local actions = getActions(map);for i=1,table.getn(actions) doa = actionsv = needvalue - getValue(a);c = getCost(a)+costed;if(v <=0 )thenif( c < mincost)thenmincost=c;exec(map,a)routes={}--clonefor j=1,table.getn(map.routing) doroutes[j]=map.routing[j]endroutes.cost=croutes.value=vundo(map)endelseif(c<mincost)thenexec(map,a)jstar(depth-1,v,c)undo(map)--else 则超出最优解范围，忽略endendendlocal testzb={{2,3,1},{4,5,1},{3,5,1},{4,7,1},{2,9,1},{300,100,1},{8,9,2},{10,10,1}}map={}map.current={5,5}map.routing={}--获取所有可能的点function getActions(m)ac={}for i=1,table.getn(testzb) dof=truefor j=1,table.getn(m.routing) doif(map.routing[j]==i)then f=false;break;endendif(f)thentable.insert(ac,i)endendreturn acend   function exec(m,action)m.old=map.current;m.current=testzb[action]table.insert(m.routing,action)endfunction undo(m)if(table.getn(m.routing)==1)then m.current={5,5} elsem.current=testzb[m.routing[table.getn(m.routing)-1]]endtable.remove(m.routing,table.getn(m.routing))endfunction getValue(a)return testzb[a][3]endfunction getCost(a)dx = map.current[1]-testzb[a][1]dy = map.current[2]-testzb[a][2]return math.sqrt(dx*dx+dy*dy)end--执行jstar算法，初始参数深度function  start(depth,w)  wantedvalue=w;  maxvalue=0;  mincost=1000000000;  callcount=0;  jstar(depth,wantedvalue,0);  print(callcount);endstart(5,5)print(callcount)print(table.concat(routes,','))