Problema di teoria dei grafi (nome sconosciuto)

Se sto leggendo la tua domanda correttamente, il tuo problema ha due proprietà interessanti:

1. Il grafico è collegato in sequenza, A- > B- > C- > D. Potrebbero esserci più spigoli tra i nodi, ma non ci sono mai bordi che "saltano" i nodi (A- > C, B- > D) o loopback (C- > A).
2. L'obiettivo finale è la fattibilità rispetto all'ottimalità. Cioè, vuoi sapere se un viaggiatore ha abbastanza soldi contro quale percorso costa il minimo assoluto.

È corretto? Se è così, ci sono alcuni trucchi disponibili.

In primo luogo, calcola il valore atteso sia in oro che in bronzo tra ogni città. Il valore atteso sarebbe il minimo che ti aspetteresti di pagare. Dato AB1 = 5 oro, AB2 = 5 bronzo e AB3 = 10 oro o bronzo (sto aggiungendo la strada per illustrare un punto), non selezioni mai AB3. AB1 o AB2 ti danno una soluzione migliore indipendentemente dalla moneta che usi. Pertanto, il valore atteso tra A e B è 5 oro e 5 bronzo. Il valore atteso tra B e C è 8 oro e 10 bronzo. Ancora una volta, non selezioneremmo mai BC1 (10 oro o bronzo) quando spendiamo oro come BC2 (8 oro) è sempre più economico. Continua a calcolare i valori previsti per il resto del percorso.

Successivamente, somma i valori attesi per ogni moneta. Stai praticamente agendo come se avessi pagato tutti i pedaggi usando un tipo di moneta, ma lo stai facendo per entrambi i tipi in un solo passaggio. Se i tuoi valori previsti sono:

• A- > B 5 oro, 5 bronzo
• B- > C 8 oro, 10 bronzo
• C- > D 10 oro, 7 bronzo

I tuoi totali sono 23 oro e 22 bronzo. Se hai iniziato con 23 o più gold e 22 o più di bronzo, hai finito. Sai che esiste una soluzione fattibile. Più probabilmente, i tuoi totali previsti saranno maggiori delle tue monete disponibili.

In tal caso, fai una scelta tra coppie di valori attesi e considerando entrambe le opzioni. Se sei a corto di oro, spendi il bronzo dove restituisce il massimo dell'oro. Ad esempio, se inizio con 13 monete d'oro, posso selezionare l'opzione di pagamento in bronzo tra C- > D per creare una soluzione fattibile. Se inizio con 5 bronzo, posso selezionare l'opzione di pagamento in oro tra B- > C e C- > D per creare una soluzione fattibile.

Di nuovo, probabilmente è un pio desiderio. È probabile che sarai a corto di oro e bronzo. In tal caso, iniziare con un'euristica per risolvere i valori previsti: se si dispone di un deficit di oro più grande, selezionare i valori attesi che producono i maggiori risparmi in oro prima di risolvere il bronzo, cercare di recuperare il deficit con il minor numero possibile di "scelte", ecc ... Alla fine, potrebbe essere necessario provare ogni combinazione di valori attesi per dimostrare che una soluzione fattibile esiste o non esiste.

Si noti che questo non tiene conto dei pedaggi che coinvolgono entrambe le valute. Un tributo di 2 monete d'oro e di bronzo 5 il mio trucco del valore atteso.

Non sono sicuro che potrebbe essere correlato a un algoritmo di flusso, perché un problema di flusso ti permetterebbe di andare parzialmente in fondo alla strada AB1 e parzialmente in fondo alla strada AB2, per esempio.

Penso che tu sia praticamente bloccato con la prima ricerca approfondita, ma hai opportunità per la potatura. Ad esempio, se una strada richiede 8 monete d'oro e un'altra tra le stesse due città richiede 10 monete d'oro, non devi preoccuparti di attraversare quest'ultima. Ciò ti lascia con un oro, un bronzo e un "o" percorso tra ogni città. Inoltre, tieni presente che l'ordine che visiti le città non ha importanza dal punto di vista dell'algoritmo. Se le strade del CD sono tutte più costose di quelle AB, potresti essere in grado di velocizzare le cose spostandole prima.

Se il tuo viaggiatore dovesse tornare all'inizio sarebbe una variazione del link . Com'è, è solo un problema di ottimizzazione del percorso. Lo affronterò usando Depth First Search , ma è perché è uno dei soli due o tre algoritmi di attraversamento grafico I ricorda dalla scuola di specializzazione.

È solo un problema con il percorso minimo / minimo dichiarato come problema decisionale. Ma con un costo bidimensionale. Esiste un percorso che costa meno di x monete d'oro e meno di monete di bronzo?

Questo rende il problema molto più difficile da risolvere nel caso generale, poiché può esserci un numero enorme di potenziali coppie ottimali (oro, bronzo) -cost per nodo. La vera sfida in questo è occuparsi del costo bidimensionale, la ricerca del grafico è parte proprio lì per raccontare la storia. Potrebbe essere qualsiasi tipo di ottimizzazione.