cs50

week1-search

search

goal test

ai中的一个重要概念，确定一个state是否是最终的目标。

path cost

numercial cost与路径紧密相关

soving search problem

node

node是ai中的一个重要概念，它表示一个状态，它有父节点(node that generated this node)，an action(action applied to this state)，一个path cost。

appraoch of ai

• start with a frotier that contains that initial node
• repeat:
  1. if the frontier is empty, then fail
  2. remove a node from the frontier
  3. if the node contains a goal state, then succeed
  4. expand node,add resulting nodes to the frontier
• 但是这个general appraoch可能出现错误，如果图中节点的连接方式存在双指针，则有可能陷入循环。

revised approach

• start with a frontier that contains the initial node
• start with an empty explored set
• repeat:
  1. if the frontier is empty, then fail
  2. remove a node from the frontier
  3. if the node contains a goal state, then succeed
  4. add node to the explored set
  5. expand node,add resulting nodes to the frontier,but only if not in the frontier or the explored set

栈与depth-first search

• 在具体的算法实现中，我们可以利用栈这个数据结构来实现frontier的作用。
• 这样我们的搜索方式便是深度优先搜索（找到一个路径直到尽头）。

队列与breadth-first search

• 在具体的算法实现中，若利用队列这个数据结构来实现frontier的作用，则我们的搜索方式便是广度优先搜索（多个路径共同进行）。

greedy best-first search

与传统的dfs和bfs不同，expands the node that is closest to the goal state.通过启发式算法实现

project0-degrees

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def shortest_path(source, target):
    """
    Returns the shortest list of (movie_id, person_id) pairs
    that connect the source to the target.
    If no possible path, returns None.
    """
      
    # TODO
    # 注意我们此时为bfs则采取队列数据结构
    frontier = QueueFrontier()
    explored = set()
    frontier.add(source,None,None)
    while not frontier.empty():
        node = frontier.remove()
        explored.add(node.state)
        neighbors = neighbors_for_person(node.state)
        for neighbor in neighbors:
            _, person_id =neighbor
            if person_id == target:
                path=[neighbor]
                while node.parent is not None:
                    path.append(node.action)
                    node = node.parent
                # 注意此时需要翻转
                path.reverse()
                return path
                # 如果此时的节点没有被探索过，且不在frontier中，则加入frontier
            if person_id not in explored and not frontier.contains_state(person_id):
                frontier.add(person_id,node,neighbor)
    return None