Euristico per il problema delle piastrelle scorrevoli

Question

L'idea è di spostare tutti gli elementi giusti a sinistra e a sinistra a destra con uno spazio vuoto nel mezzo. Gli elementi possono saltare uno o due pezzi in uno spazio vuoto.

LLL[ ]RRR

Sto cercando di pensare a un'euristica per questo compito. L'euristica ha lo scopo di aiutare a trovare una possibile soluzione o effettivamente restituire una serie di mosse come soluzione? Come esprimerei un tale euristico?

Answer 1

Sembra che tu sia un po 'confuso su cosa sia un euristico.

Una definizione approssimativa è "un'ipotesi semplificativa" o "un'ipotesi decente"

Ad esempio, supponiamo che tu debba mettere insieme una squadra di basket e che tu abbia delle schede sulle persone che vogliono giocare in quella lista le loro informazioni di contatto, la data di nascita e l'altezza. Potresti tenere delle prove in cui metti alla prova le abilità specifiche di ciascun candidato; ciò richiederebbe comunque l'inserimento di tutti i candidati e ciò potrebbe richiedere molto tempo. Usi un euristico per restringere la ricerca - chiama solo le persone che sono almeno 6'2 " alto. Questo potrebbe ignorare alcuni grandi giocatori di basket, ma è un'ipotesi abbastanza decente.

Un altro esempio di euristica: stai cercando di utilizzare il minor numero di monete per pagare una fattura. L'euristico (un approccio semplificato) è quello di scegliere prima la moneta con il valore più grande (che è inferiore al conto rimanente), sottrarre il valore dal conto e ripetere. Questo non è garantito per funzionare ogni volta, ma ti porterà nel quartiere giusto per la maggior parte del tempo.

Un'euristica per il tuo problema potrebbe essere " mai spostare Ls a destra e mai spostare Rs a sinistra " - restringe lo "spazio di ricerca" di tutte le mosse possibili eliminando alcune possibilità sin dall'inizio.

Answer 2

Stai cercando un euristico o un algoritmo? Un euristico può o meno risolvere un determinato problema. È proprio destinato a indicarti la direzione in cui probabilmente si trova la soluzione. Un algoritmo dovrebbe davvero risolvere un determinato problema.

Answer 3

Un euristico è generalmente un "suggerimento" che di solito (ma non sempre) guiderà la procedura nella direzione corretta. L'uso dell'euristica accelera le tue procedure (i tuoi algoritmi), di nuovo, di solito , ma non sempre. È come un "consiglio" all'algoritmo che è corretto il più delle volte.

Non sono sicuro di quello che stai cercando, poiché la descrizione è un po 'vaga. Se si desidera l'algoritmo, sarà necessario studiare l'effetto che una determinata mossa avrà sulla situazione attuale e un modo per avanzare di volta in volta per tutte le mosse possibili, attraversando in effetti un albero di stati (ad es. Stati che si evolveranno se fai una particolare sequenza di mosse).

Puoi anche vedere che è probabilmente importante quanto vicino la posizione attuale è ciò che vuoi raggiungere (la tua posizione finale desiderata). Quindi invece di calcolare tutti i possibili percorsi dal tuo stato iniziale fino a trovi lo stato finale, puoi guidare il tuo algoritmo in base all'euristico "quanto è vicino lo stato corrente a quello desiderato" e attraversare solo una parte dell'albero.