Chinaunix首页 | 论坛 | 博客
  • 博客访问: 596229
  • 博文数量: 282
  • 博客积分: 285
  • 博客等级: 二等列兵
  • 技术积分: 2851
  • 用 户 组: 普通用户
  • 注册时间: 2010-03-06 22:04
个人简介

Linuxer, ex IBMer. GNU https://hmchzb19.github.io/

文章分类

全部博文(282)

文章存档

2019年(10)

2018年(43)

2017年(79)

2016年(80)

2015年(58)

2014年(1)

2013年(8)

2012年(3)

分类: Python/Ruby

2019-04-14 15:51:31

最近在看这本书,复习了DFS,BFS,A*,书上的代码还是很精妙的.
先贴Search的这些算法.

点击(此处)折叠或打开

  1. from __future__ import annotations
  2. from typing import (TypeVar, Iterable, Sequence, Generic, List, Callable,
  3. Set, Deque, Dict, Any, Optional)
  4. from typing_extensions import Protocol
  5. from heapq import heappush, heappop

  6. T= TypeVar('T')

  7. def linear_contains(iterable: Iterable[T], key: T) ->bool:
  8.     for item in iterable:
  9.         if item == key:
  10.             return True
  11.     
  12.     return False


  13. C = TypeVar('C', bound='Comparable')

  14. class Comparable(Protocol):
  15.     def __eq__(self, other:Any) -> bool:
  16.         ...
  17.     
  18.     def __lt__(self:C, other:Any) -> bool:
  19.         ...
  20.     
  21.     def __gt__(self:C, other:Any) -> bool:
  22.         return (not self < other) and self != other
  23.     
  24.     def __le__(self:C, other:Any) -> bool:
  25.         return self < other or self == other
  26.     
  27.     def __ge__(self:C , other:C) ->bool:
  28.         return not self < other
  29.     
  30.     

  31. def binary_contains(sequence: Sequence[C], key:C) -> bool:
  32.     low: int = 0
  33.     high: int = len(sequence) - 1
  34.     while low<= high:
  35.         middle = (low+high)//2
  36.         if sequence[middle] < key:
  37.             low = middle + 1
  38.         elif sequence[middle] > key:
  39.             high = middle -1
  40.         else:
  41.             return True
  42.         
  43.     return False

  44. def main():
  45.     print(linear_contains([1,5,15,15,15,20], 5))
  46.     print(binary_contains(["a", "d", "e", "f", "z"], "f"))
  47.     print(binary_contains(["John", "mark", "ronald", "sarah"], "sheila"))





  48. class Stack(Generic[T]):
  49.     def __init__(self) ->None:
  50.         self._container: List[T] = []
  51.     
  52.     @property
  53.     def empty(self) ->bool:
  54.         return not self._container
  55.     
  56.     def push(self, item:T)->None:
  57.         self._container.append(item)
  58.     
  59.     def pop(self) ->T:
  60.         return self._container.pop()
  61.     
  62.     def __repr__(self) ->str:
  63.         return repr(self._container)


  64. class Node(Generic[T]):
  65.     def __init__(self, state:T, parent: Optional[Node], cost: float=0.0,
  66.         heuristic:float=0.0) ->None:
  67.             self.state: T = state
  68.             self.parent: Optional[Node] = parent
  69.             self.cost: float = cost
  70.             self.heuristic: float = heuristic
  71.             
  72.     def __lt__(self, other: Node) ->bool:
  73.         return (self.cost + self.heuristic) < (other.cost + other.heuristic)

  74. def dfs(initial: T, goal_test: Callable[[T], bool], successors:Callable[[T],List[T]]) ->Optional[Node[T]]:
  75.     #frontier is where we've yet to go
  76.     frontier: Stack[Node[T]]= Stack()
  77.     frontier.push(Node(initial, None))
  78.     
  79.     #explored is where we've been
  80.     explored: set[T] = {initial}
  81.     
  82.     #keep going while where is more to explore
  83.     while not frontier.empty:
  84.         current_node: Node[T] = frontier.pop()
  85.         current_state: T = current_node.state
  86.         
  87.         #if we found the goal, we 're done
  88.         if goal_test(current_state):
  89.             return current_node
  90.         
  91.         #check where we can go next and haven't explored
  92.         for child in successors(current_state):
  93.             if child in explored: #skip children we already explored
  94.                 continue
  95.             
  96.             explored.add(child)
  97.             frontier.push(Node(child, current_node))
  98.     return None

  99. def node_to_path(node: Node[T]) ->List[T]:
  100.     path: List[T] = [node.state]
  101.     #work backwards from end to front
  102.     while node.parent is not None:
  103.         node = node.parent
  104.         path.append(node.state)
  105.     path.reverse()
  106.     return path


  107. class Queue(Generic[T]):
  108.     def __init__(self)->None:
  109.         self._container: Deque[T] = Deque()
  110.     
  111.     @property
  112.     def empty(self)->bool:
  113.         return not self._container
  114.     
  115.     def push(self, item:T) ->None:
  116.         self._container.append(item)
  117.     
  118.     def pop(self) ->T:
  119.         return self._container.popleft()
  120.     
  121.     def __repr__(self) ->str:
  122.         return repr(self._container)
  123.     
  124. def bfs(initial: T, goal_test: Callable[[T], bool], successors:Callable[[T], List[T]]) ->Optional[Node[T]]:
  125.     #frontier is where we've yet to go
  126.     frontier: Queue[Node[T]] = Queue()
  127.     frontier.push(Node(initial, None))
  128.     
  129.     #explored is where we've been
  130.     explored: Set[T] = {initial}
  131.     
  132.     #keep going while there is more to explore
  133.     while not frontier.empty:
  134.         current_node: Node[T] = frontier.pop()
  135.         current_state: T = current_node.state
  136.         
  137.         #if we found the goal, we 're done
  138.         if goal_test(current_state):
  139.             return current_node
  140.         
  141.         #check where we can go next and haven't explored
  142.         for child in successors(current_state):
  143.             if child in explored: #skip children already explored
  144.                 continue
  145.             explored.add(child)
  146.             frontier.push(Node(child, current_node))
  147.         
  148.     return None


  149. class PriorityQueue(Generic[T]):
  150.     def __init__(self) ->None:
  151.         self._container: List[T] = []
  152.     
  153.     @property
  154.     def empty(self) ->bool:
  155.         return not self._container
  156.     
  157.     def push(self, item: T) ->None:
  158.         heappush(self._container, item)
  159.     
  160.     def pop(self)->T:
  161.         return heappop(self._container)
  162.     
  163.     def __repr__(self) ->str:
  164.         return repr(self._container)
  165.     
  166.     
  167. def astar(initial: T, goal_test: Callable[[T], bool], successors:Callable[[T], List[T]], heuristic:Callable[[T], float]) ->Optional[Node[T]]:
  168.     #frontier is where we've yet to go
  169.     frontier: PriorityQueue[Node[T]] = PriorityQueue()
  170.     frontier.push(Node(initial, None, 0.0, heuristic(initial)))
  171.     
  172.     #explored is where we've been
  173.     explored: Dict[T, float] = {initial: 0.0}
  174.     
  175.     #keep going while there is more to explore
  176.     while not frontier.empty:
  177.         current_node: Node[T] = frontier.pop()
  178.         current_state: T = current_node.state
  179.         #if we found the goal, we're done
  180.         if goal_test(current_state):
  181.             return current_node
  182.         
  183.         #check where we can go next and haven't explored
  184.         for child in successors(current_state):
  185.             new_cost: float = current_node.cost + 1
  186.             #1 assumes a grid,need a cost function for more sophisticated apps
  187.             if child not in explored or explored[child] > new_cost:
  188.                 explored[child] = new_cost
  189.                 frontier.push(Node(child, current_node, new_cost, heuristic(child)))
  190.                 
  191.     #went through everything and never found goal
  192.     return None
