Encontrar el camino más largo en un juego de Settlers of Catan algorítmicamente

Question

Escribo un clon de Settlers of Catan para una clase. Una de las funciones de crédito adicionales es determinar automáticamente qué jugador tiene el camino más largo. Lo he pensado, y parece que una pequeña variación en la búsqueda en profundidad podría funcionar, pero estoy teniendo problemas para averiguar qué hacer con la detección de ciclos, cómo manejar la unión de las dos redes de carreteras iniciales de un jugador, y algunas otras minucias. ¿Cómo podría hacer esto algorítmicamente?

Para quienes no estén familiarizados con el juego, intentaré describir el problema de forma concisa y abstracta: Necesito encontrar el camino más largo posible en un gráfico cíclico no dirigido.

Answer 1

esto debería ser un algoritmo más bien fácil de implementar.

Para empezar, separa las carreteras en conjuntos distintos, donde todos los segmentos de la carretera en cada conjunto están de alguna manera conectados. Hay varios métodos sobre cómo hacer esto, pero aquí está uno:

1. Elige un segmento de carretera al azar, añadirlo a un conjunto, y se marca
2. sucursal fuera de este segmento, es decir. seguir los segmentos conectados en ambas direcciones que no están marcados (si están marcados, ya hemos estado aquí)
3. Si el segmento de carretera encontrado no está aún en el conjunto, agréguelo y márquelo
4. Continuar desde segmentos nuevos hasta que no pueda encontrar más segmentos sin marcar que están conectados a los que están actualmente en el conjunto
5. Si quedan segmentos sin marcar, son parte de un nuevo conjunto, elija uno aleatorio y comience de nuevo con 1 con otro conjunto

Nota: De acuerdo con la Catan Rules oficial, un camino puede romperse si ano ther play construye un asentamiento en una unión entre dos segmentos. Debe detectar esto y no pasar del acuerdo.

Nota: en los pasos anteriores y siguientes, solo tenga en cuenta los segmentos de reproductores actuales. Puede ignorar esos otros segmentos como si ni siquiera estuvieran en el mapa.

Esto le proporciona uno o más conjuntos, cada uno con uno o más segmentos de carretera.

Ok, para cada conjunto, haga lo siguiente:

1. Escoja un segmento de carretera al azar en el conjunto que tiene sólo un segmento de carretera conectado hacia fuera de él (es decir.tienes que elegir un punto final)
2. Si no puede hacer eso, entonces todo el conjunto es un bucle (uno o más), por lo que elegir un segmento de azar en este caso

Ahora, desde el segmento que eligió, realice una búsqueda recursiva de bifurcación en profundidad, haciendo un seguimiento de la longitud de la carretera actual que ha encontrado hasta ahora. Marque siempre los segmentos de la carretera también, y no bifurque en los segmentos ya marcados. Esto permitirá que el algoritmo se detenga cuando "come su propia cola".

Cuando necesite retroceder, porque no hay más ramas, tome nota de la longitud actual, y si es más larga que el "máximo anterior", almacene la nueva longitud como máximo.

Haga esto para todos los juegos, y debe tener el camino más largo.

Answer 2

lo que he hecho:

1. Elige un vértice con un camino
2. recogida en la mayoría de los dos caminos a seguir
3. Siga el camino; dar marcha atrás aquí si se ramifica, y escoger lo que era ya
4. Si vértice actual está en la lista de visitados, dar marcha atrás a 3
5. Añadir el vértice a la lista de visitados, Recurse de 3
6. Si no hay más camino a los 3, devolver la longitud
7. Cuando usted ha seguido en la mayoría de las carreteras 2, sumarlos, tenga en cuenta la longitud
8. Si había 3 carreteras en el vértice inicial, dar marcha atrás a 2.

este momento para la terminología prolog-ish :)

Answer 3

Sugeriría una búsqueda de amplitud.

Para cada jugador:

• Establecer un conocido máximo predeterminado de 0

• Escoja un nodo de partida. Omita si tiene cero o más de un vecino conectado y encuentre todos los caminos del jugador a partir de él de forma amplia. El truco: una vez que un nodo ha sido atravesado, se "desactiva" para todas las búsquedas que quedan en ese turno. Es decir, puede que ya no se atraviese.

  ¿Cómo se puede implementar esto? Aquí hay un posible algoritmo de amplitud que se puede usar:

  1. Si no hay rutas desde este nodo inicial, o más de una ruta, márquelo desactivado y sáltelo.
  2. Mantenga una cola de rutas.
  3. Agregue una ruta que contenga solo el nodo inicial sin salida a la cola. Desactivar este nodo
  4. Pop la primera ruta de la cola y "explotar" - es decir, encontrar todas las rutas válidas que son la ruta + 1 paso más en una dirección válida. Por "válido", el siguiente nodo debe estar conectado al último por un camino, y también debe estar activado.
  5. Desactivar todos los nodos a los que se dio un paso durante el último paso.
  6. Si no hay "explosiones" válidas de la ruta anterior, compare esa longitud de esa ruta con el máximo conocido. Si es mayor que eso, es el nuevo máximo.
  7. Agregue todas las rutas explosionadas, si las hubiera, de nuevo a la cola.
  8. Repita 4-7 hasta que la cola esté vacía.

