Algoritmo o dominio para encontrar subgrafos más baratos que conectan pares de vértices

7

Actualmente estoy trabajando en un proyecto inspirado en el juego de mesa Ticket to Ride . Este juego de mesa se juega en un gráfico no dirigido donde cada vértice representa una ciudad y cada borde representa una línea de tren reclamable que conecta dos ciudades. Los jugadores obtienen puntos reclamando una ventaja por sí mismos, y obtienen puntos según la cantidad de autos que la ruta requiere para reclamar. También hay boletos que dan puntos de bonificación si el jugador puede reclamar un camino que conecta las dos ciudades. Cada jugador tiene solo 45 autos, por lo que este es un problema de asignación de recursos.

Estoy tratando de escribir un programa que ayude a los agentes (personas o AI) a planificar qué rutas tomar en función de qué tickets debe completar el agente, qué rutas ya ha reclamado el agente y qué rutas no están disponibles debido a otros jugadores. habiendolos reclamado Necesito un algoritmo que encuentre un conjunto de subgrafos (s) de manera que cada boleto tenga su ciudad en el mismo subgrafo al intentar optimizar algunos criterios (uso mínimo del auto, puntos máximos por carro, etc.). No me importa si el algoritmo obtiene todas las ciudades en un subgrafo, o si las encierra en una línea sin ramificación (lo que ayudaría a obtener el bono de Ruta más larga); Quiero algo que le permita al agente completar los tickets rápidamente para que pueda comenzar a trabajar en los nuevos.

El problema es que no tengo suficiente familiaridad con la teoría de grafos para saber el nombre de este tipo de problema. He intentado búsquedas con texto que describe lo que estoy tratando de hacer sin suerte. También busqué en mis antiguos libros de texto ( Introducción a los algoritmos y Algoritmos en C: Parte 5 - Algoritmos de gráficos ) para tratar de encontrar un dominio de problemas de gráficos que parezca estar relacionado con mi problema; Lo más cercano parece ser el flujo de la red, pero eso no parece estar lo suficientemente cerca.

He intentado resolver este problema por mi cuenta. Escribí un A * que puntuaba cada conjunto de subgrafos en función de la distancia mínima estimada a un nodo, pero no funcionó (como habría descubierto si hubiera leído el artículo de Wikipedia en A * primero). Escribí una implementación de NSGA-II para tratar de resolver el problema de manera estocástica, pero curiosamente parece empeorar cuanto más cerca está el conjunto inicial de las ventajas propias de conectar los tickets. De hecho, la implementación de NSGA-II se "asusta" y encuentra rutas muy extrañas para conectar subgrafos cuando solo una de las rutas anteriores al algoritmo recomendado.

¿Alguien podría decirme el nombre de este dominio para que pueda empezar a investigar, señalarme un algoritmo o proponer un algoritmo que pueda probar?

    
pregunta sadakatsu 26.02.2015 - 18:53

3 respuestas

2

Suena como un problema de optimización combinatoria. Comenzaría por leer acerca de la rama y el límite, y otras técnicas utilizadas en ese tipo de problema. Su representación de un punto en el espacio problemático (la combinación actual) puede tener un efecto en la eficiencia. Si puede crear una representación compacta, puede comparar puntos y evitar recorridos redundantes en el árbol de combinaciones. Su función de costo también es muy importante: es decir, qué tan buena es una combinación particular (sucursal) hasta ahora, en comparación con otras.

    
respondido por el Frank Hileman 02.03.2015 - 17:38
2

Lo que estás intentando hacer es no trivial.

Usted tiene efectivamente un gráfico y está tratando de optimizar una serie de conexiones basadas en reglas y restricciones relativamente complicadas.

  

¿Alguien podría decirme el nombre de este dominio para que pueda empezar a investigar, señalarme un algoritmo o proponer un algoritmo que pueda probar?

Una descripción más formal de su problema es un problema de optimización restringida. Hay una variedad de métodos en la literatura que tratan estos problemas, como problemas combinatorios .

Dependiendo de cómo haya implementado sus restricciones, puede usar una variedad de métodos. Parece que sus restricciones son relativamente sencillas de enumerar heurísticamente.

Es posible que tenga éxito en modificar su problema para que sea un problema de vendedor ambulante ya que hay muchos métodos. para hacer frente a estos.

No estoy lo suficientemente familiarizado con Ticket to Ride para saber cómo se calculan los "puntos" para una ruta. Si es posible determinar un valor por borde, esto es ideal. Lo ideal sería convertir esto en un problema que se pueda abordar directamente con la metodología existente. NO desea intentar inventar su propio algoritmo de optimización para lidiar con esto.

    
respondido por el enderland 02.03.2015 - 19:28
1

