该程序使用*算法查找从起点城市(海得拉巴)到终点城市(伊斯兰堡)的最短路径
此python程序工作正常,但它错误地复制了数据,如 可能被探索的城市:[“海得拉巴”、“卡拉奇”、“奎达”、“奎达”、“苏库尔”、“木尔坦”、“拉合尔”、“巴哈瓦尔布尔”、“巴哈瓦尔布尔”、“白沙瓦”、“伊斯兰堡” 可能的城市数量:11个
Q2。我想做的另一件事是跟踪星型算法所采取的步骤,并将其显示为输出。
输入
所以在海得拉巴.txt文件中,我添加了两个城市之间的路径距离 例如
Hyderabad,Quetta, 160`
Hyderabad,Karachi, 60
Hyderabad,Sukkur, 60
Karachi,Quetta, 80
Quetta,Peshawar, 120
Peshawar,Islamabad, 40
Sukkur,Multan, 80
Sukkur,Bahawalpur, 160
Multan,Bahawalpur, 60
Multan,Lahore, 80
Bahawalpur,Islamabad, 160
Lahore,Islamabad, 100
在hyderabad_sld.txt文件中,我添加了启发式
Hyderabad, 200
Islamabad, 0
Quetta, 100
Karachi, 140
Sukkur, 220
Multan, 140
Bahawalpur, 80
Lahore, 20
Peshawar, 50
import heapq
class priorityQueue:
def __init__(self):
self.cities = []
def push(self, city, cost):
heapq.heappush(self.cities, (cost, city))
def pop(self):
return heapq.heappop(self.cities)[1]
def isEmpty(self):
if (self.cities == []):
return True
else:
return False
def check(self):
print(self.cities)
class ctNode:
def __init__(self, city, distance):
self.city = str(city)
self.distance = str(distance)
hyderabad = {}
def makedict():
file = open("Hyderabad.txt", 'r')
for string in file:
line = string.split(',')
ct1 = line[0]
ct2 = line[1]
dist = int(line[2])
hyderabad.setdefault(ct1, []).append(ctNode(ct2, dist))
hyderabad.setdefault(ct2, []).append(ctNode(ct1, dist))
def makeheuristicdict():
h = {}
with open("hyderabad_sld.txt", 'r') as file:
for line in file:
line = line.strip().split(",")
node = line[0].strip()
sld = int(line[1].strip())
h[node] = sld
return h
def heuristic(node,values):
return values[node]
def astar(start, end):
path = {}
distance = {}
q = priorityQueue()
h = makeheuristicdict()
q.push(start, 0)
distance[start] = 0
path[start] = None
expandedList = []
while (q.isEmpty() == False):
current = q.pop()
expandedList.append(current)
if (current == end):
break
for new in hyderabad[current]:
g_cost = distance[current] + int(new.distance)
# print(new.city, new.distance, "now : " + str(distance[current]), g_cost)
if (new.city not in distance or g_cost < distance[new.city]):
distance[new.city] = g_cost
f_cost = g_cost + heuristic(new.city, h)
q.push(new.city, f_cost)
path[new.city] = current
printoutput(start, end, path, distance, expandedList)
def printoutput(start, end, path, distance, expandedlist):
finalpath = []
i = end
while (path.get(i) != None):
finalpath.append(i)
i = path[i]
finalpath.append(start)
finalpath.reverse()
print("A star search problem >> Islamabad")
print("\tHyderabad => Islamabad")
print("=======================================================")
print("Cities that maybe explored \t\t: " + str(expandedlist))
print("number of possible cities \t\t: " + str(len(expandedlist)))
print("=======================================================")
print("City with shortest distance \t: " + str(finalpath))
print("Number of cities passed \t\t\t: " + str(len(finalpath)))
print("Total distance \t\t\t\t\t\t: " + str(distance[end]))
def main():
src = "Hyderabad"
dst = "Islamabad"
makedict()
astar(src, dst)
if __name__ == "__main__":
main()
目前没有回答
相关问题 更多 >
编程相关推荐