• Después de hacer esto una vez, vaya al siguiente nodo activado y comience nuevamente el proceso. Deténgase cuando todos los nodos estén desactivados.

• El máximo que tiene ahora es la longitud de ruta más larga para un jugador determinado.

Tenga en cuenta que esto es un poco ineficiente, pero si el rendimiento no importa, entonces esto sería trabajar :)

NOTA IMPORTANTE, gracias a Cameron MacFarland

• Asumir todos los nodos con ciudades que no pertenecen al jugador actual desactivadas automáticamente siempre.

---

Rubí pseudocódigo (asume una función de get_neighbors para cada nodo)

def explode n 
    exploded = n.get_neighbors    # get all neighbors 
    exploded.select! { |i| i.activated? } # we only want activated ones 
    exploded.select! { |i| i.is_connected_to(n) } # we only want road-connected ones 
    return exploded 
end 

max = 0 

nodes.each do |n|     # for each node n 
    next if not n.activated?  # skip if node is deactivated 
    if explode(n).empty? or explode(n).size > 1 
    n.deactivate     # deactivate and skip if 
    next       # there are no neighbors or 
    end        # more than one 

    paths = [ [n] ]     # start queue 

    until paths.empty?    # do this until the queue is empty 

    curr_path = paths.pop   # pop a path from the queue 
    exploded = explode(curr_path) # get all of the exploded valid paths 

    exploded.each { |i| i.deactivate } # deactivate all of the exploded valid points 

    if exploded.empty?     # if no exploded paths 
     max = [max,curr_path.size].max # this is the end of the road, so compare its length to 
             # the max 
    else 
     exploded.each { |i| paths.unshift(curr_path.clone + i) } 
             # otherwise, add the new paths to the queue 
    end 

    end 

end 

puts max 

Answer 4

Puede usar Dijkstra y simplemente cambie las condiciones para elegir la ruta más larga.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Es eficiente, pero no siempre encuentran el camino que en realidad es más corta/larga a pesar de que va a funcionar la mayor parte de las veces.

Answer 5

Es poco probable que una simple búsqueda de profundidad en el primer tiempo polinomial funcione, ya que el problema es NP-hard. Necesitará algo que tome tiempo exponencial para obtener una solución óptima. Dado que el problema es muy pequeño, eso no debería ser un problema en la práctica.

Posiblemente la solución más simple sería la programación dinámica: mantener una tabla T [v, l] que almacene para cada nodo v y cada longitud l el conjunto de rutas que tienen longitud l y terminan en v. Claramente T [v, 1] = {[v]} y puede completar T [v, l] para l> 1 recopilando todas las rutas de T [w, l-1] donde w es un vecino de v que no contiene v, y luego adjuntar v. Esto es similar a la solución de Justin L. pero evita algunos trabajos duplicados.

Answer 6

Poco tarde, pero sigue siendo relevante. Lo implementé en Java, vea here. Algoritmo va como sigue:

• derivar un gráfico a partir de la gráfica principal usando todos los bordes de un jugador, la adición de los vértices de la gráfica principal conectado a los bordes
• Haga una lista de extremos (vértices donde grado == 1) y splits (vértices donde grado == 3)
• Agregue una ruta para verificar (possibleRoute) para cada extremo, y para cada dos bordes + una combinación de vértice encontrada (3, ya que el grado es 3) en cada división
• Camine por todas las rutas. Se pueden encontrar tres cosas: un final, intermedio o una división.
• Fin: Terminar possibleRoute, añadirlo a la lista que se encuentra
• Intermedio: comprobar si es posible la conexión a otro borde. Si es así, agrega el borde. De lo contrario, finalice la ruta y añádala a la lista de rutas encontradas
• División: para ambos extremos, haga como intermedio. Cuando ambas rutas se conectan, copie la segunda ruta y agréguela a la lista también.
• La comprobación de una conexión se realiza mediante dos métodos: ver si el nuevo borde ya existe en el posible Routing (sin conexión), y preguntar al nuevo borde si se puede conectar dando como vértices y vértices de origen.Un camino puede conectarse a una carretera, pero solo si el vértice no contiene una ciudad/asentamiento de otro jugador. Un camino puede conectarse a un barco, pero solo si el vértice contiene una ciudad o carretera del jugador cuya ruta se está controlando.
• Loops pueden existir. Cada borde encontrado se agrega a una lista si aún no está allí. Cuando se marcan todos los posiblesRutados, pero la cantidad de bordes en esta lista es menor que la cantidad total de bordes del jugador, existen uno o más bucles. Cuando este es el caso, cualquier borde no verificado se convierte en un nuevo posibleRuta de, y se vuelve a verificar para la ruta.
• La longitud de la ruta más larga se determina simplemente iterando en todas las rutas. Se devuelve la primera ruta encontrada con igual o más de 5 aristas.

