Algoritmi: costi di calcolo e euristica successiva - manichini

Spesso, trovi che un approccio euristico, che si basi sull'auto-scoperta e produce risultati sufficientemente utili (non necessariamente ottimali, ma abbastanza buoni) è il metodo che è effettivamente necessario per risolvere un problema. Ottenere l'algoritmo per eseguire parte del lavoro richiesto consente di risparmiare tempo e fatica perché è possibile creare algoritmi che vedano i modelli meglio degli umani.

Di conseguenza, l'auto-scoperta è il processo che consente all'algoritmo di mostrarti un percorso potenzialmente utile per una soluzione (ma devi comunque contare sull'intuizione umana e sulla comprensione per sapere se la soluzione è quella giusta). Le sezioni seguenti descrivono le tecniche che è possibile utilizzare per calcolare il costo di un algoritmo utilizzando l'euristica come metodo per scoprire l'effettiva utilità di una determinata soluzione.

Rappresentazione del problema come spazio

Uno spazio di problemi è un ambiente in cui avviene la ricerca di una soluzione. Un insieme di stati e gli operatori utilizzati per modificare quegli stati rappresentano lo spazio del problema. Ad esempio, considera un gioco di tessere con otto tessere in una cornice 3 x 3. Ogni tessera mostra una parte di un'immagine e le tessere iniziano in ordine casuale in modo che l'immagine sia criptata. L'obiettivo è spostare una tessera alla volta per posizionare tutte le tessere nel giusto ordine e rivelare l'immagine.

La combinazione dello stato iniziale, dei riquadri randomizzati e dello stato obiettivo - le tessere in un ordine particolare - è l'istanza del problema. È possibile rappresentare graficamente il puzzle utilizzando un grafico dello spazio dei problemi. Ogni nodo del grafico dello spazio del problema presenta uno stato (le otto tessere in una posizione particolare). I bordi rappresentano operazioni, come spostare il numero di tessere otto su. Quando muovi la tessera otto su, l'immagine cambia - passa a un altro stato.

Vincere il gioco passando dallo stato di partenza allo stato di obiettivo non è l'unica considerazione. Per risolvere il gioco in modo efficiente, è necessario eseguire l'attività nel minor numero di mosse possibili, il che significa usare il minor numero di operatori. Il numero minimo di mosse utilizzate per risolvere il puzzle è la profondità del problema.

È necessario considerare diversi fattori quando si rappresenta un problema come spazio. Ad esempio, è necessario considerare il numero massimo di nodi che si adatta alla memoria, che rappresenta la complessità dello spazio. Quando non è possibile inserire tutti i nodi nella memoria in una volta, il computer deve memorizzare alcuni nodi in altre posizioni, come il disco rigido, che può rallentare considerevolmente l'algoritmo.Per determinare se i nodi si adattano alla memoria, è necessario considerare la complessità temporale, che è il numero massimo di nodi creati per risolvere il problema. Inoltre, è importante considerare il fattore di diramazione, che è il numero medio di nodi creati nel grafico dello spazio del problema per risolvere un problema.

Andare a caso ed essere benedetti dalla fortuna

Risolvere un problema di ricerca usando tecniche a forza bruta è possibile. Il vantaggio di questo approccio è che non è necessaria alcuna conoscenza specifica del dominio per utilizzare uno di questi algoritmi. Un algoritmo a forza bruta tende a utilizzare l'approccio più semplice possibile per risolvere il problema. Lo svantaggio è che un approccio a forza bruta funziona bene solo per un piccolo numero di nodi. Ecco alcuni degli algoritmi di ricerca di forza bruta più comuni:

• Ricerca in ampiezza: Questa tecnica inizia dal nodo radice, esplora prima ciascuno dei nodi figlio e solo dopo passa al livello successivo. Progredisce livello per livello fino a quando non trova una soluzione. Lo svantaggio di questo algoritmo è che deve memorizzare ogni nodo in memoria, il che significa che utilizza una notevole quantità di memoria per un gran numero di nodi. Questa tecnica può verificare la presenza di nodi duplicati, risparmiando tempo e sempre con una soluzione.
• Ricerca approfondita: Questa tecnica inizia dal nodo radice ed esplora una serie di nodi figlio connessi fino a raggiungere un nodo foglia. Progredisce ramo dopo ramo finché non trova una soluzione. Lo svantaggio di questo algoritmo è che non può controllare i nodi duplicati, il che significa che potrebbe attraversare gli stessi percorsi dei nodi più di una volta. In effetti, questo algoritmo potrebbe non trovare affatto una soluzione, il che significa che è necessario definire un punto limite per mantenere l'algoritmo dalla ricerca infinita. Un vantaggio di questo approccio è che è efficiente in termini di memoria.
• Ricerca bidirezionale: Questa tecnica esegue la ricerca simultanea dal nodo radice e dal nodo obiettivo finché i due percorsi di ricerca non si incontrano nel mezzo. Un vantaggio di questo approccio è che è efficiente nel tempo perché trova la soluzione più veloce di molte altre soluzioni a forza bruta. Inoltre, utilizza la memoria in modo più efficiente rispetto ad altri approcci e trova sempre una soluzione. Il principale svantaggio è la complessità dell'implementazione, che si traduce in un ciclo di sviluppo più lungo.

Uso di una funzione euristica e di un costo

Per alcune persone, la parola euristica sembra complicata. Sarebbe altrettanto semplice dire che l'algoritmo fa un'ipotesi e poi ci riprova quando fallisce. A differenza dei metodi a forza bruta, gli algoritmi euristici apprendono. Usano anche le funzioni di costo per fare scelte migliori. Di conseguenza, gli algoritmi euristici sono più complessi, ma hanno un netto vantaggio nella risoluzione di problemi complessi. Come con gli algoritmi a forza bruta, ci sono molti algoritmi euristici e ognuno ha una propria serie di vantaggi, svantaggi e requisiti speciali. L'elenco seguente descrive alcuni dei più comuni algoritmi euristici:

• Ricerca euristica pura: L'algoritmo espande i nodi in ordine di costo.Mantiene due liste. La lista chiusa contiene i nodi che ha già esplorato; la lista aperta contiene i nodi che deve ancora esplorare. In ogni iterazione, l'algoritmo espande il nodo con il costo più basso possibile. Tutti i nodi figlio vengono inseriti nell'elenco chiuso e vengono calcolati i costi dei singoli nodi figlio. L'algoritmo invia i nodi figli con un costo ridotto alla lista aperta ed elimina i nodi figlio con un costo elevato. Di conseguenza, l'algoritmo esegue una ricerca intelligente e basata sui costi per la soluzione.
• A * search: L'algoritmo tiene traccia del costo dei nodi mentre li esplora utilizzando l'equazione: f (n) = g (n) + h (n), dove
  • n è l'identificativo del nodo.
  • g (n) è il costo per raggiungere il nodo finora.
  • h (n) è il costo stimato per raggiungere l'obiettivo dal nodo.
  • f (n) è il costo stimato del percorso da n all'obiettivo.

L'idea è di cercare prima i percorsi più promettenti ed evitare percorsi costosi.

• Greedy best-first search: L'algoritmo sceglie sempre il percorso più vicino all'obiettivo utilizzando l'equazione: f (n) = h