Trova il percorso minimo in un albero con nodi multivalore

Question

Le mie lezioni di matematica sono molto indietro, e attualmente sto lottando per trovare una soluzione decente a un problema che sto riscontrando: ho un albero, in cui i nodi sono azioni e sono "ponderati" secondo più criteri: il costo di detta azione, il tempo necessario, le risorse necessarie, il disturbo, ecc ...

E voglio trovare in questo albero il percorso che minimizza sia il costo E il tempo ad esempio, sia il disturbo E il costo E il tempo, ecc. Il mio problema è che non ho idea di come farlo, tranne presentando una funzione di costo globale F (costo, tempo, risorse, ...) e applicando un normale algoritmo di attraversamento dell'albero usando il risultato di F (...) come mio unico peso. Ma allora, come faccio a trovare F? Qualcosa di simile a " F (costo, tempo, risorse) = a * costo + b * tempo + c * risorse " sembra molto "poco professionale" ...

Modifica:

Volevo evitare la parola "somma" " poiché non ero sicuro che fosse davvero la strada da percorrere, ma in sostanza, è quello che sto facendo: calcolare un costo totale per ogni "percorso" o "ramo" che va da quel nodo superiore, a una delle foglie, e scegliendo il "percorso" o "ramo" che minimizza il costo. Il problema è che ogni nodo ha un peso basato sul tempo necessario, sui costi finanziari, sull'utilizzo delle risorse, ecc.

Quindi sembra inevitabile dover elaborare una formula, come dice Stephan, che ridurrà tutti questi parametri a un costo globale, per nodo, che posso quindi sommare attraverso i nodi mentre viaggio lungo l'albero, e scegliere il percorso che minimizza il costo totale.

Quindi credo che la mia domanda sia davvero, esiste una metodologia per scegliere quella funzione?

Grazie per le risposte e i commenti, ora inizia a essere un po 'più chiaro nella mia testa.

Answer 1

Supponiamo di avere quattro coppie (x, y) come (1, 4), (1, 5), (2, 3), (3, 3). Ora vuoi minimizzare " sia x che y " ;. Cosa intendi? Se minimizzi prima x e poi y finisci con (1, 4). Se minimizzi prima y e poi x trovi (2, 3).

A meno che tu non scelga una funzione di costo globale F (x, y), come nella tua osservazione, non riesco a vedere alcun significato di " entrambi " ;. (Ad ogni modo, una volta scelta F, possono esserci ancora più punti minimi.) A proposito, a mio avviso una combinazione lineare (i moltiplicatori positivi a, b, c intesi come "pesi") non è "non professionale"; affatto, almeno se non hai idea di quale potrebbe essere una funzione di costo più adatta.

Modifica:

  

Quindi sembra inevitabile dover elaborare una formula, come dice Stephan, che ridurrà tutti questi parametri a un costo globale, per nodo, che posso quindi sommare attraverso i nodi mentre viaggio lungo l'albero, e scegliere il percorso che minimizza il costo totale.

Attenzione. In effetti questa strategia ha senso solo se F è lineare. Sicuramente costo, tempo, risorse, ecc. Sono funzioni additive, nel senso che tempo (nodo1 - > nodo2 - > nodo3) = tempo (nodo1) + tempo (nodo2) + tempo (nodo3), ma in generale non lo è il caso di F, a meno che non sia lineare. (ovvero F (costo (nodo1 - > nodo2)) = F (costo (nodo1) + costo (nodo2))! = F (costo (nodo1)) + F (costo (nodo2)).)

Se si sceglie una funzione di costo globale non lineare, la strategia giusta è calcolare, per ciascun nodo, il costo totale, il tempo totale, le risorse totali dalla radice a quel nodo e calcolare (quindi minimizzare) F solo per il terminale nodi.

Answer 2

Venire con F è la cosa più importante. Se posso darti 6 costi e 5 volte o 5 volte e 6 costi, quale preferisci? La tua funzione di costo deve tenerne conto. Purtroppo non esiste un algoritmo che risolverà il problema. L'ho negato per una settimana prima di sedermi e scrivere F per un'applicazione di ottimizzazione su cui stavo lavorando. Nel peggiore dei casi, lasciare all'utente i parametri con cui armeggiare.

Answer 3

Perché un normale algoritmo di ricerca di grafici come A * non funziona?

Per la funzione percorso-costo, è possibile utilizzare la somma corrente dei criteri pertinenti. La distanza dall'obiettivo è più difficile ...

potrebbe essere la distanza dalla foglia più vicina, pre-calcolata per tutti o alcuni nodi, anche se sembra terribilmente costosa. A seconda della struttura del tuo albero, potresti trovare una sottovalutazione più economica - se è perfettamente bilanciata, ad esempio, è banale.