Esta implementación es compatible con la mayoría de las variantes de Catan. Los bordes pueden decidir por sí mismos si quieren conectarse a otro, ver

SidePiece.canConnect(point, to.getSidePiece()); 

Una carretera, un barco, el puente tiene interfaz implementada pieza lateral. Un camino tiene como aplicación

public boolean canConnect(GraphPoint graphPoint, SidePiece otherPiece) 
{ 
    return (player.equals(graphPoint.getPlayer()) || graphPoint.getPlayer() == null) 
      && otherPiece.connectsWithRoad(); 
} 

Answer 7

Aquí está el fragmento de código que utilizo para determinar el camino más largo para un jugador dado ("usuario") en mi simulador de Catan Excel VBA.

hace un momento me di cuenta que no tiene en cuenta la regla sobre los asentamientos, pero eso no debería ser difícil de capa en.

Private Frays As Dictionary 
Private RoadPths As Collection 
Public Function GetLongestRoad(g As Board, oUser As User) As Long 
    Dim oRoad As Road 
    Dim v, w 
    Dim fNum As Long 
    Dim rCount As Long 

    Set Frays = New Dictionary 
    Set RoadPths = New Collection 

    ' get list of roads that happen to be linked to other roads ("Frays") 
    For fNum = 55 To 126 
     If g.Roads(fNum).Owner = oUser.Name Then 
      For Each v In RoadLinks(g, fNum) 
       If g.Roads(v).Owner = oUser.Name Then Frays(fNum) = v 
      Next v 
     End If 
    Next fNum 

    ' begin recursion 
    For Each v In Frays 
     RecurSegmts g, v & ";" & Frays(v) 
    Next v 

    rCount = 0 
    For Each v In RoadPths 
     w = Split(v, ";") 
     If rCount < UBound(w) Then rCount = UBound(w) 
    Next v 

    GetLongestRoad = rCount + 1 
End Function 

Private Sub RecurSegmts(g As Board, Segmts As Variant) 
    Dim SegmtArr, NextRoad 
    Dim LoopsBack As Boolean 
    Dim i As Long 

    RoadPths.Add Segmts 
    SegmtArr = Split(Segmts, ";") 

    For Each NextRoad In RoadLinks(g, CLng(SegmtArr(UBound(SegmtArr)))) 
     LoopsBack = False 
     For i = 0 To UBound(SegmtArr) 
      If CLng(NextRoad) = CLng(SegmtArr(i)) Then LoopsBack = True 
     Next i 

     If LoopsBack = False Then Call RecurSegmts(g, Segmts & ";" & NextRoad) 

    Next NextRoad 
End Sub 

Answer 8

Aquí está mi versión si alguien lo necesita. Escrito en Typescript.

longestRoadLengthForPlayer (jugador: PlayerColors): Número { dejar que longestRoad = 0

let mainLoop = (currentLongestRoad: number, tileEdge: TileEdge, passedCorners: TileCorner[], passedEdges: TileEdge[]) => { 
     if (!(passedEdges.indexOf(tileEdge) > -1) && tileEdge.owner == player) { 
      passedEdges.push(tileEdge) 
      currentLongestRoad++ 
      for (let endPoint of tileEdge.hexEdge.endPoints()) { 
       let corner = this.getTileCorner(endPoint)! 

       if ((corner.owner == player || corner.owner == PlayerColors.None) && !(passedCorners.indexOf(corner) > -1)) { 
        passedCorners.push(corner) 
        for (let hexEdge of corner.hexCorner.touchingEdges()) { 
         let edge = this.getTileEdge(hexEdge) 
         if (edge != undefined && edge != tileEdge) { 
          mainLoop(currentLongestRoad, edge, passedCorners, passedEdges) 
         } 
        } 
       } else { 
        checkIfLongestRoad(currentLongestRoad) 
       } 
      } 
     } else { 
      checkIfLongestRoad(currentLongestRoad) 
     } 
    } 

    for (let tileEdge of this.tileEdges) { 
     mainLoop(0, tileEdge, [], []) 
    } 

    function checkIfLongestRoad(roadLength: number) { 
     if (roadLength > longestRoad) { 
      longestRoad = roadLength 
     } 
    } 

    return longestRoad 
}