Castores y madrigueras

Question

En el diagrama de abajo, a, B, C, D, E, F son beaver las logias y los segmentos en azul y rojo son las madrigueras de los que se conectan a las logias. Los puntos marcados con las letras G a S son puntos de cruce donde los castores se puede cambiar de pista. En el hotel hay 3 castores que quieren llegar a sus casas de campo en B, C y D. Obviamente cada castor puede seguir varios caminos alternativos para llegar a su lodge. De acuerdo con el número de caminos diferentes que cada castor puede seguir, vamos a recompensar a cada uno con su correspondiente número de manzanas. Cada ruta se compone de varias madrigueras entre los puntos de cruce (las logias de la a a la F también pueden ser puntos de cruce). Un castor puede elegir su madriguera sólo si su terminando de cruzar el punto más cercano a su destino lodge, con respecto a su punto de origen. Cuántas manzanas cada uno de castor, de la ganancia?Las logias y madrigueras

Es algo muy confuso; casi no puedo entender los términos. Alguien puede ayudar?

Por ejemplo, de la a a la B, creo que es AB, AOB, ANOB, AOPB, ANOPB.

Answer 1

Lo que estoy tratando de resolver uno de los castores, sólo para ver si he resuelto :)

Con todo, es un gráfico de recorrido problema que se puede resolver con retroceso. Yo creo que el problema es NP completo, por lo que necesitará un algoritmo para contarlos. He implementado el gráfico y una búsqueda en profundidad el algoritmo en python. Resulta que yo estaba subestimando mucho!

• Beaver 1: $\to$B consigue 5 manzanas
• Beaver 2: $\to$C tiene 41 manzanas
• Beaver 3: $\to$D obtiene 121 manzanas ¡A disfrutar!

Python simulación

Importación de paquetes requeridos

import numpy as np

Definir el gráfico

nodes = {
  "A": [-np.sqrt(3)/2, -1/2], "B": [0,-1], "C": [np.sqrt(3)/2, -1/2], "D": [np.sqrt(3)/2, 1/2], "E": [0,1],
  "F": [-np.sqrt(3)/2, 1/2], "S": [1/np.sqrt(3),0], "J": [np.sqrt(3)/4, 1/4], "L": [-np.sqrt(3)/4, 1/4],
  "I": [1/(2*np.sqrt(3)) , 1/2], "K": [-np.sqrt(3)/4 , 1/4], "G": [-1/(2*np.sqrt(3)), 1/2], "H": [0, 1/2],
  "Q": [1/(2*np.sqrt(3)), -1/2], "N": [-np.sqrt(3)/4, -1/4], "M": [-1/np.sqrt(3),0], "P": [0, -1/2],
  "R": [np.sqrt(3)/4, -1/4], "O": [-1/(2*np.sqrt(3)), -1/2], "K": [0,0],
}

edges = [
  ["A","B"], ["A","O"], ["A",'N'], ['A','M'], ['A','F'], ['B','O'],
  ['B','P'], ['B','Q'], ['B','C'], ['C','Q'], ['C','R'], ['C','S'],
  ['C','D'], ['D','E'], ['D','S'], ['D','J'], ['D','I'], ['D','E'],
  ['E','I'], ['E','H'], ['E','G'], ['E','F'], ['F','G'], ['F','L'],
  ['F','M'], ['M','N'], ['N','O'], ['O','P'], ['P','Q'], ['Q','R'],
  ['R','S'], ['S','J'], ['J','I'], ['I','H'], ['H','G'], ['G','L'],
  ['L','M'], ['K','R'],  ['K','J'], ['K','H'], ['K','L'], ['K','N'],
  ['K','P'], 
]

Para probar, aquí es un dibujo de la gráfica

for edge in edges:
  ls = nodes[edge[0]]
  le = nodes[edge[1]]
  plt.plot([ls[0], le[0]], [ls[1],le[1]], color="blue")

for p in nodes:
  l = nodes[p]

  plt.text(l[0],l[1],p)
  plt.scatter(l[0], l[1], color="red")

Funciones auxiliares. El primero se presenta el otro nodo en un borde; la segunda se calcula la distancia entre dos nodos.

def getOther(node, edge):
  a,b = edge
  if node == a:
    return b
  else:
    return a

def getDistance(node1, node2):
  x1,y1 = nodes[node1]
  x2,y2 = nodes[node2]

  return np.sqrt((x1 - x2)**2 + (y1- y2)**2)

