Trasformare un algoritmo fisico in uno computerizzato

Nell'algoritmo "fisico" usi il parallelismo massiccio della natura.

Senza passare al livello molecolare, ogni nodo e movimento del connettore viene "calcolato" in parallelo. Per ottenere la stessa velocità avresti bisogno di un computer con un numero eccessivo di core CPU e una comunicazione estremamente veloce tra loro.

Quindi direi: no, solitamente la mappatura diretta dell'algoritmo fisico al computer non fornisce un algoritmo veloce.

Quello che stai descrivendo è un computer analogico . Questi erano in realtà costruiti per determinati scopi e i vecchi libri di CS avevano capitoli dedicati a loro. Questi capitoli si sono accorciati nel tempo e alla fine sono scomparsi, così come le macchine. Il problema è che i computer analogici

• non si adatta bene
• sono molto limitati nella precisione dei risultati che possono dare
• sono molto rigidi (devono essere costruiti per uno scopo specifico, relativamente ristretto)

Come per "Trasformare un algoritmo fisico in uno computerizzato" - ciò non è possibile, perché il nucleo del computer analogico non è affatto un algoritmo - è solo usando le leggi della fisica che operano continuamente su un meccanismo, mentre un algoritmo consiste di passaggi discreti.

C'è una ragione per cui le simulazioni fisiche sono alcune delle applicazioni più impegnative per i supercomputer, per cui essenzialmente mai hanno una potenza di calcolo sufficiente.

Consente di analizzare la soluzione fisica in modo più dettagliato.

La prima costruzione del grafico sarà O (E + V) dato che devi legare ogni spigolo a ciascun nodo connesso (E è il numero di spigoli, V numero di vertici su un grafico ben collegato questo sarà O ( E)). In termini di complessità, ciò equivale a costruire un grafico come software, ma possiamo già immaginare che i fattori costanti saranno molto più grandi per la legatura di stringhe.

La seconda estrazione dei nodi iniziale e finale non dà la risposta istantaneamente, la forza deve propagarsi lungo il percorso più breve, quindi possiamo selezionare la risposta in O (L) dove L è la lunghezza del percorso più breve, questo ancora sembra abbastanza buono, e questo perché la forza si propaga in parallelo. Tuttavia abbiamo ancora altri problemi qui, se ci sono due percorsi di lunghezza molto simile, allora sarà difficile scegliere tra di loro come la larghezza finita delle stringhe e dei nodi significherà che sono entrambi sotto tensione.

Infine, consente di esaminare la scala. Tutte le tue corde hanno una massa fisica e la massima resistenza alla trazione. Supponendo che abbiamo un filo di acciaio abbiamo una lunghezza di rottura di 25,9 km . Nel peggiore dei casi il tuo percorso più breve è di 3 nodi con tutti gli altri bordi / nodi che pendono dal nodo centrale, quindi questo significherà (in acciaio) la lunghezza massima di tutto il filo nel tuo grafico sarà di circa 25,9 km. dato l'alto fattore costante nella costruzione, questo può significare che ci sono pochissimi o addirittura nessun grafico per il quale è sia possibile sia più veloce risolvere fisicamente il problema del percorso più breve.

Conversione in una soluzione di computer, se colleghiamo i nodi hardware V con i canali di messaggi E in modo che il tempo di propagare un messaggio lungo un canale sia il peso di un margine, penso che possiamo ancora vedere che se possiamo inviare un messaggio parallelo lungo tutti i bordi possiamo trovare il percorso più breve nel tempo O (L). E questo penso che dimostri il problema chiave, stai usando l'hardware O (E + V) per farlo, se lo convertiamo in software su hardware O (1) in modo diretto allora l'algoritmo diventa O (L + E + V) come ora dobbiamo simulare tutto il nostro hardware in serie. Ora possiamo vedere che questo è peggio dei soliti algoritmi.

Penso che questo sia ciò di cui OP sta parlando:

Puoi quasi istantaneamente trovare il percorso più breve nella vita reale, ma non sono sicuro di quanto potrebbe funzionare con un computer- Potresti assegnare un valore di tensione a ogni nodo collegato agli endpoint, quindi a ciascuno dei nodi collegati a ciascuno di questi nodi, e così via, ma sono abbastanza sicuro che altri metodi sarebbero più veloci.

Simulare la fisica per ciascun nodo richiederebbe probabilmente molto più tempo rispetto alla semplice ricerca della distanza di ciascun nodo tra i due endpoint.

Non esiste una distinzione tra un algoritmo "fisico" e uno "computerizzato": la verità è che un algoritmo è un'idea o una formula completamente concettuale. I computer sono in grado di eseguire esattamente lo stesso sottoinsieme di calcoli che i cervelli umani possono fare, né più né meno: la vera differenza è la velocità. In quanto tale, qualsiasi formula che hai per fare qualcosa fisicamente ha un equivalente che può essere programmato, e viceversa. Questo è il principio "I computer non sono magici" che tutti gli studenti di informatica dovrebbero accettare.

Credo che il tipico algoritmo di percorso più breve a cui sei abituato sia funzionalmente equivalente al tuo metodo di corda, e che tu non stia prendendo in considerazione la relativa complessità di come la scelta delle varie palle e la loro caduta equivalgono ai controlli che un computer avrebbe eseguito.

How exactly does one take this physical method of solving the problem and implement it in a computer?

La natura sequenziale dei computer digitali impedisce loro di mimare perfettamente molte operazioni fisiche, quindi non c'è sempre un modo utile per implementare algoritmi fisici nel software.

Spaghetti sort è un classico esempio di un'operazione fisica che non può essere implementata in software con le stesse prestazioni. L'idea è che tu rappresenti una serie di numeri tagliando pezzi di spaghetti secchi a lunghezze corrispondenti a ciascun numero dell'insieme. Quindi raccogli gli spaghetti in mano e abbassa il fascio su una superficie in modo che le estremità siano tutte allineate. È quindi semplice rimuovere i pezzi dal pacchetto uno alla volta, iniziando dal più lungo. Le prestazioni sono O (n) perché il tempo di tagliare gli spaghetti e il tempo per rimuovere tutti i fili dal gruppo sono entrambi O (n).

La versione software dell'ordinamento spaghetti è tipo di selezione , che ha O (n ² ) prestazioni. La ragione di ciò è che una macchina sequenziale come un computer non è in grado di valutare tutti i numeri contemporaneamente. Invece, deve scorrere l'elenco dei numeri che cercano il più grande, che è di per sé un'operazione di tipo O (n), e deve scegliere il numero più grande n volte. Nel mondo reale, possiamo valutare tutti i fili di spaghetti contemporaneamente, quindi la selezione è O (1) invece di O (n).

Quindi, la risposta alla tua domanda è che non è sempre possibile convertire un metodo fisico in software e preservare i vantaggi del metodo fisico.