搜索算法实验

实验二 搜索算法实验

​ 对下面这个有向图进行广度优先搜索和深度优先搜索

image-20241209143655870

​ 用字典来表示整个图，图由多个节点组成。将节点与其所有邻近节点的关系用键值对来表示，代码如下：

1
2
3
4
5
6
7
8
9
graph = {}
graph["A"] = ["B", "D", "F"]
graph["B"] = ["C", "E"]
graph["D"] = ["C"]
graph["F"] = ["G", "H"]
graph["C"] = []
graph["E"] = []
graph["G"] = []
graph["H"] = []

​ 键表示每个节点，值是一个数组，其中包含了键的所有邻近节点，这里的邻近节点是指从键所表示的节点出发，箭头所指向的其他节点。没有邻近节点的键所对应的值为空列表。

一、广度优先搜索

​ 使用函数deque来创建一个双端列表，可以实现在列表两端添加(append)和弹出(pop)元素。

1
2
3
from collections import deque
search_queue = deque()     #创建一个节点列表
search_queue += graph["A"]     #表示将"A"的相邻节点都添加到节点列表中

•我们指定 “A” 为起点，”G” 为终点。

•需要一个 searched 数组来保存搜索过的节点，防止同一个节点被多次搜索。

•每次从节点列表的最左边取出节点。

代码运行结果

1
2
3
4
#运行上述代码，可以得到输出：
B D F C E C G 
find the destination!
True

​ 根据节点的输出顺序就可以知道搜索顺序符合广度优先搜索的规则。

二、深度优先搜索

​ 只需将上面代码中的

1
2
3
node = search_queue.popleft() # 取出节点列表中最左边的节点
#改为如下语句
node = search_queue.pop() # 取出节点列表中最右边的节点

​ 因为广度优先搜索和深度优先搜索的区别就只是选择哪一个候补节点作为下一个节点的基准不同。

代码运行结果

1
2
3
4
#运行上述代码，可以得到输出：
F H G
find the destination!
True

​ 根据节点的输出顺序就可以知道搜索顺序符合深度优先搜索的规则。

三、实验作业

​ 代码实现使用深度优先搜索和广度优先搜索分别找到从A到I的路径

image-20241209144243070

四、深度优先代码

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
31
32
33
34
35
from collections import deque

# 创建一个图
graph = {}
graph["I"] = []
graph["H"] = ["I"]
graph["G"] = ["I"]
graph["F"] = ["E", "H"]
graph["E"] = ["H"]
graph["D"] = ["E"]
graph["C"] = ["G", "H"]
graph["B"] = ["F"]
graph["A"] = ["B", "C", "D"]

#深度优先搜索
search_queue = deque()
search_queue += graph["A"]

# 搜索函数
def search(start_node):
    search_queue = deque()
    search_queue += graph[start_node]
    searched = []
    while search_queue:
        node = search_queue.pop()
        print(node,end=" ")
        if not node in searched:
            if node == "I":
                print("\nfind the destination")
                return True
            else:
                search_queue += graph[node]
                searched.append(node)
    return False
print(search("A"))

运行结果截图

image-20241209144503995

五、广度优先代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#广度优先搜索
search_queue = deque()
search_queue += graph["A"]

def search(start_node):
    search_queue = deque()
    search_queue += graph[start_node]
    searched = []
    while search_queue:
        node = search_queue.popleft()
        print(node,end=" ")
        if not node in searched:
            if node == "I":
                print("\nfind the destination")
                return True
            else:
                search_queue += graph[node]
                searched.append(node)
    return False

print(search("A"))

运行结果截图

image-20241209144609968

六、实验结论

​ 本次实验使用了collections.deque。

​ collections.deque: 是一个双端队列，它允许我们在两端进行插入和删除操作。这在广度优先搜索中非常有用，因为它允许我们按照进入队列的顺序访问节点。deque的构造函数只有一个参数，即一个可迭代对象，如列表、元组等。