Quiero agradecer a aquellos que han publicado respuestas con respecto a la optimización combinatoria. Voy a comenzar a estudiar el campo este fin de semana después de mudarme. Mientras tanto, quería presentar mi mejor esfuerzo actual en caso de que otra persona lo encuentre útil.

He desarrollado un algoritmo basado en heurística que parece encontrar al menos resultados decentes en lo que puede ser una cantidad de tiempo aceptable una vez que lanzo parte del procesamiento en un algoritmo. Estimo la complejidad del algoritmo en O (T! M ^ TV ^ 2 E ^ 2) , donde T es el número de pares a resolver (el número de boletos) para completar), M es el número máximo de rutas de igual longitud encontradas para conectar dos vértices usando un Bellman-Ford modificado, V es el número de vértices en el gráfico ( 36 para mi mapa), y E es el número de bordes en el gráfico (78 para mi mapa). Para mis propósitos, M parece ser bastante bajo (probablemente con un límite de 6, y con frecuencia más bajo que eso), y no espero que T sea más de 5 (aunque 3 es un techo mucho más probable).

La suposición básica detrás de este algoritmo es que la mejor ruta conectará de manera óptima uno de los pares de vértices, y las otras tienen más probabilidades de ahorrar costos al conectarse a esta ruta que a conectarse directamente utilizando sus rutas óptimas localmente. El truco consiste en encontrar el orden correcto para conectar los pares que mejor reduzca el costo. El siguiente enfoque recursivo es la columna vertebral del algoritmo:

def planWorker(graph, pairs, ownedEdges, blockedEdges):
    if there are no pairs:
        return 0, empty set
    bestScore, added <- null, empty set
    build a Bellman-Ford table for every vertex in the graph
    // each ownedEdge costs 0
    // each blockedEdge effectively no longer exists in the graph
    for each pair:
        base <- distance to complete pair
        options <- all shortest paths connecting the pair
        // options is a set of sets of edges
        if this is the last ticket:
            bestScore <- base
            for each option:
                path <- option - owned
                added.add(path)
        else:
            for each option:
                subscore, subpaths <- planWorker(graph, pairs - pair, owned + option, blocked)
                total <- base + subscore
                if bestScore == null or total <= bestScore:
                    if bestScore == null or total < bestScore:
                        bestScore <- total
                        added <- empty set
                    for each subpath:
                        added.add(option + subpath)
    return bestScore, added

La complejidad de este algoritmo es O (T! M ^ T | V | ^ 2 | E |). Llamado por sí solo, encuentra al menos un buen umbral con el que comparar otras rutas. Todavía no he encontrado un ejemplo en el que no encuentre al menos un subconjunto de las rutas óptimas, pero no asumo que sí encuentre las rutas óptimas porque no sé si mi suposición sobre la estructura óptima de la ruta es correcta.

He encontrado que este algoritmo no encuentra todas las rutas de la misma longitud para un conjunto de pares. Sin embargo, al agregar una búsqueda adicional probando bordes no probados, el algoritmo parece probarlos todos:

def plan(graph, pairs, owned, blocked):
    bestScore, added <- planWorker(graph, pairs, owned, blocked)
    candidates <- graph.edges - owned - blocked - flatten(added) // the "untried" edges
    for each candidate:
        base = candidate's weight
        score, alternatives <- planWorker(graph, pairs, owned + candidate, blocked)
        total <- base + score
        if total > bestScore:
            continue
        if total < bestScore:
            bestScore = total
            added <- empty set
        for each path in alternatives:
            added <- added + (path + candidate)
    return bestScore, added

El bucle multiplica la complejidad computacional por E , dando la complejidad computacional final de O (T! M ^ T V ^ 2 E ^ 2) . Probablemente hay términos adicionales que no estoy considerando que provienen de las operaciones del conjunto, pero supongo que los conjuntos que estoy usando realmente no necesitan más que un log E múltiple adicional para eso.

He pirateado este enfoque (probablemente muy ineficientemente) en Java 8. Ejecutar esta implementación para cuatro tickets en el mapa Ticket to Ride sin rutas de propiedad o bloqueo inicialmente toma menos de doce minutos en mi computadora portátil desenchufada con un Intel Core i7-4710HQ con velocidad de reloj de 2.5 GHz. Es probable que pueda acelerarlo reduciendo la asignación de memoria dinámica y enlazando los cheques candidatos en lugar de hacer un bucle sobre ellos de forma sincrónica. Este algoritmo resuelve los boletos (Los Ángeles, Miami), (Los Ángeles, Nueva York), (Montreal, Vancouver) y (Nueva York, Seattle) con un costo de 39 automóviles. Las seis rutas con esa longitud que encuentra se muestran a continuación. La llamada inicial planWorker() encuentra la ruta verde y la búsqueda de candidatos encuentra las otras cinco.

    
respondido por el sadakatsu 03.03.2015 - 15:29

Lea otras preguntas en las etiquetas