Tengo un gráfico como este:

# graph table
graph = {}
graph['start'] = {}
graph['start']['a'] = 5
graph['start']['b'] = 2

graph['a'] = {}
graph['a']['c'] = 4
graph['a']['d'] = 2 

graph['b'] = {}
graph['b']['a'] = 8
graph['b']['d'] = 7

graph['c'] = {}
graph['c']['d'] = 6
graph['c']['finish'] = 3

graph['d'] = {}
graph['d']['finish'] = 1
graph['finish'] = {}

enter image description here

Y estoy tratando de encontrar la forma más rápida de S a F.

En el primer ejemplo del libro, solo se conectó un borde a un nodo, en este ejemplo, por ejemplo, el nodo D tiene 3 pesos y se usó una tabla cost:

costs = {}
infinity = float('inf')
costs['a'] = 5
costs['b'] = 2
costs['c'] = 4 
costs['d'] = # there is 3 costs to node D, which one to select?
costs['finish'] = infinity

Y una mesa para padres:

parents = {}
parents['a'] = 'start' # why not start and b since both `S` and `B` can be `A` nodes parent?
parents['b'] = 'start'
parents['c'] = 'a'
parents['d'] =  # node D can have 3 parents
parents['finish'] = None

Pero esto también funciona, por obras quiero decir que no se arroja ningún error, así que ¿solo tengo que nombrar a los padres del primer nodo S?

parents = {}
parents['a'] = 'start' 
parents['b'] = 'start'
parents['finish'] = None

El código:

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float('inf')
    lowest_cost_node = None

    for node in costs:
        cost = costs[node]

        if cost < lowest_cost and node not in processed:
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node



node = find_lowest_cost_node(costs)

while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  for n in neighbors.keys():
      new_cost = cost + neighbors[n]
      if costs[n] > new_cost:
          costs[n] = new_cost
          parents[n] = node
  processed.append(node)
  node = find_lowest_cost_node(costs)


def find_path(parents, finish):
  path = []
  node = finish
  while node:
      path.insert(0, node)
      if parents.__contains__(node):
          node = parents[node]
      else:
          node = None
  return path


path = find_path(parents, 'finish')
distance = costs['finish']

print(f'Path is: {path}')
print(f'Distance from start to finish is: {distance}')

Entiendo:

Path is: ['finish']
Distance from start to finish is: inf

¿Dónde está mi error y cómo debo agregar cost y parent a un nodo que se puede visitar desde más de 1 nodo?

Editar Creo que este no es el mejor enfoque para este problema, las mejores soluciones / recomendaciones en la práctica son bienvenidas.

2
Jonas Palačionis 20 ene. 2021 a las 17:31

1 respuesta

La mejor respuesta

No es necesario que inicialice la tabla de costos con más de costs['start'] = 0 o el diccionario principal con más de parents = {}. ¡Eso es lo que su algoritmo creará para usted!

El único otro cambio que necesita hacer es en su bucle while. Solo necesita verificar si el nuevo nodo ya se ha detectado antes. Si es así, verificamos si la nueva ruta es más corta y la actualizamos según sea necesario; si no, establecemos el nuevo camino.

while node is not None:
  cost = costs[node]
  neighbors = graph[node]
  for n in neighbors.keys():
      new_cost = cost + neighbors[n]
      if n in costs:
          if costs[n] > new_cost:
              costs[n] = new_cost
              parents[n] = node
      else:
          costs[n] = new_cost
          parents[n] = node
  processed.append(node)
  node = find_lowest_cost_node(costs)

Creo que hay formas mucho más ordenadas de lidiar con los gráficos, pero este es el cambio mínimo necesario para que su código funcione como se requiere. ¡Espero que sea de ayuda!

2
Jerry 20 ene. 2021 a las 15:28