Created
November 14, 2017 19:12
-
-
Save SohanChy/7e585e84ebdb482e0e93967afc46ecdc to your computer and use it in GitHub Desktop.
AI Book Searching Algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| romania_map = { | |
| "Arad": {"Zerind": 75, "Timisoara": 118, "Sibiu": 140}, | |
| "Zerind": {"Arad": 75, "Oradea": 71}, | |
| "Oradea": {"Zerind": 71, "Sibiu": 151}, | |
| "Timisoara": {"Arad": 118, "Lugoj": 111}, | |
| "Lugoj": {"Timisoara": 111, "Mehadia":70}, | |
| "Mehadia": {"Lugoj": 70, "Dobreta": 75}, | |
| "Dobreta": {"Mehadia":75, "Craiova":120}, | |
| "Craiova": {"Dobreta": 120, "RimnicuVilcea": 146, "Pitesi": 138}, | |
| "RimnicuVilcea": {"Craiova": 146, "Pitesi": 97, "Sibiu":80}, | |
| "Sibiu": {"Arad": 140, "Oradea":151, "RimnicuVilcea": 80, "Fagaras": 99}, | |
| "Fagaras": {"Sibiu": 99, "Bucharest":211}, | |
| "Pitesi": {"Bucharest": 101, "RimnicuVilcea": 97, "Craiova": 138}, | |
| "Bucharest": {"Pitesi": 101, "Fagaras": 211, "Giurgiu": 90, "Urziceni": 85}, | |
| "Giurgiu": {"Bucharest": 90}, | |
| "Urziceni": {"Bucharest": 85, "Hirsova": 98, "Vaslui": 142}, | |
| "Hirsova": {"Urziceni": 98, "Eforie": 86}, | |
| "Eforie": {"Hirsova": 86}, | |
| "Vaslui": {"Urziceni": 142, "Iasi": 92}, | |
| "Iasi": {"Vaslui": 92, "Neamt": 87}, | |
| "Neamt": {"Iasi": 87} | |
| } | |
| romania_distance_bucharest = { | |
| "Arad": 366, | |
| "Zerind": 374, | |
| "Oradea": 380, | |
| "Timisoara": 329, | |
| "Lugoj": 244, | |
| "Mehadia": 241, | |
| "Dobreta": 242, | |
| "Craiova": 160, | |
| "RimnicuVilcea": 193, | |
| "Sibiu": 253, | |
| "Fagaras": 178, | |
| "Pitesi": 98, | |
| "Bucharest": 0, | |
| "Giurgiu": 77, | |
| "Urziceni": 80, | |
| "Hirsova": 151, | |
| "Eforie": 161, | |
| "Vaslui": 199, | |
| "Iasi": 226, | |
| "Neamt": 234 | |
| } | |
| class Node: | |
| def calc_path_cost(self,cost): | |
| if self.prev != None: | |
| return self.prev.path_cost + cost | |
| else: | |
| return 0 | |
| def __init__(self,name,prev,hcost,cost): | |
| self.name = name | |
| self.prev = prev | |
| self.path_cost = self.calc_path_cost(cost) | |
| self.hcost = hcost | |
| self.cost = self.path_cost + self.hcost | |
| def is_equal(self,other_node): | |
| if self.name == other_node.name: | |
| return True | |
| else: | |
| return False | |
| class myQue: | |
| def __init__(self,innerList = []): | |
| self.innerList = innerList | |
| def push(self,value): | |
| self.innerList.append(value) | |
| def pop(self): | |
| return self.innerList.pop(0) | |
| def get(self): | |
| return list(self.innerList) | |
| def empty(self): | |
| if len(self.innerList)==0: | |
| return True | |
| else: | |
| return False | |
| def first(self): | |
| return self.innerList[0] | |
| def sort_by_function(self,func): | |
| #print("B: ",end="") | |
| #for i in self.innerList: | |
| # print(i.cost,end=",") | |
| #print(); | |
| self.innerList = sorted(self.innerList,key = func) | |
| #print("A: ",end="") | |
| #for i in self.innerList: | |
| # print(i.cost,end=",") | |
| #print(); | |
| def bfs_travel(start): | |
| def cost_return(x): | |
| return x.cost | |
| def staight_line_cost(name): | |
| return romania_distance_bucharest[name] | |
| if start not in romania_map: | |
| print("Invalid start or dest") | |
| else: | |
| #Bucharest is fixed since no other destination data is available | |
| dest = "Bucharest" | |
| visited = [] | |
| q = myQue() | |
| node = Node(start,None,staight_line_cost(start),0) | |
| q.push(node) | |
| while q.empty != True: | |
| now = q.pop() | |
| if now.name == dest: | |
| tcost = now.cost | |
| path = [now.name,] | |
| while now.prev != None: | |
| tcost = now.prev.cost | |
| path.append(now.prev.name) | |
| now = now.prev | |
| #print(tcost) | |
| print(list(reversed(path))) | |
| break | |
| visited.append(now) | |
| fringe = list(romania_map[now.name].keys()) | |
| for loc in fringe: | |
| is_visited = False | |
| for v in visited: | |
| if loc == v.name: | |
| is_visited = True | |
| if is_visited == True: | |
| continue | |
| cost = romania_map[now.name][loc] | |
| node = Node(loc,now,staight_line_cost(loc),cost) | |
| q.push(node) | |
| q.sort_by_function(cost_return); | |
| #start = input("Start from?") | |
| #dest = input("Destination?") | |
| bfs_travel("Arad") | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| romania_map = { | |
| "Arad": {"Zerind": 75, "Timisoara": 118, "Sibiu": 140}, | |
| "Zerind": {"Arad": 75, "Oradea": 71}, | |
| "Oradea": {"Zerind": 71, "Sibiu": 151}, | |
| "Timisoara": {"Arad": 118, "Lugoj": 111}, | |
| "Lugoj": {"Timisoara": 111, "Mehadia":70}, | |
| "Mehadia": {"Lugoj": 70, "Dobreta": 75}, | |
| "Dobreta": {"Mehadia":75, "Craiova":120}, | |
| "Craiova": {"Dobreta": 120, "RimnicuVilcea": 146, "Pitesi": 138}, | |
| "RimnicuVilcea": {"Craiova": 146, "Pitesi": 97, "Sibiu":80}, | |
| "Sibiu": {"Arad": 140, "Oradea":151, "RimnicuVilcea": 80, "Fagaras": 99}, | |
| "Fagaras": {"Sibiu": 99, "Bucharest":211}, | |
| "Pitesi": {"Bucharest": 101, "RimnicuVilcea": 97, "Craiova": 138}, | |
| "Bucharest": {"Pitesi": 101, "Fagaras": 211, "Giurgiu": 90, "Urziceni": 85}, | |
| "Giurgiu": {"Bucharest": 90}, | |
| "Urziceni": {"Bucharest": 85, "Hirsova": 98, "Vaslui": 142}, | |
| "Hirsova": {"Urziceni": 98, "Eforie": 86}, | |
| "Eforie": {"Hirsova": 86}, | |
| "Vaslui": {"Urziceni": 142, "Iasi": 92}, | |
| "Iasi": {"Vaslui": 92, "Neamt": 87}, | |
| "Neamt": {"Iasi": 87} | |
| } | |
| romania_distance_bucharest = { | |
| "Arad": 366, | |
| "Zerind": 374, | |
| "Oradea": 380, | |
| "Timisoara": 329, | |
| "Lugoj": 244, | |
| "Mehadia": 241, | |
| "Dobreta": 242, | |
| "Craiova": 160, | |
| "RimnicuVilcea": 193, | |
| "Sibiu": 253, | |
| "Fagaras": 178, | |
| "Pitesi": 98, | |
| "Bucharest": 0, | |
| "Giurgiu": 77, | |
| "Urziceni": 80, | |
| "Hirsova": 151, | |
| "Eforie": 161, | |
| "Vaslui": 199, | |
| "Iasi": 226, | |
| "Neamt": 234 | |
| } | |
| class Node: | |
| def __init__(self,name,prev,cost): | |
| self.name = name | |
| self.prev = prev | |
| self.cost = cost | |
| def is_equal(self,other_node): | |
| if self.name == other_node.name: | |
| return True | |
| else: | |
| return False | |
| class myQue: | |
| def __init__(self,innerList = []): | |
| self.innerList = innerList | |
| def push(self,value): | |
| self.innerList.append(value) | |
| def pop(self): | |
| return self.innerList.pop(0) | |
| def get(self): | |
| return list(self.innerList) | |
| def empty(self): | |
| if len(self.innerList)==0: | |
| return True | |
| else: | |
| return False | |
| def first(self): | |
| return self.innerList[0] | |
| def sort_by_function(self,func): | |
| #print("B: ",end="") | |
| #for i in self.innerList: | |
| # print(i.cost,end=",") | |
| #print(); | |
| self.innerList = sorted(self.innerList,key = func) | |
| #print("A: ",end="") | |
| #for i in self.innerList: | |
| # print(i.cost,end=",") | |
| #print(); | |
| def bfs_travel(start): | |
| def cost_return(x): | |
| return x.cost | |
| def staight_line_cost(name): | |
| return romania_distance_bucharest[name] | |
| if start not in romania_map: | |
| print("Invalid start or dest") | |
| else: | |
| #Bucharest is fixed since no other destination data is available | |
| dest = "Bucharest" | |
| visited = [] | |
| q = myQue() | |
| node = Node(start,None,staight_line_cost(start)) | |
| q.push(node) | |
| while q.empty != True: | |
| now = q.pop() | |
| if now.name == dest: | |
| tcost = now.cost | |
| path = [now.name,] | |
| while now.prev != None: | |
| tcost = now.prev.cost | |
| path.append(now.prev.name) | |
| now = now.prev | |
| #print(tcost) | |
| print(list(reversed(path))) | |
| break | |
| visited.append(now) | |
| fringe = list(romania_map[now.name].keys()) | |
| for loc in fringe: | |
| is_visited = False | |
| for v in visited: | |
| if loc == v.name: | |
| is_visited = True | |
| if is_visited == True: | |
| continue | |
| cost = romania_map[now.name][loc] | |
| node = Node(loc,now,staight_line_cost(loc)) | |
| q.push(node) | |
| q.sort_by_function(cost_return); | |
| #start = input("Start from?") | |
| #dest = input("Destination?") | |
| bfs_travel("Arad") | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| romania_map = { | |
| "Arad": {"Zerind": 75, "Timisoara": 118, "Sibiu": 140}, | |
| "Zerind": {"Arad": 75, "Oradea": 71}, | |
| "Oradea": {"Zerind": 71, "Sibiu": 151}, | |
| "Timisoara": {"Arad": 118, "Lugoj": 111}, | |
| "Lugoj": {"Timisoara": 111, "Mehadia":70}, | |
| "Mehadia": {"Lugoj": 70, "Dobreta": 75}, | |
| "Dobreta": {"Mehadia":75, "Craiova":120}, | |
| "Craiova": {"Dobreta": 120, "RimnicuVilcea": 146, "Pitesi": 138}, | |
| "RimnicuVilcea": {"Craiova": 146, "Pitesi": 97, "Sibiu":80}, | |
| "Sibiu": {"Arad": 140, "Oradea":151, "RimnicuVilcea": 80, "Fagaras": 99}, | |
| "Fagaras": {"Sibiu": 99, "Bucharest":211}, | |
| "Pitesi": {"Bucharest": 101, "RimnicuVilcea": 97, "Craiova": 138}, | |
| "Bucharest": {"Pitesi": 101, "Fagaras": 211, "Giurgiu": 90, "Urziceni": 85}, | |
| "Giurgiu": {"Bucharest": 90}, | |
| "Urziceni": {"Bucharest": 85, "Hirsova": 98, "Vaslui": 142}, | |
| "Hirsova": {"Urziceni": 98, "Eforie": 86}, | |
| "Eforie": {"Hirsova": 86}, | |
| "Vaslui": {"Urziceni": 142, "Iasi": 92}, | |
| "Iasi": {"Vaslui": 92, "Neamt": 87}, | |
| "Neamt": {"Iasi": 87} | |
| } | |
| class Node: | |
| def path_cost(self,cost): | |
| if self.prev != None: | |
| return self.prev.cost + cost | |
| else: | |
| return 0 | |
| def __init__(self,name,prev,cost): | |
| self.name = name | |
| self.prev = prev | |
| self.cost = self.path_cost(cost) | |
| def is_equal(self,other_node): | |
| if self.name == other_node.name: | |
| return True | |
| else: | |
| return False | |
| class myQue: | |
| def __init__(self,innerList = []): | |
| self.innerList = innerList | |
| def push(self,value): | |
| self.innerList.append(value) | |
| def pop(self): | |
| return self.innerList.pop(0) | |
| def get(self): | |
| return list(self.innerList) | |
| def empty(self): | |
| if len(self.innerList)==0: | |
| return True | |
| else: | |
| return False | |
| def first(self): | |
| return self.innerList[0] | |
| def sort_by_function(self,func): | |
| #print("B: ",end="") | |
| #for i in self.innerList: | |
| # print(i.cost,end=",") | |
| #print(); | |
| self.innerList = sorted(self.innerList,key = func) | |
| #print("A: ",end="") | |
| #for i in self.innerList: | |
| # print(i.cost,end=",") | |
| #print(); | |
| def bfs_travel(start,dest): | |
| def cost_return(x): | |
| return x.cost | |
| if start not in romania_map or dest not in romania_map: | |
| print("Invalid start or dest") | |
| else: | |
| visited = [] | |
| q = myQue() | |
| node = Node(start,None,0) | |
| q.push(node) | |
| while q.empty != True: | |
| now = q.pop() | |
| if now.name == dest: | |
| print(now.cost) | |
| path = [now.name,] | |
| while now.prev != None: | |
| path.append(now.prev.name) | |
| now = now.prev | |
| print(list(reversed(path))) | |
| break | |
| visited.append(now) | |
| fringe = list(romania_map[now.name].keys()) | |
| for loc in fringe: | |
| is_visited = False | |
| for v in visited: | |
| if loc == v.name: | |
| is_visited = True | |
| if is_visited == True: | |
| continue | |
| cost = romania_map[now.name][loc] | |
| node = Node(loc,now,cost) | |
| q.push(node) | |
| q.sort_by_function(cost_return); | |
| #start = input("Start from?") | |
| #dest = input("Destination?") | |
| bfs_travel("Arad","Bucharest") | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
hi sir, can you help me explain the 'step by step' code using A* & GBFS, I'm a newbie and I'm pretty bad.
if possible contact me by email: mrdoyel.5802@gmail.com