Я немного новичок, когда дело доходит до python, и я пытаюсь реализовать алгоритм поиска Astar, и я сталкиваюсь с проблемами, когда дело доходит до обратного отслеживания моего поиска и изучения неисследованных узлов. Отслеживание с возвратом сработало для меня только один раз, и я понятия не имею, почему он не продолжает исследовать неисследованные узлы.
Пока в алгоритме: Узел (соседи):: 1 (2,12,1363) -> 2 ( 1,13,48) -> 13 (2): 2 (1,13,48) -> 48 (2)
Таким образом, алгоритм никогда не смотрит на других соседей узла 1, но он действительно смотрел для других соседей узла 2 я понятия не имею, почему. Буду признателен за любую помощь! Заранее спасибо!
Функция, в которой, похоже, возникают мои проблемы:
def distance(startnode, endnode, graphone):
"""computes the distance between two vertices"""
startNeighbors = startnode.getNeighbors(graphone)
startWeights = startnode.getWeights()
startWeights.sort()
index = startWeights.index(min(startWeights))
dist.add(startWeights[index])
endIndex = endnode.index
path.add(startnode.index)
startNeighborsIndex = []
for number in startNeighbors:
startNeighborsIndex.append(number.index)
if endIndex in startNeighborsIndex:
return path.add(endnode.index)
elif startNeighborsIndex[index] in path and len(startNeighborsIndex) > 1: #Backtrack
i = 0
for item in startNeighborsIndex:
if item not in path:
return distance(graphone.getVertex(startNeighborsIndex[i]),endnode,graphone)
i = i + 1
# if index + 1 < len(startNeighbors)-1:
# return distance(graph.getVertex(startNeighbors[index+1]),n2,graph)
# elif index + 1 == len(startNeighbors):
# return distance(graph.getVertex(startNeighbors[index]),n2,graph)
# elif index + 1 > len(startNeighbors)-1:
# return distance(graph.getVertex(startNeighbors[index-1]),n2,graph)
# else:
# return distance(graph.getVertex(startNeighbors[len(startNeighbors)-1]),n2,graph)
else:
return distance(graphone.getVertex(startNeighborsIndex[index]),endnode,graphone)
Полный код:
from abc import ABCMeta, abstractmethod
from heapq import heappush, heappop, heapify
import fileinput
import math
Infinite = float('inf')
dist = set()
path = set()
def __main__():
graphone = readGraph('data/USA-road-d.NY.gr')
co = readCoordinates('data/USA-road-d.NY.co')
startNode = graphone.getVertex(1)
endNode = graphone.getVertex(3)
costFunc = distance(startNode,endNode,graphone)
# find_path(startNode,endNode,neighbors_fnct=startNode.neighbors(graphone),heuristic_cost_estimate_fnct=distance(startNode,endNode,graphone),distance_between_fnct=distance(startNode,endNode,graphone))
find_path(startNode,endNode,neighbors_fnct=startNode.neighbors(graphone),heuristic_cost_estimate_fnct=distance(graphone),distance_between_fnct=distance(graphone))
def readGraph(filePath):
n_vertices = 0
for line in fileinput.input([filePath]):
words = line.split(" ")
if (words[0] == "p"):
n_vertices = int(words[2])
graph = Graph(n_vertices)
for line in fileinput.input([filePath]):
words = line.split(" ")
if (words[0] == "a"):
graph._addVertex(int(words[1]), int(words[2]), float(words[3]))
return graph
# read coordinates data
def readCoordinates(filepath):
# Start to count from 1
coordinates = [None]
for line in fileinput.input([filepath]):
words = line.split(" ")
if (words[0] == "v"):
coordinates.append([float(words[2]), float(words[3])])
return coordinates
class Vertex:
# Initialization of a vertex, given a neighbor and the corresponding weight
# Each vertex contains a list of neighbors and corresponding weights
def __init__(self, i, neighbor_index, weight):
self.index = i
self.neighbors = [neighbor_index]
self.weights = [weight]
def getNeighbors(self,graphone):
neighborList = self.neighbors
neighbors = []
for number in neighborList:
neighbors.append(graphone.getVertex(number))
return neighbors
def getWeights(self):
return self.weights
# Add a neighbor with corresponding weight to the vertex
def _addNeighbor(self, neighbor_index, weight):
self.neighbors.append(neighbor_index)
self.weights.append(weight)
# Graph data structure
class Graph:
# Initializes a graph with n_vertices nodes
# The graph contains a list of vertices
def __init__(self, n_vertices):
self.vertices = [None] * (n_vertices+1)
self.num_vertices = n_vertices
# Returns the i'th node
def getVertex(self, i): #Recursion error, maximum depth reached
if ((i > self.num_vertices) | (i <= 0)):
raise ValueError(f'index {i} is out of bounds')
else:
return self.vertices[i]
# Adds a new vertex to the graph
def _addVertex(self, vertex_index, neighor_index, distance):
if (self.vertices[vertex_index] == None):
# Construct new vertex
self.vertices[vertex_index] = Vertex(vertex_index, neighor_index, distance)
else:
# Vertex already in graph but other neighbor, add extra edge
self.vertices[vertex_index]._addNeighbor(neighor_index, distance)
def getTrueDistance(self,startNode, endNode):
startIndex = startNode.index
endIndex = endNode.index
def distance(startnode, endnode, graphone):
"""computes the distance between two vertices"""
startNeighbors = startnode.getNeighbors(graphone)
startWeights = startnode.getWeights()
startWeights.sort()
index = startWeights.index(min(startWeights))
dist.add(startWeights[index])
endIndex = endnode.index
path.add(startnode.index)
startNeighborsIndex = []
for number in startNeighbors:
startNeighborsIndex.append(number.index)
if endIndex in startNeighborsIndex:
return path.add(endnode.index)
elif startNeighborsIndex[index] in path and len(startNeighborsIndex) > 1: #Backtrack
i = 0
for item in startNeighborsIndex:
if item not in path:
return distance(graphone.getVertex(startNeighborsIndex[i]),endnode,graphone)
i = i + 1
# if index + 1 < len(startNeighbors)-1:
# return distance(graph.getVertex(startNeighbors[index+1]),n2,graph)
# elif index + 1 == len(startNeighbors):
# return distance(graph.getVertex(startNeighbors[index]),n2,graph)
# elif index + 1 > len(startNeighbors)-1:
# return distance(graph.getVertex(startNeighbors[index-1]),n2,graph)
# else:
# return distance(graph.getVertex(startNeighbors[len(startNeighbors)-1]),n2,graph)
else:
return distance(graphone.getVertex(startNeighborsIndex[index]),endnode,graphone)
class AStar:
__metaclass__ = ABCMeta
__slots__ = ()
class SearchNode:
__slots__ = ('data', 'gscore', 'fscore',
'closed', 'came_from', 'out_openset')
def __init__(self, data, gscore=Infinite, fscore=Infinite):
self.data = data
self.gscore = gscore
self.fscore = fscore
self.closed = False
self.out_openset = True
self.came_from = None
def __lt__(self, b):
return self.fscore < b.fscore
class SearchNodeDict(dict):
def __missing__(self, k):
v = AStar.SearchNode(k)
self.__setitem__(k, v)
return v
@abstractmethod
def heuristic_cost_estimate(self, current, goal):
"""Computes the estimated (rough) distance between a node and the goal, this method must be implemented in a subclass. The second parameter is always the goal."""
raise NotImplementedError
@abstractmethod
def distance_between(self, n1, n2):
"""Gives the real distance between two adjacent nodes n1 and n2 (i.e n2 belongs to the list of n1's neighbors).
n2 is guaranteed to belong to the list returned by the call to neighbors(n1).
This method must be implemented in a subclass."""
raise NotImplementedError
@abstractmethod
def neighbors(self, current):
"""For a given node, returns (or yields) the list of its neighbors. this method must be implemented in a subclass"""
vertex = Vertex(node)
raise NotImplementedError
def is_goal_reached(self, current, goal):
""" returns true when we can consider that 'current' is the goal"""
return current == goal
def reconstruct_path(self, last, reversePath=False):
def _gen():
current = last
while current:
yield current.data
current = current.came_from
if reversePath:
return _gen()
else:
return reversed(list(_gen()))
def astar(self, start, goal, reversePath=False):
# def astar(start,goal,reversePath=False):
if self.is_goal_reached(start, goal):
return [start]
searchNodes = AStar.SearchNodeDict()
startNode = searchNodes[start] = AStar.SearchNode(
start, gscore=.0, fscore=self.heuristic_cost_estimate(start,goal))
openSet = []
heappush(openSet, startNode)
while openSet:
current = heappop(openSet)
if self.is_goal_reached(current.data, goal):
return self.reconstruct_path(current, reversePath)
current.out_openset = True
current.closed = True
#for neighbor in map(lambda n: searchNodes[n], self.neighbors[current.data]):
for neighbor in map(lambda n: searchNodes[n], self.neighbors(current.data)):
if neighbor.closed:
continue
tentative_gscore = current.gscore + \
self.distance_between(current.data, neighbor.data)
if tentative_gscore >= neighbor.gscore:
continue
neighbor.came_from = current
neighbor.gscore = tentative_gscore
neighbor.fscore = tentative_gscore + \
self.heuristic_cost_estimate(neighbor.data, goal)
if neighbor.out_openset:
neighbor.out_openset = False
heappush(openSet, neighbor)
else:
heapify(openSet)
#return self
return None
def find_path(start, goal, neighbors_fnct, reversePath=False, heuristic_cost_estimate_fnct=lambda a, b: Infinite, distance_between_fnct=lambda a, b: 1.0, is_goal_reached_fnct=lambda a, b: a == b):
"""A non-class version of the path finding algorithm"""
class FindPath(AStar):
def heuristic_cost_estimate(self, current, goal):
return heuristic_cost_estimate_fnct(current, goal)
def distance_between(self, n1, n2):
return distance_between_fnct(n1, n2)
def neighbors(self, node):
return neighbors_fnct(node)
def is_goal_reached(self, current, goal):
return is_goal_reached_fnct(current, goal)
return FindPath().astar(start, goal, reversePath)
if __name__ == '__main__':
__main__()