了解IT技术
老九你最好的选择

推荐本书Classic_Computer_Science_Problems_in_Python

最近在看这本书,复习了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.     return False
  12. C = TypeVar(‘C’, bound=’Comparable’)
  13. class Comparable(Protocol):
  14.     def __eq__(self, other:Any) -> bool:
  15.         …
  16.     def __lt__(self:C, other:Any) -> bool:
  17.         …
  18.     def __gt__(self:C, other:Any) -> bool:
  19.         return (not self < other) and self != other
  20.     def __le__(self:C, other:Any) -> bool:
  21.         return self < other or self == other
  22.     def __ge__(self:C , other:C) ->bool:
  23.         return not self < other
  24. def binary_contains(sequence: Sequence[C], key:C) -> bool:
  25.     low: int = 0
  26.     high: int = len(sequence) – 1
  27.     while low<= high:
  28.         middle = (low+high)//2
  29.         if sequence[middle] < key:
  30.             low = middle + 1
  31.         elif sequence[middle] > key:
  32.             high = middle -1 
  33.         else:
  34.             return True
  35.     return False
  36. def main():
  37.     print(linear_contains([1,5,15,15,15,20], 5))
  38.     print(binary_contains([“a”, “d”, “e”, “f”, “z”], “f”))
  39.     print(binary_contains([“John”, “mark”, “ronald”, “sarah”], “sheila”))
  40. class Stack(Generic[T]):
  41.     def __init__(self) ->None:
  42.         self._container: List[T] = []
  43.     @property
  44.     def empty(self) ->bool:
  45.         return not self._container 
  46.     def push(self, item:T)->None:
  47.         self._container.append(item)
  48.     def pop(self) ->T:
  49.         return self._container.pop()
  50.     def __repr__(self) ->str:
  51.         return repr(self._container)
  52. class Node(Generic[T]):
  53.     def __init__(self, state:T, parent: Optional[Node], cost: float=0.0,
  54.         heuristic:float=0.0) ->None:
  55.             self.state: T = state
  56.             self.parent: Optional[Node] = parent
  57.             self.cost: float = cost
  58.             self.heuristic: float = heuristic
  59.     def __lt__(self, other: Node) ->bool:
  60.         return (self.cost + self.heuristic) < (other.cost + other.heuristic)
  61. def dfs(initial: T, goal_test: Callable[[T], bool], successors:Callable[[T],List[T]]) ->Optional[Node[T]]:
  62.     #frontier is where we’ve yet to go
  63.     frontier: Stack[Node[T]]= Stack()
  64.     frontier.push(Node(initial, None))
  65.     #explored is where we’ve been
  66.     explored: set[T] = {initial}
  67.     #keep going while where is more to explore
  68.     while not frontier.empty:
  69.         current_node: Node[T] = frontier.pop()
  70.         current_state: T = current_node.state
  71.         #if we found the goal, we ‘re done
  72.         if goal_test(current_state):
  73.             return current_node
  74.         #check where we can go next and haven’t explored
  75.         for child in successors(current_state):
  76.             if child in explored: #skip children we already explored
  77.                 continue
  78.             explored.add(child)
  79.             frontier.push(Node(child, current_node))
  80.     return None
  81. def node_to_path(node: Node[T]) ->List[T]:
  82.     path: List[T] = [node.state]
  83.     #work backwards from end to front
  84.     while node.parent is not None:
  85.         node = node.parent
  86.         path.append(node.state)
  87.     path.reverse()
  88.     return path
  89. class Queue(Generic[T]):
  90.     def __init__(self)->None:
  91.         self._container: Deque[T] = Deque()
  92.     @property
  93.     def empty(self)->bool:
  94.         return not self._container
  95.     def push(self, item:T) ->None:
  96.         self._container.append(item)
  97.     def pop(self) ->T:
  98.         return self._container.popleft()
  99.     def __repr__(self) ->str:
  100.         return repr(self._container)
  101. def bfs(initial: T, goal_test: Callable[[T], bool], successors:Callable[[T], List[T]]) ->Optional[Node[T]]:
  102.     #frontier is where we’ve yet to go
  103.     frontier: Queue[Node[T]] = Queue()
  104.     frontier.push(Node(initial, None))
  105.     #explored is where we’ve been 
  106.     explored: Set[T] = {initial}
  107.     #keep going while there is more to explore
  108.     while not frontier.empty:
  109.         current_node: Node[T] = frontier.pop()
  110.         current_state: T = current_node.state
  111.         #if we found the goal, we ‘re done
  112.         if goal_test(current_state):
  113.             return current_node
  114.         #check where we can go next and haven’t explored
  115.         for child in successors(current_state):
  116.             if child in explored: #skip children already explored
  117.                 continue
  118.             explored.add(child)
  119.             frontier.push(Node(child, current_node))
  120.     return None
  121. class PriorityQueue(Generic[T]):
  122.     def __init__(self) ->None:
  123.         self._container: List[T] = []
  124.     @property
  125.     def empty(self) ->bool:
  126.         return not self._container 
  127.     def push(self, item: T) ->None:
  128.         heappush(self._container, item)
  129.     def pop(self)->T:
  130.         return heappop(self._container)
  131.     def __repr__(self) ->str:
  132.         return repr(self._container)
  133. def astar(initial: T, goal_test: Callable[[T], bool], successors:Callable[[T], List[T]], heuristic:Callable[[T], float]) ->Optional[Node[T]]:
  134.     #frontier is where we’ve yet to go
  135.     frontier: PriorityQueue[Node[T]] = PriorityQueue()
  136.     frontier.push(Node(initial, None, 0.0, heuristic(initial)))
  137.     #explored is where we’ve been
  138.     explored: Dict[T, float] = {initial: 0.0}
  139.     #keep going while there is more to explore
  140.     while not frontier.empty:
  141.         current_node: Node[T] = frontier.pop()
  142.         current_state: T = current_node.state
  143.         #if we found the goal, we’re done
  144.         if goal_test(current_state):
  145.             return current_node
  146.         #check where we can go next and haven’t explored
  147.         for child in successors(current_state):
  148.             new_cost: float = current_node.cost + 1
  149.             #1 assumes a grid,need a cost function for more sophisticated apps
  150.             if child not in explored or explored[child] > new_cost:
  151.                 explored[child] = new_cost
  152.                 frontier.push(Node(child, current_node, new_cost, heuristic(child)))
  153.     #went through everything and never found goal
  154.     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.     def __init__(self, missionaries: int, cannibals: int, boat: bool)->None:
  7.         #west bank missionaries 
  8.         self.wm: int = missionaries
  9.         #west bank cannibals
  10.         self.wc: int = cannibals
  11.         #east bank missionaries
  12.         self.em: int = MAX_NUM – missionaries
  13.         #eat bank cannibals
  14.         self.ec: int = MAX_NUM – cannibals
  15.         self.boat: bool = boat
  16.     def __str__(self) ->str:
  17.         return (“On the west bank there are {} missionaries and {} cannibals”
  18.         “\nonthe east bank there are {} missionaries and “
  19.         “{} cannibals.\nThe boat is on the {} bank.”.format(
  20.             self.wm, self.wc, self.em, self.ec, (“west” if self.boat else “east”)))
  21.     def goal_test(self) -> bool:
  22.         return self.is_legal and self.em == MAX_NUM and self.ec == MAX_NUM
  23.     @property
  24.     def is_legal(self) ->bool:
  25.         if self.wm < self.wc and self.wm > 0:
  26.             return False
  27.         if self.em < self.ec and self.em > 0:
  28.             return False
  29.         return True
  30.     def successors(self) ->List[MCState]:
  31.         sucs: List[MCState] = []
  32.         if self.boat: #boat on west bank
  33.             if self.wm > 1:
  34.                 sucs.append(MCState(self.wm -2, self.wc, not self.boat))
  35.             if self.wm > 0:
  36.                 sucs.append(MCState(self.wm -1, self.wc, not self.boat))
  37.             if self.wc > 1:
  38.                 sucs.append(MCState(self.wm, self.wc -2, not self.boat))
  39.             if self.wc > 0:
  40.                 sucs.append(MCState(self.wm, self.wc -1, not self.boat))
  41.             if (self.wc >0 ) and (self.wm > 0):
  42.                 sucs.append(MCState(self.wm -1, self.wc -1, not self.boat))
  43.         else:
  44.             #Boat on east side
  45.             if self.em > 1:
  46.                 sucs.append(MCState(self.wm +2, self.wc, not self.boat))
  47.             if self.em > 0:
  48.                 sucs.append(MCState(self.wm +1, self.wc, not self.boat))
  49.             if self.ec > 1:
  50.                 sucs.append(MCState(self.wm, self.wc +2, not self.boat))
  51.             if self.ec > 0:
  52.                 sucs.append(MCState(self.wm, self.wc +1, not self.boat))
  53.             if (self.ec > 0) and (self.em > 0):
  54.                 sucs.append(MCState(self.wm + 1, self.wc + 1, not self.boat))
  55.         return [ x for x in sucs if x.is_legal]
  56. def display_solution(path: List[MCState]):
  57.     if len(path) == 0:
  58.         return
  59.     old_state: MCState = path[0]
  60.     print(old_state)
  61.     for current_state in path[1:]:
  62.         if current_state.boat:
  63.             print(“{} missionaries and {} cannibals moved from the east “
  64.             ” bank to the west bank.\n”.format(old_state.em – current_state.em, old_state.ec -current_state.ec))
  65.         else:
  66.             print(“{} missionaries and {} cannibals moved from the west “
  67.             “bank to the east bank.\n”.format(old_state.wm – current_state.wm, old_state.wc – current_state.wc))
  68.         print(current_state)
  69.         old_state = current_state
  70. def main():
  71.     start: MCState = MCState(MAX_NUM, MAX_NUM, True)
  72.     solution: Optional[Node[MCState]] = bfs(start, MCState.goal_test,
  73.         MCState.successors)
  74.     if solution is None:
  75.         print(“No solution found!”)
  76.     else:
  77.         path: List[MCState] = node_to_path(solution)
  78.         display_solution(path)
  79. if __name__ == “__main__”:
  80.     main()
  81. #执行结果如下
  82. ./missionaries.py 
  83. On the west bank there are 3 missionaries and 3 cannibals
  84. onthe east bank there are 0 missionaries and 0 cannibals.
  85. The boat is on the west bank.
  86. 0 missionaries and 2 cannibals moved from the west bank to the east bank.
  87. On the west bank there are 3 missionaries and 1 cannibals
  88. onthe east bank there are 0 missionaries and 2 cannibals.
  89. The boat is on the east bank.
  90. 0 missionaries and 1 cannibals moved from the east bank to the west bank.
  91. On the west bank there are 3 missionaries and 2 cannibals
  92. onthe east bank there are 0 missionaries and 1 cannibals.
  93. The boat is on the west bank.
  94. 0 missionaries and 2 cannibals moved from the west bank to the east bank.
  95. On the west bank there are 3 missionaries and 0 cannibals
  96. onthe east bank there are 0 missionaries and 3 cannibals.
  97. The boat is on the east bank.
  98. 0 missionaries and 1 cannibals moved from the east bank to the west bank.
  99. On the west bank there are 3 missionaries and 1 cannibals
  100. onthe east bank there are 0 missionaries and 2 cannibals.
  101. The boat is on the west bank.
  102. 2 missionaries and 0 cannibals moved from the west bank to the east bank.
  103. On the west bank there are 1 missionaries and 1 cannibals
  104. onthe east bank there are 2 missionaries and 2 cannibals.
  105. The boat is on the east bank.
  106. 1 missionaries and 1 cannibals moved from the east bank to the west bank.
  107. On the west bank there are 2 missionaries and 2 cannibals
  108. onthe east bank there are 1 missionaries and 1 cannibals.
  109. The boat is on the west bank.
  110. 2 missionaries and 0 cannibals moved from the west bank to the east bank.
  111. On the west bank there are 0 missionaries and 2 cannibals
  112. onthe east bank there are 3 missionaries and 1 cannibals.
  113. The boat is on the east bank.
  114. 0 missionaries and 1 cannibals moved from the east bank to the west bank.
  115. On the west bank there are 0 missionaries and 3 cannibals
  116. onthe east bank there are 3 missionaries and 0 cannibals.
  117. The boat is on the west bank.
  118. 0 missionaries and 2 cannibals moved from the west bank to the east bank.
  119. On the west bank there are 0 missionaries and 1 cannibals
  120. onthe east bank there are 3 missionaries and 2 cannibals.
  121. The boat is on the east bank.
  122. 1 missionaries and 0 cannibals moved from the east bank to the west bank.
  123. On the west bank there are 1 missionaries and 1 cannibals
  124. onthe east bank there are 2 missionaries and 2 cannibals.
  125. The boat is on the west bank.
  126. 1 missionaries and 1 cannibals moved from the west bank to the east bank.
  127. On the west bank there are 0 missionaries and 0 cannibals
  128. onthe east bank there are 3 missionaries and 3 cannibals.
  129. The boat is on the east bank.
赞(0) 打赏
未经允许不得转载:老九IT技术网 » 推荐本书Classic_Computer_Science_Problems_in_Python

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

老九为IT技术人提供最全面的IT资讯和交流互动

欢迎投稿广告合作

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