探索未探索节点的问题Astar - Python

Question

当涉及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__()

Answer 1

我不知道python，但是在A*算法中，当您向打开的列表中添加一个节点时，将它的“父”设置为当前节点，这是一种回溯方法。因此，当您向打开的列表中添加节点时，将其父节点设置为当前节点，该节点是从该节点添加的节点。然后，当您将节点添加到打开列表中并且打开列表中已经存在一个节点时，将其父节点替换为当前节点。

如果你还没有看到这个视频，你应该看：https://www.youtube.com/watch?v=-L-WgKMFuhE&t=445s