Implementing Search Algorithms

# Implementing Search Algorithms(DFS&BFS&UCS)

In this notebook we will go through implementing depth-first search, breadth-first search, and uniform cost search. We will use the graph given in the last activity.

One way of implementing a graph is to use a python dictionary (<https://docs.python.org/3/tutorial/datastructures.html#dictionaries>). The dictionary will have nodes as keys, and a list of nodes that each attaches to as values. In the cell below, have a go at writing down the graph given in the last activity.

*the value for the key is actually the list which includes all the nodes connected to the key node*

``` python
graph = {
            'h':['c','a','b']
            # Your code here
}
```

## Depth-first Search

Let\'s think about how we implement depth-first search. This code runs - you don\'t need to add anything to it. Let\'s talk through it and see if we can understand all the parts.

``` python
def dfs(graph, start, goal):
    # We set up lists to store the explored nodes 
    # and the nodes in the frontier. At the start we have 
    # no explored nodes, and the only node in the frontier 
    # is the start node
    explored = []
    frontier=[start]

# We set up a loop which runs while there are still nodes
    # to explore
    while frontier:
        current = frontier.pop() #what does this do? Try looking it up
        print(f'current: {current}')
        explored.append(current) #what does this do?
        print(f'explored: {explored}')
        # if we have found the goal, we break out of the loop
        if current==goal:
            break
        
        # If we haven't yet found the goal, we will add the neighbours of 
        # our current node to the frontier
        for neighbour in graph[current][::-1]: #does anyone know what this does?
            # We only add the neighbours to the frontier if they are not
            # already explored and if they are not already in the frontier
            if neighbour not in explored and neighbour not in frontier:
                frontier.append(neighbour)
        print(f'frontier: {frontier}')
    # when we break out of the loop, we will print the nodes we have explored in order
    print(explored)
```

``` python
# Try running the code
dfs(graph, 'h', 'g')
```

It is hard to create a whole available graph so I just copied one from CSDN

```python 
graph = {
    'A':['B','C'],
    'B':['A','C','D'],
    'C':['A','B','D','E'],
    'D':['B','C','E','F'],
    'E':['C','D'],
    'F':['D'],
}
```

Finally I got this

```python
current: A
explored: ['A']
frontier: ['C', 'B']
current: B
explored: ['A', 'B']
frontier: ['C', 'D']
current: D
explored: ['A', 'B', 'D']
```

If you don't need a node as the goal then this one is OK

```python
def DFS(graph,s):       
    stack = []          
    stack.append(s)      
    seen = set()       
    seen.add(s)
    while (len(stack) > 0):
        vertex = stack.pop()     
        nodes = graph[vertex]     #the list of the key'vertex'
        for w in nodes:           #first judge 'w' is in the nodes linked with the last node or not
            if w not in seen:     #then judge 'w' has been seen or not
                stack.append(w) 
                seen.add(w)
        print(vertex)             #print this node and search 'w' in the next loop
DFS(graph,'A')
#A
#C
#E
#D
#F
#B
```

## Breadth-first Search

Breadth-first search has a very similar structure to depth-first search. We simply have to change the order in which we explore the nodes. Let\'s try to put together some code to implement breadth-first search.

``` python
def bfs(graph, start, goal):
    # We set up lists to store the explored nodes 
    # and the nodes in the frontier. At the start we have 
    # no explored nodes, and the only node in the frontier 
    # is the start node

# Set up lists for the explored nodes and the frontier nodes
    
    # Your code here

# We set up a loop which runs while there are still nodes
    # to explore
    while frontier:
        # Take a node from the frontier. Which node should you take?

# Your code here

print(f'current: {current}')
        # Append this node to the list of explored nodes

# Your code here

print(f'explored: {explored}')
        # If the current node is the goal node, break out of the loop

# Your code here

# If we haven't yet found the goal, we will add the neighbours of 
        # our current node to the frontier. 
        # NB: this time we do not need to reverse the order of the nodes

# Your code here

print(f'frontier: {frontier}')
    # when we break out of the loop, we will print the nodes we have explored in order
    print(explored)
```

``` python
# Try running your code. Does it work? if not, can you work out how to solve the errors?
bfs(graph, 'h', 'g')
```

If use the graph created in DFS

```python
graph = {
    'A':['B','C'],
    'B':['A','C','D'],
    'C':['A','B','D','E'],
    'D':['B','C','E','F'],
    'E':['C','D'],
    'F':['D'],
}
def BFS(graph,s):       #graph表示图表关系，s表示开始的节点
    queue = []          #新建队列
    queue.append(s)       #将初始节点加入到队列中
    seen = set()       #建立一个集合，后续判断是否重复
    seen.add(s)
    while (len(queue) > 0):
        vertex = queue.pop(0)     #移出队列的第一个元素
        nodes = graph[vertex]     #找到那个元素的相关节点并保存起来
        for w in nodes:
            if w not in seen:      #如果节点不重复，就添加到队列中
                queue.append(w)
                seen.add(w)
        print(vertex)
BFS(graph,'A')
#A
#B
#C
#D
#E
#F
```

The only difference between them is ***vertex = queue.pop(0)*** in**BFS**and ***vertex = stack.pop() ***in **DFS**

## Uniform Cost Search

In uniform cost search, we always expand the path that has the lowest cost. Can we do this with the graph representation we currently have?

No - we have not attached any costs to the edges in the graph. Your first task for implementing USC is to change the graph representation so that we have costs attached to the edges. Any suggestions on how to do this?

``` python
# We need to add costs to each edge.
ucs_graph = {

}
```

### Implementing UCS

UCS has similarities to breadth-first search, but we need to weight the nodes in the frontier with the cost of getting to those nodes.

``` python
def ucs(graph, start, goal):
    # We will again set up lists for the explored and frontier nodes. 
    # In the frontier, we need to give the cost of getting to that node.
    # The cost of getting to the start node from the start node is 0

# Your code here

while frontier:
        # We are implementing a variant of BFS, so how should we pick the node to expand?
        
        # Your code here

print(f'current: {current}')
        # We again add the current node to the explored list
        
        # Your code here

print(f'explored: {explored}')
        # We need to check whether the current node is actually the goal
        
        # Your code here
        
        # We look at the neighbours of the current node.
        # If it's not explored or in the frontier, we add it to the frontier.
        # When we add it to the frontier, we must also add the cost of getting there from the start node.
        # How should we calculate that?
        for neighbour in graph[current[0]]:
            # we use a little trick to get the first element of each tuple in the frontier
            if neighbour not in explored and neighbour not in dict(frontier).keys():
                # To get the cost of getting to the neighbouring node, note that we 
                # already have the cost of getting to the current node, so we just have to add 
                # on how much it takes to get to the neightbouring node from the current node
                
                # Your code here

# We need to sort the frontier by the cost of getting to each node
                # We can also sort alphabetically to break any ties
                frontier.sort(key=lambda x:(x[1], x[0]))
        print(f'frontier: {frontier}')
    print(explored)
```

``` python
ucs(ucs_graph, 'h','g')
```