接下来是一个missionary问题的解法,3个牧师和3个食人族要到河对岸去,只有一条船,船最多载2个人,任何时候当食人族的数目多于牧师,食人族就会吃掉牧师。

点击(此处)折叠或打开

  1. from __future__ import annotations
  2. from typing import List, Optional
  3. from generic_search import bfs, Node, node_to_path

  4. MAX_NUM: int = 3

  5. class MCState:
  6.     
  7.     def __init__(self, missionaries: int, cannibals: int, boat: bool)->None:
  8.         #west bank missionaries
  9.         self.wm: int = missionaries
  10.         #west bank cannibals
  11.         self.wc: int = cannibals
  12.         #east bank missionaries
  13.         self.em: int = MAX_NUM - missionaries
  14.         #eat bank cannibals
  15.         self.ec: int = MAX_NUM - cannibals
  16.         self.boat: bool = boat
  17.     
  18.     def __str__(self) ->str:
  19.         return ("On the west bank there are {} missionaries and {} cannibals"
  20.         "\nonthe east bank there are {} missionaries and "
  21.         "{} cannibals.\nThe boat is on the {} bank.".format(
  22.             self.wm, self.wc, self.em, self.ec, ("west" if self.boat else "east")))
  23.         
  24.     
  25.     def goal_test(self) -> bool:
  26.         return self.is_legal and self.em == MAX_NUM and self.ec == MAX_NUM
  27.     
  28.     
  29.     @property
  30.     def is_legal(self) ->bool:
  31.         if self.wm < self.wc and self.wm > 0:
  32.             return False
  33.         if self.em < self.ec and self.em > 0:
  34.             return False
  35.         return True
  36.     
  37.     def successors(self) ->List[MCState]:
  38.         sucs: List[MCState] = []
  39.         
  40.         if self.boat: #boat on west bank
  41.             if self.wm > 1:
  42.                 sucs.append(MCState(self.wm -2, self.wc, not self.boat))
  43.             if self.wm > 0:
  44.                 sucs.append(MCState(self.wm -1, self.wc, not self.boat))
  45.             if self.wc > 1:
  46.                 sucs.append(MCState(self.wm, self.wc -2, not self.boat))
  47.             if self.wc > 0:
  48.                 sucs.append(MCState(self.wm, self.wc -1, not self.boat))
  49.             if (self.wc >0 ) and (self.wm > 0):
  50.                 sucs.append(MCState(self.wm -1, self.wc -1, not self.boat))
  51.             
  52.         else:
  53.             #Boat on east side
  54.             if self.em > 1:
  55.                 sucs.append(MCState(self.wm +2, self.wc, not self.boat))
  56.             if self.em > 0:
  57.                 sucs.append(MCState(self.wm +1, self.wc, not self.boat))
  58.             if self.ec > 1:
  59.                 sucs.append(MCState(self.wm, self.wc +2, not self.boat))
  60.             if self.ec > 0:
  61.                 sucs.append(MCState(self.wm, self.wc +1, not self.boat))
  62.             if (self.ec > 0) and (self.em > 0):
  63.                 sucs.append(MCState(self.wm + 1, self.wc + 1, not self.boat))
  64.         
  65.         return [ x for x in sucs if x.is_legal]


  66. def display_solution(path: List[MCState]):
  67.     if len(path) == 0:
  68.         return
  69.     
  70.     old_state: MCState = path[0]
  71.     print(old_state)
  72.     for current_state in path[1:]:
  73.         if current_state.boat:
  74.             print("{} missionaries and {} cannibals moved from the east "
  75.             " bank to the west bank.\n".format(old_state.em - current_state.em, old_state.ec - current_state.ec))
  76.         else:
  77.             print("{} missionaries and {} cannibals moved from the west "
  78.             "bank to the east bank.\n".format(old_state.wm - current_state.wm, old_state.wc - current_state.wc))
  79.             
  80.         print(current_state)
  81.         old_state = current_state
  82.     
  83.     

  84. def main():
  85.     
  86.     start: MCState = MCState(MAX_NUM, MAX_NUM, True)
  87.     solution: Optional[Node[MCState]] = bfs(start, MCState.goal_test,
  88.         MCState.successors)
  89.     if solution is None:
  90.         print("No solution found!")
  91.     else:
  92.         path: List[MCState] = node_to_path(solution)
  93.         display_solution(path)

  94. if __name__ == "__main__":
  95.     main()

  96. #执行结果如下
  97. ./missionaries.py
  98. On the west bank there are 3 missionaries and 3 cannibals
  99. onthe east bank there are 0 missionaries and 0 cannibals.
  100. The boat is on the west bank.
  101. 0 missionaries and 2 cannibals moved from the west bank to the east bank.

  102. On the west bank there are 3 missionaries and 1 cannibals
  103. onthe east bank there are 0 missionaries and 2 cannibals.
  104. The boat is on the east bank.
  105. 0 missionaries and 1 cannibals moved from the east bank to the west bank.

  106. On the west bank there are 3 missionaries and 2 cannibals
  107. onthe east bank there are 0 missionaries and 1 cannibals.
  108. The boat is on the west bank.
  109. 0 missionaries and 2 cannibals moved from the west bank to the east bank.

  110. On the west bank there are 3 missionaries and 0 cannibals
  111. onthe east bank there are 0 missionaries and 3 cannibals.
  112. The boat is on the east bank.
  113. 0 missionaries and 1 cannibals moved from the east bank to the west bank.

  114. On the west bank there are 3 missionaries and 1 cannibals
  115. onthe east bank there are 0 missionaries and 2 cannibals.
  116. The boat is on the west bank.
  117. 2 missionaries and 0 cannibals moved from the west bank to the east bank.

  118. On the west bank there are 1 missionaries and 1 cannibals
  119. onthe east bank there are 2 missionaries and 2 cannibals.
  120. The boat is on the east bank.
  121. 1 missionaries and 1 cannibals moved from the east bank to the west bank.

  122. On the west bank there are 2 missionaries and 2 cannibals
  123. onthe east bank there are 1 missionaries and 1 cannibals.
  124. The boat is on the west bank.
  125. 2 missionaries and 0 cannibals moved from the west bank to the east bank.

  126. On the west bank there are 0 missionaries and 2 cannibals
  127. onthe east bank there are 3 missionaries and 1 cannibals.
  128. The boat is on the east bank.
  129. 0 missionaries and 1 cannibals moved from the east bank to the west bank.

  130. On the west bank there are 0 missionaries and 3 cannibals
  131. onthe east bank there are 3 missionaries and 0 cannibals.
  132. The boat is on the west bank.
  133. 0 missionaries and 2 cannibals moved from the west bank to the east bank.

  134. On the west bank there are 0 missionaries and 1 cannibals
  135. onthe east bank there are 3 missionaries and 2 cannibals.
  136. The boat is on the east bank.
  137. 1 missionaries and 0 cannibals moved from the east bank to the west bank.

  138. On the west bank there are 1 missionaries and 1 cannibals
  139. onthe east bank there are 2 missionaries and 2 cannibals.
  140. The boat is on the west bank.
  141. 1 missionaries and 1 cannibals moved from the west bank to the east bank.

  142. On the west bank there are 0 missionaries and 0 cannibals
  143. onthe east bank there are 3 missionaries and 3 cannibals.
  144. The boat is on the east bank.



阅读(866) | 评论(0) | 转发(0) |
0

上一篇:使用不同版本的python来启动ipython

下一篇:没有了

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册