-
Notifications
You must be signed in to change notification settings - Fork 0
/
UCS_G3.py
105 lines (80 loc) · 2.82 KB
/
UCS_G3.py
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
try:
import queue
except ImportError:
import Queue as queue
from queue import PriorityQueue
graph3 = {
'a': {'b':2,'c':2},
'b': {'a':2,'d':1},
'c': {'a':2,'d':8,'f':3},
'd': {'b':1,'c':8,'e':2,'s':3},
'e': {'d':2,'h':8,'r':2,'s':9},
'f': {'c':3,'g':2,'r':2},
'g': {'f':2},
'h': {'e':8,'p':4,'q':4},
'p': {'h':4,'q':15,'s':1},
'q': {'h':4,'p':15},
'r': {'e':2,'f':2},
's': {'d':3,'e':9,'p':1}
}
AM3= [[0,2,2,0,0,0,0,0,0,0,0,0],
[2,0,0,1,0,0,0,0,0,0,0,0],
[2,0,0,8,0,3,0,0,0,0,0,0],
[0,1,8,0,2,0,0,0,0,0,0,3],
[0,0,0,2,0,0,0,8,0,0,2,9],
[0,0,3,0,0,0,2,0,0,0,2,0],
[0,0,0,0,0,2,0,0,0,0,0,0],
[0,0,0,0,8,0,0,0,4,4,0,0],
[0,0,0,0,0,0,0,4,0,15,0,1],
[0,0,0,0,0,0,0,4,15,0,0,0],
[0,0,0,0,2,2,0,0,0,0,0,0],
[0,0,0,3,9,0,0,0,1,0,0,0]]
def UCS(graph, start, goal):
visited = set()
expanded=[]
queue = PriorityQueue()
queue.put((0, start))
while queue:
cost, node = queue.get()
current = node[-1]
if current not in visited:
visited.add(current)
expanded.append(current)
if current == goal:
return node, expanded
neighbours = graph[current]
for i in neighbours:
if i not in visited:
total_cost = cost + neighbours[i]
queue.put((total_cost, node+i))
maps = {'a':0, 'b': 1, 'c':2, 'd':3, 'e':4, 'f':5, 'g':6, 'h':7, 'p':8, 'q':9, 'r':10, 's':11 }
def USC_Matrix(graph,start, goal):
visited = set()
expanded = []
queue = PriorityQueue()
queue.put((0, start))
while queue:
cost, node = queue.get()
current = node[-1]
if current not in visited:
visited.add(current)
expanded.append(current)
if current == goal:
return node, expanded
length = len(graph[maps[current]])
for neighbor in range(length):
if neighbor not in visited and graph[maps[current]][neighbor] >= 1:
j = [k for k, v in maps.items() if v == neighbor]
if j[0] not in visited:
total_cost = cost + graph[maps[current]][neighbor]
queue.put((total_cost, node + j[0]))
path, expanded = UCS(graph3,'s','g')
output = [char for char in path]
print("\nThe path of undirected graph 3 through UCS Priority Queue with vertex list is : " + "->".join(output))
print("The states expanded with vertex list are:")
print(expanded)
path_AM, expanded_AM = USC_Matrix(AM3,'s','g')
output1 = [char for char in path]
print("\nThe path of undirected graph 3 through UCS Priority Queue with adjacency matrix is : " + "->".join(output1))
print("The states expanded with adjacency matrix are:")
print(expanded)