统一成本搜索根据成本查找从源节点到目标节点的最短路径。我曾尝试使用 ucs 实现双向搜索。但是，我在正确设置终止条件方面遇到了麻烦。我尝试实现终止条件，因为当向前和向后搜索都访问了一个公共节点时，该函数返回以该节点为相交节点的路径并形成一条路径。此解决方案不会返回所有源节点和目标节点组合的最短路径。
Here is the visualization of the graph on which I am trying to implement the bidirectional UCS
python中的代码实现
# import required packages
from collections import defaultdict
from queue import PriorityQueue
class Graph :
"""
Class to create the graph data structures and implement the supporting functions
Class Variables :
1. edges
2. weights
Class Functions :
""descriptions inside function definitions""
1. addEdge(node1,node2,cost)
2. neighbors(node)
3. get_cost(from_node,to_node)
"""
def __init__(self):
"""
Function to initialize class variables
edges : a dictionary that holds the adjacent nodes for a node. eg : {"A" : {"B","C"}}
weights : a dictinary that holds cost of an edge. eg : {(node1,node2) : cost}
"""
try :
self.edges = defaultdict(set)
self.weights = defaultdict(int)
except Exception as e :
print("Exception occured due to : {0}".format(e))
def addEdge(self,node1,cost):
"""
Function to populate the class variables,edges and weights
Parameters :
node1,node2 : nodes between which an undirected edge is present (node1 --- node2)
cost : cost/weight associated with the edge
Returns :
None
"""
try :
# check for non-negative edge weights
if cost > 0 :
# Add edge from node1 --> node2
self.edges[node1].add(node2)
self.weights[(node1,node2)] = cost
# Add edge from node2 --> node1 (as the edges are undirected)
self.edges[node2].add(node1)
self.weights[(node2,node1)] = cost
else :
print("Please enter non negative cost for the edge...")
except Exception as e :
print("Exception occured due to : {0}".format(e))
def neighbors(self,node):
"""
Function to return all the adjacent nodes of a node
Parameters :
node : node for which the adjacent nodes are to be returned
Returns :
adjacent nodes of a node
"""
try :
return self.edges[node]
except Exception as e :
print("Exception occured due to : {0}".format(e))
def get_cost(self,from_node,to_node):
"""
Function to return the cost/weight associated with an edge
Parameters :
from_node,to_node : nodes representing an edge
Returns :
cost/weight associated with the edge b/w from_node and to_node
"""
try :
return self.weights[(from_node,to_node)]
except Exception as e :
print("Exception occured due to : {0}".format(e))
class shortestPathSearch :
"""
Class to define functions for finding the shortest path between start and goal nodes
Class Variables :
1. graph : instance of the graph class through which populated graph and
other supporting functions defined on graph can be accessed
2. srcQ : frontier initialized as priority queue from the source node (for use in forward search)
3. goalQ : frontier initialized as priority queue from the goal node (for use in backward search)
4. srcVisited : initialized as a dictionary for holding visited node and its associated path cost (for use in forward search)
5. goalVisited : initialized as a dictionary for holding visited node and its associated path cost (for use in backward search)
6. srcPath : initialized as a list to hold the nodes in the optimal path from forward search
7. goalPath : initialized as a list to hold the nodes in the optimal path from backward search
Class Functions :
""descriptions inside function definitions""
1. uniformCostSearch(direction)
2. intersectingNode()
3. bidirectionalSearch(start,goal)
4. getPath(intersecting_node)
5. calculateCost(path)
"""
def __init__(self,graph) :
"""
Function to initialize class variables
Parameters :
graph : an instance of the Graph class
Returns :
None
"""
try :
self.graph = graph
# Initializing queues for forward and backward search
self.srcQ = PriorityQueue()
self.goalQ = PriorityQueue()
# Initializing data structures to hold visited nodes for source and goal nodes
self.srcVisited = dict()
self.goalVisited = dict()
# Initializing data structures to hold path for source and goal nodes
self.srcPath = []
self.goalPath = []
except Exception as e :
print("Exception occured due to : {0}".format(e))
def uniformCostSearch(self,direction = "F") :
"""
Function to find shortest path between two nodes using uniform cost search on the graph
Parameters :
direction : search direction - forward (F) or backward (B)
Returns :
None
"""
try :
# forward search from source node
if direction == "F" :
# Pop the cost,node and path from the queue
cost,node,self.srcPath = self.srcQ.get()
# If the node has been visited,and has a lower cost,bail
if node in self.srcVisited and self.srcVisited[node] < cost:
return
# add node to srcVisited if not in it,loop through its children,calculate cumulative cost and add to srcQ
if node not in self.srcVisited:
self.srcVisited[node] = cost
for i in self.graph.neighbors(node):
if i not in self.srcVisited:
total_cost = cost + self.graph.get_cost(node,i)
self.srcQ.put((total_cost,i,self.srcPath + [node]))
print(self.srcQ.queue)
# backward search from goal node
# While the goalQ isn't empty
else :
# Pop the cost,self.goalPath = self.goalQ.get()
# If the node has been visited,bail
if node in self.goalVisited and self.goalVisited[node] < cost:
return
# add node to srcVisited if not in it,calculate cumulative cost and add to srcQ
if node not in self.goalVisited:
self.goalVisited[node] = cost
for i in self.graph.neighbors(node):
if i not in self.goalVisited:
total_cost = cost + self.graph.get_cost(node,i)
self.goalQ.put((total_cost,self.goalPath + [node]))
print(self.goalQ.queue)
except Exception as e :
print("Exception occured due to : {0}".format(e))
def intersectingNode(self) :
"""
function to check for an intersecting node while searching from both the directions
Parameters :
None
Returns :
intersecting node if present else -1
"""
try :
for key in self.graph.edges :
if key in self.goalVisited and key in self.srcVisited :
return key
return -1
except Exception as e :
print("Exception occured due to : {0}".str(e))
def bidirectionalSearch(self,start,goal) :
"""
function to implement bidirectional search using ucs
Parameters :
start : start node
goal : goal node
Returns :
None
"""
try :
self.srcQ.put((0,self.srcPath))
self.goalQ.put((0,goal,self.goalPath))
while self.srcQ and self.goalQ:
self.uniformCostSearch()
self.uniformCostSearch("B")
intersecting_node = self.intersectingNode()
if intersecting_node != -1 :
print(f"Path exists between {start} and {goal}")
print(f"Intersection at : {intersecting_node}")
return intersecting_node
except Exception as e :
print("Exception occured due to : {0}".format(e))
def getPath(self,intersecting_node) :
"""
Function to form the path from forward search and backward search
Parameters :
intersecting_node : node at which both the searches met
Returns :
path : optimal path from source to goal nodes
"""
try :
# a condition is defined in order to avoid intersecting node appearing twice in the path
if intersecting_node in self.srcPath or intersecting_node in self.goalPath :
path = self.srcPath + self.goalPath[-1:]
else :
path = self.srcPath + list(intersecting_node) + self.goalPath[-1:]
return path
except Exception as e :
print("Exception occured due to : {0}".format(e))
def calculateCost(self,path) :
"""
Function to calculate cost of the optimal path from source to goal nodes
Parameters :
path : optimal path from source to goal node
Returns :
cost : cost calculated from the optimal path
"""
try :
# initialize a list that holds cost of the consecutive nodes in the path
cost = [0] * (len(path) - 1)
for i in range(len(path)) :
cost[i] = graph.weights[(path[i],path[i + 1])]
# once the cost is obtained b/w consecutive nodes,sum them and return
return sum(cost)
except Exception :
return sum(cost)
if __name__ == "__main__" :
"""
*** Main Function ***
"""
try :
# add edges and associated path costs to the graph
graph = Graph()
graph.addEdge("A","B",110)
graph.addEdge("A","C",132)
graph.addEdge("B","D",159)
graph.addEdge("B","G",59)
graph.addEdge("C","E",89)
graph.addEdge("C",120)
graph.addEdge("D","F",98)
graph.addEdge("D",108)
graph.addEdge("E",68)
graph.addEdge("E",102)
graph.addEdge("F",92)
# Define an instance of shortestPathSearch class
sp = shortestPathSearch(graph)
# ask the user to enter source ans goal nodes
source = input("Enter source : ")
goal = input("Enter goal : ")
# check if valid nodes are entered and call the search algorithm
if source in graph.edges and goal in graph.edges :
intersecting_node = sp.bidirectionalSearch(source,goal)
if (intersecting_node == -1) :
print(f"Path not found between {source} and {goal}")
else :
# get the path,calculate cost and identify nodes that are visited
path = sp.getPath(intersecting_node)
cost = sp.calculateCost(path)
visited = sorted(set(list(sp.srcVisited.keys()) + list(sp.goalVisited.keys())))
# print
print(f"path : {path}")
print(f"cost : {cost}")
print(f"visited : {visited}")
print(f"No of nodes visited : {len(visited)}")
else :
print("Please check if you have entered valid source and goal nodes")
except Exception as e :
print("Exception occured due to : {0}".format(e))
对于给定的图形，虽然此代码适用于大多数情况，但不适用于特定情况，例如距离（E，G）。而最短路径是直接边，E -> G : 102，输出为
Path exists between E and G
Intersection at : F
path : ['E','F','G']
cost : 160
visited : ['B','C','E','G']
No of nodes visited : 5
如何使终止条件正确？