Come vengono sviluppati gli algoritmi? [chiuso]

5

Sono impressionato dall'efficienza di alcuni algoritmi e ho notato come il problema possa essere risolto e / o sembrare davvero non intuitivo.

Può sembrare stupido, ma mi piacerebbe sapere:

  • In che modo gli autori escogitano algoritmi sorprendenti? Continuano a pensare al problema e finiscono con la risposta? Sono dei geni?

  • Che mi porta alla mia prossima domanda: quanto tempo impiegano per trovare la soluzione? Ore, giorni, mesi, anni?

So che non esiste una risposta definitiva a queste domande. Ma mi piacerebbe sapere come funziona di solito per quanto riguarda gli algoritmi più usati / noti.

    
posta 2013Asker 04.12.2013 - 17:40
fonte

4 risposte

11

How are algorithms developed?

In generale, ecco come vengono sviluppati gli algoritmi.

  1. Trova un problema (o un problema con una soluzione esistente)
  2. Trova una soluzione al problema
  3. Ripeti i passaggi 1 e amp; 2 fino a quando non riesci a trovare un problema o non riesci a risolverlo.

La soluzione risultante è l'algoritmo per risolvere il problema.

Gli algoritmi "Really Useful" si verificano quando si dispone di un algoritmo monouso esistente e si rendono conto che potrebbe essere utilizzato in un contesto diverso con alcune modifiche. Questa realizzazione è ciò che ri-attiva il ciclo iterativo.

Da qui deriva gran parte della generalizzazione alla base di un algoritmo. E, come ha affermato Robert Harvey, questo esteso ciclo iterativo è il luogo da cui provengono i pattern software.

È equivalente a dire "Ho risolto foo con questo, e se risolvo un po 'questa soluzione potrei risolvere anche bar ." E poi questo potenzialmente si estende alla risoluzione di baz e così via pure. Risolvi abbastanza sfide con l'approccio e diventa generalizzabile come un algoritmo o un modello.

How long does that take?

Tutto dipende dalla natura del problema, dalle soluzioni disponibili e dagli strumenti utilizzati per affrontare il problema.

Per aiutare a chiarire il passo 2 nell'approccio generale: questo è il motivo per cui un sacco di duro lavoro e ispirazione vanno nella creazione di un algoritmo . I tuoi primi tentativi di risolvere il problema probabilmente falliranno o non saranno così eleganti.

Ma inizi con "bene, come potrei suddividere quel problema e risolverlo?" Ricorda che un algoritmo è un approccio passo-passo alla risoluzione di un problema. Quindi interrompo il problema in passaggi e vedi come questo approccio risolve il problema. Tieni presente inoltre che Risoluzione dei problemi è un ampio campo di ricerca. Alcuni metodi hanno più successo di altri e, a volte, è l'approccio non ortodosso a sviluppare l'elegante soluzione.

    
risposta data 04.12.2013 - 17:46
fonte
4

Creare qualcosa di nuovo e meglio di solito richiede un lampo di intuizione che non può essere insegnato o spiegato, ma ci sono cose che puoi fare per aiutarti:

  • Comprendi il lavoro degli altri. Inizia con corsi universitari o libri di testo sugli algoritmi. Cerca documenti, blog, risposte Stack Exchange o codice open source per problemi simili.
  • Determina la migliore complessità teorica asintotica. Quando superi questa complessità, saprai che c'è margine di miglioramento.
  • Lavagna bianca Disegna diagrammi, elenchi e problemi. Pensa a come un essere umano risolverebbe il problema manualmente. Non limitarti a inserire il codice.
  • Esperimento. Prova diverse strutture di dati. Prova a lavorare al contrario dall'ovvia risposta. Prova a preelaborare alcuni dati per renderlo più veloce con cui lavorare. Prova a suddividere il problema in passaggi più semplici. Prova tecniche diverse dagli algoritmi esistenti.
  • Raffinamento continuo. Il campione mondiale di scacchi di 27 anni, Emanuel Lasker, ha dichiarato: "Quando vedi una buona mossa, aspetta, cercane una migliore". Trova le parti che non ti piacciono del tuo algoritmo e rendilo migliore.
risposta data 04.12.2013 - 18:23
fonte
1

Lo sviluppo dell'algoritmo è un problema fondamentale e in quanto tale è un argomento popolare nella comunità di ricerca.

Le persone molto specializzate con un strong background matematico stanno lavorando per risolvere nuovi problemi o migliorare quelli vecchi. Inoltre, un buon algoritmo può essere un vantaggio significativo per alcune società di software e non è necessario un sacco di soldi per sperimentare in questo campo.

Quindi hai un esercito di persone brillanti che pubblicano articoli sperando di diventare famosi e utilizzando tutto ciò che altri stanno scoprendo e facile da usare, quasi in ambienti di lavoro gratuiti per eseguire tutti i test di cui hanno bisogno.

Per ogni soluzione / miglioramento pubblicato, ci sarà un certo numero di persone che si chiedono:

  • posso fare meglio di questo?
  • come posso usarlo per risolvere altri miei problemi?

Questo processo dura da anni e coinvolge un sacco di persone (anche se non interagiscono direttamente)

    
risposta data 04.12.2013 - 18:04
fonte
1

Molte volte è possibile adattare algoritmi esistenti o mettere insieme altri algoritmi.

Ordina rapidamente, ad esempio, dove qualcuno si è reso conto di poter suddividere un problema in insiemi più piccoli e utilizzare metodi di ordinamento più efficienti con insiemi di piccole dimensioni. Tuttavia, utilizza solo algoritmi preesistenti per l'ordinamento degli elementi.

L'uso di alberi quad per indicizzare la geografia, collega tra loro strutture dati algoritmiche preesistenti, ma le applica a un nuovo problema.

Quindi, mentre alcuni algoritmi sono veramente innovativi, un sacco di "innovazione" non è altro che la realizzazione di uno strumento esistente che si adatta bene a un determinato problema. Quindi, se vuoi sviluppare algoritmi, dovresti avere familiarità con altri algoritmi esistenti.

    
risposta data 04.12.2013 - 18:27
fonte

Leggi altre domande sui tag