Algoritmo o dominio per trovare sottografi più economici che collegano coppie di vertici

Sembra un problema di ottimizzazione combinatoria. Vorrei iniziare leggendo di ramo e rilegato, e altre tecniche utilizzate in quel tipo di problema. La tua rappresentazione di un punto nello spazio del problema (la combinazione attuale) può avere un effetto sull'efficienza. Se è possibile creare una rappresentazione compatta, è possibile confrontare i punti ed evitare attraversamenti di rami ridondanti nell'albero delle combinazioni. Anche la tua funzione di costo è molto importante: cioè, quanto è buona una particolare combinazione (ramo) fino ad ora, rispetto ad altre.

Quello che stai tentando di fare è non banale.

Hai effettivamente un grafico e stai cercando di ottimizzare una serie di connessioni basate su regole e vincoli relativamente complicati.

Could someone either tell me the name of this domain so I can start doing research, point me to an algorithm, or propose an algorithm that I could try?

Una descrizione più formale del problema è un problema di ottimizzazione vincolata. Esistono vari metodi in letteratura che trattano tali problemi, come i problemi combinatori .

A seconda di come hai implementato i vincoli, puoi utilizzare una varietà di metodi. sembra come se i tuoi vincoli fossero relativamente semplici da elencare euristicamente.

Potresti trovare successo nel modificare il tuo problema per essere un problema del commesso viaggiatore poiché ci sono molti metodi occuparsi di questi

Non sono abbastanza familiare con Ticket to Ride per sapere come vengono calcolati i "punti" per un percorso. Se è possibile determinare un valore per spigolo, questo è l'ideale. Preferisci idealmente convertirlo in un problema che può essere indirizzato direttamente con la metodologia esistente. NON vuoi provare a inventare il tuo algoritmo di ottimizzazione per far fronte a questo.

Voglio ringraziare coloro che hanno pubblicato risposte sull'ottimizzazione combinatoria. Ho intenzione di iniziare a studiare il campo questo fine settimana dopo il mio trasloco. Nel frattempo, volevo presentare il mio miglior sforzo nel caso in cui qualcun altro potesse trovarlo utile.

Ho sviluppato un algoritmo guidato euristicamente che sembra trovare risultati almeno decenti in quella che potrebbe essere una quantità accettabile di tempo una volta che lancio una parte dell'elaborazione in un algoritmo. Stimo la complessità dell'algoritmo in O (T! M ^ TV ^ 2 E ^ 2) , dove T è il numero di coppie da risolvere (il numero di biglietti per completare), M è il numero massimo di percorsi di uguale lunghezza trovati per collegare due vertici usando un Bellman-Ford modificato, V è il numero di vertici nel grafico ( 36 per la mia mappa), e E è il numero di spigoli nel grafico (78 per la mia mappa). Per i miei scopi, M sembra essere piuttosto basso (probabilmente limitato a 6, e spesso inferiore a quello), e non mi aspetto che T sia più di 5 (sebbene 3 è un soffitto molto più probabile).

L'assunto di base dietro questo algoritmo è che il percorso migliore connetterà in modo ottimale una delle coppie di vertici e che gli altri hanno maggiori probabilità di risparmiare sui costi collegandosi a questo percorso piuttosto che collegarsi direttamente usando i loro percorsi localmente ottimali. Il trucco è trovare l'ordine corretto per connettere le coppie che meglio riduce il costo. Il seguente approccio ricorsivo è il backbone dell'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 complessità di questo algoritmo è O (T! M ^ T | V | ^ 2 | E |). Chiamato da solo, trova almeno una buona soglia rispetto alla quale confrontare altri percorsi. Non ho ancora trovato un esempio in cui non trovi almeno un sottoinsieme dei percorsi ottimali, ma non presumo che trovi percorsi ottimali perché non so che la mia ipotesi sulla struttura ottimale del percorso sia corretta.

Ho trovato che questo algoritmo non trova tutti i percorsi della stessa lunghezza per un insieme di coppie. Tuttavia, aggiungendo una ricerca aggiuntiva per testare i bordi non sperimentati, l'algoritmo sembra provarli tutti:

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

Il ciclo moltiplica la complessità computazionale di E , dando la complessità computazionale finale di O (T! M ^ T V ^ 2 E ^ 2) . Probabilmente ci sono termini aggiuntivi che non sto tenendo conto che provengono dalle operazioni del set, ma la mia ipotesi è che i set che sto usando non abbiano davvero bisogno di più di un log E multiplo per quello.

Ho hackerato questo approccio (probabilmente in modo molto inefficiente) in Java 8. L'esecuzione di questa implementazione per quattro ticket sulla mappa Ticket to Ride senza percorsi inizialmente di proprietà o bloccati richiede meno di dodici minuti sul mio laptop unplugged con un processore Intel Core i7-4710HQ con clock a 2.5 GHz. Posso probabilmente accelerarlo riducendo l'allocazione dinamica della memoria e inserendo i controlli candidati invece di eseguire il ciclo su di essi in modo sincrono. Questo algoritmo risolve i biglietti (Los Angeles, Miami), (Los Angeles, New York), (Montreal, Vancouver) e (New York, Seattle) con un costo di 39 auto. Di seguito sono mostrati i sei percorsi con quella lunghezza che trova. La chiamata iniziale planWorker() trova la rotta verde e la ricerca candidata trova gli altri cinque.