CS 188 (4) Uniform Cost Search( 统一代价搜索算法)

    本文要实现 Uniform Cost Search( 统一代价搜索算法) ,首先搜索总成本最小的节点,  统一代价搜索算法搜索到达目标。

    PriorityQueue实现一个优先级队列的数据结构，每个插入元素具有与之关联的优先级，client快速检索队列中优先级最低的元素，以 O(1) 时间复杂度访问最低优先级的元素。   

class PriorityQueue:
    """
      Implements a priority queue data structure. Each inserted item
      has a priority associated with it and the client is usually interested
      in quick retrieval of the lowest-priority item in the queue. This
      data structure allows O(1) access to the lowest-priority item.
    """
    def  __init__(self):
        self.heap = []
        self.count = 0


    def push(self, item, priority):
        entry = (priority, self.count, item)
        heapq.heappush(self.heap, entry)
        self.count += 1


    def pop(self):
        (_, _, item) = heapq.heappop(self.heap)
        return item


    def isEmpty(self):
        return len(self.heap) == 0


    def update(self, item, priority):
        # If item already in priority queue with higher priority, update its priority and rebuild the heap.
        # If item already in priority queue with equal or lower priority, do nothing.
        # If item not in priority queue, do the same thing as self.push.
        for index, (p, c, i) in enumerate(self.heap):
            if i == item:
                if p python pacman.py -l mediumScaryMaze -p StayWestSearchAgent
Path found with total cost of 68719479864 in 0.2 seconds
Search nodes expanded: 108
Pacman emerges victorious! Score: 418
Average Score: 418.0
Scores:        418.0
Win Rate:      1/1 (1.00)
Record:        Win

如使用mediumMaze 布局：

E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumMaze -p SearchAgent -a fn=ucs
[SearchAgent] using function ucs
[SearchAgent] using problem type PositionSearchProblem
Path found with total cost of 68 in 0.3 seconds
Search nodes expanded: 269
Pacman emerges victorious! Score: 442
Average Score: 442.0
Scores:        442.0
Win Rate:      1/1 (1.00)
Record:        Win


E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumMaze -p StayEastSearchAgent
Path found with total cost of 1 in 0.2 seconds
Search nodes expanded: 260
Pacman emerges victorious! Score: 436
Average Score: 436.0
Scores:        436.0
Win Rate:      1/1 (1.00)
Record:        Win


E:\2019reforce_learning\cs188\proj1-search-python3>python pacman.py -l mediumMaze -p StayWestSearchAgent
Path found with total cost of 17183280440 in 0.2 seconds
Search nodes expanded: 173
Pacman emerges victorious! Score: 358
Average Score: 358.0
Scores:        358.0
Win Rate:      1/1 (1.00)
Record:        Win

欢迎关注微信公众号：“从零起步学习人工智能”。