Qualcuno può aiutarmi a creare una soluzione di programmazione dinamica per questo problema?

Naviga le tue risposte
1

Ho alcuni nomi di funzioni che sono assegnati ad alcuni nodi. Devo decidere quali funzioni spostare su altri nodi per aumentare la velocità.

Perché devo spostare le funzioni su altri nodi? Se le funzioni di comunicazione si trovano sugli stessi nodi, richiedono meno tempo rispetto a quando le funzioni di comunicazione si trovano su nodi diversi. Una funzione potrebbe comunicare con diverse funzioni (tutte potrebbero essere su nodi diversi). La domanda è su quale nodo devo spostarlo, per massimizzare le prestazioni globali.

Ho bisogno di trovare una soluzione ottimale a livello globale usando la programmazione dinamica.

Ho le seguenti informazioni

  1. Il valore intero della quantità di dati trasferiti tra le funzioni

  2. La quantità di tempo necessaria per trasferire i dati tra i nodi. Inizialmente tutte le funzioni sono state assegnate ad alcuni nodi.

Qualcuno può aiutarmi a mappare questo problema all'algoritmo di schedulazione della catena di montaggio (programmazione dinamica) o creare qualche altra soluzione di programmazione dinamica a questo problema?

La metrica complessa è il tempo di esecuzione dell'intero programma. Il tempo di esecuzione indipendente di una funzione è calcolato da qualsiasi API temporizzatore (l'abbiamo già). Il tempo di esecuzione effettivo della sua (funzione) sarebbe uguale al tempo di esecuzione indipendente + il tempo di esecuzione di tutte le funzioni che producono dati consumati da questa funzione + il tempo di comunicazione tra questa funzione e altre funzioni sullo stesso nodo + il tempo di comunicazione tra questo funzione e funzioni su altri nodi. Il tempo di esecuzione del programma sarebbe quindi la somma del tempo di esecuzione di tutte le funzioni del programma.

Devo minimizzare il tempo di esecuzione del programma che è la somma del tempo di esecuzione di tutte le funzioni. Ogni tempo di esecuzione delle funzioni è la somma del suo tempo (precalcolato) e la somma di tutte le funzioni che verranno eseguite prima di esso e la sua somma con il suo tempo trascorso a comunicare con altre funzioni (nodi uguali o diversi).

    
posta Robert Harvey 21.11.2013 - 15:02
fonte

1 risposta

7

Quindi hai uno scenario in cui hai molte variabili che forniscono un risultato facile da testare e devi assolutamente conoscere la configurazione ottimale?

Congratulazioni! Hai un problema NP-Completo. Se è assolutamente necessario conoscere la configurazione ottimale, è necessario eseguire un algoritmo a forza bruta per provare ogni singola combinazione. In realtà, non stiamo parlando di un problema molto diverso dal problema dell'imballaggio del contenitore.

Tuttavia, detto questo, forse sei flessibile nel trovare quella soluzione ottimale. Forse non deve essere la soluzione migliore, ma entro il 99% della soluzione migliore.

Ricottura simulata

La ricottura simulata è un approccio eccellente in generale, se non ti dispiace il fatto che probabilmente non ottieni la soluzione ottimale. Il più grande vantaggio di questo approccio è la sua velocità, dal momento che essenzialmente stai facendo soluzioni migliori con le buone soluzioni esistenti.

Lati positivi: veloce

Svantaggi: la soluzione migliore non è probabile

Algoritmo genetico

Gli algoritmi genetici sono progettati per gestire specificamente questi tipi di problemi, vale a dire, molte variabili, ma facili da test. Dovresti definire le soluzioni di configurazione, essere in grado di unire due soluzioni di configurazione ed essere in grado di creare un punteggio basato su tale configurazione (fitness). Da lì, generi una popolazione di soluzioni di configurazione casuali e la esegui finché non ottieni una soluzione soddisfacente.

Upsides: molto più veloce della forza bruta

Aspetti negativi: non molto efficienti se ci sono solo pochi nodi

Forza bruta

Non escluderei automaticamente l'algoritmo della forza bruta solo perché è il più lento. Se hai pochi nodi, potresti scoprire che puoi ottenere la soluzione ottimale con il minimo sforzo. In ogni caso, è la soluzione che impiegherebbe meno tempo per implementare e vale la pena provare se non vedere se questa è una soluzione fattibile.

Upsides: facilmente implementato, garantisce una soluzione ottimale

Aspetti negativi: lento con grandi quantità di nodi

Conclusione

È difficile dire quale sia la soluzione più adatta alle tue esigenze, tuttavia, una cosa è certa: se ottenere la soluzione ottimale è la tua priorità, allora non fa differenza quale algoritmo applichi per quanto riguarda la precisione, dal momento che devi cercare l'intero spazio della soluzione per garantire di avere la soluzione ottimale. Per quanto riguarda la velocità, la forza bruta sarà la più veloce delle tre, poiché gli altri algoritmi sono ideali solo per trovare una buona soluzione in modo efficiente.

Spero che ti aiuti!

    
risposta data 21.11.2013 - 16:52
fonte

Leggi altre domande sui tag

COBOL & Mainframe & Business [chiuso] 1 a 1 Sistema di confronto e classificazione