Блог

Мне нужно рассчитать общую стоимость пути по следующему алгоритму

Этот код находит кратчайший или оптимальный путь между двумя узлами. Этот код написан не мной, на самом деле я пытаюсь изучить информированные алгоритмы поиска и то, как они работают. Ваш интерес будет оценен по достоинству.

Я также приложил изображение графика с фактическими значениями и эвристическими значениями, которые используются в этом коде

 from collections import deque


class Graph:

    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

    def get_neighbors(self, v):
        return self.adjacency_list[v]

    # heuristic function with values for all nodes
    def h(self, n):
        H = {
            'oradea': 380,
            'zerind': 374,
            'sibiu': 253,
            'arad': 366,
            'timisoara': 329,
            'lugoj': 244,
            'mehadia': 241,
            'dobreta': 242,
            'craiova': 160,
            'rimnicu vilcea': 193,
            'pitesti': 10,
            'fagaras': 176,
            'bucharest': 0,
            'giurgiu': 77,
            'urziceni': 80,
            'vaslui': 199,
            'lasi': 226,
            'neamt': 234,
            'hirsova': 151,
            'eforie': 161
        }

        return H[n]

    def a_star_algorithm(self, start_node, stop_node):
        # open_list is a list of nodes which have been visited, but who's neighbors
        # haven't all been inspected, starts off with the start node
        # closed_list is a list of nodes which have been visited
        # and who's neighbors have been inspected
        open_list = set([start_node])
        closed_list = set([])

        # g contains current distances from start_node to all other nodes
        # the default value (if it's not found in the map) is  infinity
        g = {}

        g[start_node] = 0

        # parents contains an adjacency map of all nodes
        parents = {}
        parents[start_node] = start_node

        while len(open_list) > 0:
            n = None

            # find a node with the lowest value of f() - evaluation function
            for v in open_list:
                if n == None or g[v]   self.h(v) < g[n]   self.h(n):
                    n = v;

            if n == None:
                print('Path does not exist!')
                return None

            # if the current node is the stop_node
            # then we begin reconstruction the path from it to the start_node
            if n == stop_node:
                reconst_path = []

                while parents[n] != n:
                    reconst_path.append(n)
                    n = parents[n]

                reconst_path.append(start_node)

                reconst_path.reverse()

                print('Path found: {}'.format(reconst_path))
                return reconst_path

            # for all neighbors of the current node do
            for (m, weight) in self.get_neighbors(n):
                # if the current node isn't in both open_list and closed_list
                # add it to open_list and note n as it's parent
                if m not in open_list and m not in closed_list:
                    open_list.add(m)
                    parents[m] = n
                    g[m] = g[n]   weight

                # otherwise, check if it's quicker to first visit n, then m
                # and if it is, update parent data and g data
                # and if the node was in the closed_list, move it to open_list
                else:
                    if g[m] > g[n]   weight:
                        g[m] = g[n]   weight
                        parents[m] = n

                        if m in closed_list:
                            closed_list.remove(m)
                            open_list.add(m)

            # remove n from the open_list, and add it to closed_list
            # because all of his neighbors were inspected
            open_list.remove(n)
            closed_list.add(n)

        print('Path does not exist!')
        return None


# adjacency list (or rather map)
adjacency_list = {
    'oradea': [('zerind', 71), ('sibiu', 151)],
    'zerind': [('oradea', 71), ('arad', 75)],
    'sibiu': [('oradea', 151), ('arad', 140), ('fagaras', 99), ('rimnicu vilcea', 80)],
    'arad': [('zerind', 71), ('timisoara', 118), ('sibiu', 140)],
    'timisoara': [('arad', 118), ('lugoj', 111)],
    'lugoj': [('timisoara', 111), ('mehadia', 70)],
    'mehadia': [('lugoj', 70), ('dobreta', 75)],
    'dobreta': [('mehadia', 75), ('craiova', 120)],
    'craiova': [('dobreta', 120), ('pitesti', 138), ('rimnicu vilcea', 148)],
    'rimnicu vilcea': [('craiova', 148), ('sibiu', 80), ('pitesti', 97)],
    'pitesti': [('craiova', 138), ('rimnicu vilcea', 97), ('bucharest', 101)],
    'fagaras': [('sibiu', 99), ('bucharest', 211)],
    'bucharest': [('pitesti', 101), ('fagaras', 211), ('giurgiu', 90), ('urziceni', 85)],
    'giurgiu': [('bucharest', 90)],
    'urziceni': [('bucharest', 85), ('hirsova', 98), ('vaslui', 142)],
    'vaslui': [('urziceni', 142), ('lasi', 92)],
    'lasi': [('vaslui', 92), ('neamt', 87)],
    'neamt': [('lasi', 87)],
    'hirsova': [('urziceni', 98), ('eforie', 86)],
    'eforie': [('hirsova', 86)]
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm('oradea', 'pitesti')
 

Информированный поиск-Карта

Мне нужно рассчитать общую стоимость пути по следующему алгоритму

Измените этот код

             while parents[n] != n:
                reconst_path.append(n)
                n = parents[n]
 

Для

             while parents[n] != n:
                reconst_path.append(n)
                next = parents[n]
                total_cost = total_cost   cost_between( next, n )
                n = next
 

Вам нужно будет закодировать cost_between, чтобы найти два узла в графике и извлечь стоимость.