Heurística para deslizar problema telha

Question

A idéia é mover todos os elementos certos para a esquerda e da esquerda para a direita com um espaço vazio no meio. Os elementos podem saltar mais de uma ou duas peças para um espaço vazio.

LLL[ ]RRR

Eu estou tentando pensar em uma heurística para esta tarefa. É a heurística concebido para ajudar a encontrar uma solução possível, ou realmente retornar uma série de movimentos como a solução? Como eu poderia expressar tal heurística?

Answer 1

Parece que você está um pouco confuso sobre o que uma heurística é.

A definição áspera é "uma hipótese simplificadora" ou "um palpite decente"

Por exemplo, digamos que você tem que montar um time de basquete, e você tem fichas técnicas sobre as pessoas que querem jogar essa lista suas informações de contato, data de nascimento, e altura. Você poderia prender tryouts onde você testar habilidades específicas de cada candidato; que exigiria trazendo todos os candidatos, porém, e isso pode levar um longo tempo. Você usa uma heurística para restringir a pesquisa - chamada apenas as pessoas que são, pelo menos, 6'2" de altura Isso pode ignorar alguns grandes jogadores de basquete, mas é uma suposição bastante decente

..

Um outro exemplo de uma heurística: você está tentando usar o menor número de moedas para pagar uma conta. A heurística (a abordagem da simplificação) é escolher a moeda com o maior valor (que é menor do que o projeto de lei restante) em primeiro lugar, subtrair o valor da conta, e repita. Isto não é garantido que funcione cada vez, mas vai chegar ao bairro direito a maior parte do tempo.

Uma heurística para o seu problema pode ser "nunca se movem Ls para a direita, e nunca mover Rs à esquerda." - ela restringe o "espaço de busca" de todos os movimentos possíveis, eliminando algumas das possibilidades, desde o início

Answer 2

Você está procurando uma heurística ou um algoritmo? A heurística pode ou não pode resolver um determinado problema. É realmente apenas a intenção de apontar na direção que a solução reside provavelmente no. Um algoritmo realmente deve resolver um determinado problema.

Answer 3

Uma heurística é geralmente uma "dica" que geralmente (mas nem sempre) irá orientar o seu procedimento para a direção correta. Usando heurística acelera os procedimentos de (seus algoritmos), mais uma vez, normalmente , mas nem sempre. É como um "conselho" para o algoritmo que é correta na maioria das vezes.

Eu não sei o que você está procurando, como a descrição é um pouco vago. Se quiser que o algoritmo, você vai precisar para estudar o efeito que um movimento particular terá à situação atual e uma forma de avanço para todos os movimentos possíveis de cada vez, com efeito percorrendo uma árvore de estados (ie. Estados que irão evoluir se você faz uma determinada seqüência de jogadas).

Você também pode ver que ele possivelmente importa quão perto a posição atual é o que você quer alcançar (a sua posição final desejada) .Assim em vez de calcular todos os caminhos possíveis a partir de seu estado inicial até você encontrar o estado final, você pode orientar o seu algoritmo baseado na heurística "quão perto é o estado atual para o desejado" e só atravessar uma parte da árvore.