-
Notifications
You must be signed in to change notification settings - Fork 0
/
BestFirstSearch.py
83 lines (63 loc) · 2.62 KB
/
BestFirstSearch.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
#Method BestFirstSearch for Searching the Goal State #-----Chandresh Maniya-----
def BestFirstSearch(graph, start, goal, heuristicValueDict):
# keep track of all visited nodes #-----Best First Search-----
explored = []
# keep track of nodes to be checked
queue = [start]
flag = 0
# keep looping until there are nodes still to be checked
while queue:
# pop first node from queue
node = queue.pop(0)
if node == goal:
explored.append(node)
flag = 1
break
else:
if node not in explored:
# add node to list of explored nodes
explored.append(node)
adjacents = graph[node]
# add neighbours with minimum heuristic Values of node to queue
localHeuristic = []
for i in adjacents:
localHeuristic.append(heuristicValueDict[i])
#finding minimum heuristic from the list of neighbours
localMin = min(localHeuristic)
for key, value in heuristicValueDict.items():
if value == localMin:
queue.append(key)
if flag == 1:
print("Succesfully Reached to the Goal!!! :)")
print(" Final Path : ",explored)
else:
print("Goal is Not Rechable :(")
#Entering Count of Total Nodes
n = int(input("Enter Number of Nodes: "))
nodes = [] #List of All Nodes
#One by one all nodes will be entered
for i in range(0, n):
nodes.append(input("Enter Node " + str(i+1) + ": "))
#List of adjacents of all nodes
adjacentList = []
#One by One adjacents of all nodes will be entered
for i in range(0, n):
adjacentList.append(input("Enter Adjecents of Node " + nodes[i] + " With Space: ").split())
#Graph of all nodes
graph = {}
#Assigning Nodes and Adjacent of Nodes to the dictionary Graph
for (key, value) in zip(nodes, adjacentList):
graph[key] = value
heuristicValues = []
for i in range(0, n):
heuristicValues.append(int(input("Enter Heuristic Value of " + nodes[i] + " - G : ")))
heuristicValueDict = {}
for (key, value) in zip(nodes, heuristicValues):
heuristicValueDict[key] = value
print("Graph :")
print(graph)
print("\n")
source = input("Enter Source Node: ")
goal = input("Enter Goal Node: ")
#Calling BestFirstSearch method
BestFirstSearch(graph, source, goal, heuristicValueDict)