本文共 1065 字，大约阅读时间需要 3 分钟。

consistent heuristic  启发的一致性

admissible heuristic 可接受启发

 

 

UCS orders by backward cost——g(n)

Greedy orders by forward cost——h(n)  （h(n)就是heuristic）

A*就是结合g(n)和h(n)

A* orders by backward cost(gn) + forward cost(hn)

g(n)可以看做从start到current所花费的cost，h(n)从current到end的花费。

 

 

 

from heapq import heappush, heappopdef aStarTsa(stateSpaceGraph, h, startState, goalState):    frontier = []    heappush(frontier, (h[startState], startState))    print('Initial frontier:',list(frontier));    while frontier:        node = heappop(frontier)        if (node[1].endswith(goalState)):             return node        print('Exploring:',node[1][-1],'at cost',node[0])        for child in stateSpaceGraph[node[1][-1]]:            heappush(frontier, (node[0]+child[0]-h[node[1][-1]]+h[child[1]], node[1]+child[1]))        print(list(frontier));aStarMotivation = {'S':[(1,'a')],'a':[(1,'b'),(3,'d'),(8,'e')],'b':[(1,'c')],'c':[],'d':[(2,'G')],'e':[(1,'d')]}aStarMotivationH = {'S':6,'a':5,'b':6,'c':7,'d':2,'e':1,'G':0}print('Solution path:',aStarTsa(aStarMotivation, aStarMotivationH, 'S', 'G'))

 

转载地址：http://aoygf.baihongyu.com/