La profundidad de primer gráfico de búsqueda.

def getPaths(source, destination):
  pathsout = []
  stack = [source]
  while stack:
    path = stack.pop()
    node = path[-1]
    if node == destination:
      pathsout.append(path)

    dist = getDistance(node, destination)
    candidates = [getOther(node, edge) for edge in edges if node in edge]
    for c in candidates:
      if getDistance(c, destination) <= dist:
        stack.append(path + c )

  return set(pathsout) # transform into set to remove duplicates

Ejecutar la simulación

print(f"n. paths from A to B: {len(getPaths('A','B'))}")
print(f"n. paths from A to C: {len(getPaths('A','C'))}")
print(f"n. paths from A to D: {len(getPaths('A','D'))}")

Resultados:

# paths from A to B: 5
# paths from A to C: 41
# paths from A to D: 121

Rutas

De impresión son los caminos de los castores pueden seguir

print(f"n. paths from A to B: {len(getPaths('A','B'))}")
print(' '.join(getPaths('A','B')) + '\n\n')
print(f"n. paths from A to C: {len(getPaths('A','C'))}")
print(' '.join(getPaths('A','C')) + '\n\n')
print(f"n. paths from A to D: {len(getPaths('A','D'))}")
print(' '.join(getPaths('A','D')))

Resultados:

n. paths from A to B: 5
AOPB ANOPB ANOB AOB AB


n. paths from A to C: 41
ANKJSC ANOPQC AOBPQC AOBQRC ANOBQRC AMNOPQC AMNKJSC AOPQRC ANOPQRC AMNKPQC AMNKJSRC AOBC AMNOBC ABPQRC AMNKPQRC AMLKRC AMNKRC ANOBQC AOBQC ANKRC AOPQC ABQC AMNOBQC AMLKJSC AMNOPQRC ANOBPQRC ANKJSRC AMLKPQC AMLKJSRC AMNOBQRC AMNOBPQC ANOBC ABC AOBPQRC ANKPQRC ANOBPQC ABPQC AMLKPQRC AMNOBPQRC ANKPQC ABQRC


n. paths from A to D: 121
AOPKHID ABOPKHID AMNKRSD ABONKHID AMLGHID AFGHID AFMLGEID AMNKHID AONKRSJD AFMLGHID AFMLKHIJD AFGEHID AOPQCRSJD AFLGEID ABONKRSJD AMLKHIJD ABONKJD ABPQCSJD AMLKJD AFMLKHID AFLKJD ABOPKHIJD ABQCSD ABCSD AMLKRSD AOPKRSJD ABCD AONKRSD AFMNKRSD AFLGEIJD ABPKRSJD AMLGEHIJD AFGED ABOPQRSJD ABQCSJD AOPQCRSD AFGEHIJD ANKHIJD ABOPKRSD AOPQRSD AFMLGEHID AMLGED AMNKRSJD ABQRSD AMLKHID AFMLKJD AFLGED ANKRSD AFLKHIJD AFMLGED AONKHID ABPKJD AMLGEIJD AFGHIJD AMLKRSJD AFLGEHID ABPKHIJD ABPQCRSJD AMLGEHID AFEIJD ABONKHIJD ABONKRSD ANKJD AOPKHIJD ABPQCRSD AFGEIJD AFEHID AMLGEID ABPQCSD ABPQCD ABQRSJD AMLGHIJD ABPKHID ABCRSD ABPQRSJD ABCRSJD ABQCRSJD ABOPQCSJD AFMLGEIJD ABOPKJD AMNKHIJD AONKHIJD AMNKJD AFEID AFLGHID AFLKRSJD ANKHID ANKRSJD AFMNKJD AFED ABQCRSD ABOPQCRSJD ABOPQRSD AOPKRSD AFGEID AFLGHIJD ABQCD AOPQCSD AFMLKRSD AONKJD AFEHIJD ABCSJD AFMNKHID ABPKRSD AOPQCD AOPKJD ABOPKRSJD AFMNKRSJD ABOPQCD AFMLKRSJD AFMLGEHIJD ABPQRSD AFLGEHIJD AFMNKHIJD ABOPQCRSD AFMLGHIJD AOPQRSJD AOPQCSJD AFLKHID ABOPQCSD AFLKRSD