Heurística para el problema del azulejo deslizante

Question

La idea es mover todos los elementos derechos hacia la izquierda y la izquierda hacia la derecha con un espacio vacío en el medio. Los elementos pueden saltar sobre una o dos piezas en un espacio vacío.

LLL[ ]RRR

Estoy tratando de pensar en una heurística para esta tarea. ¿La heurística está destinada a ayudar a encontrar una posible solución, o en realidad devuelve una serie de movimientos como la solución? ¿Cómo expresaría tal heurística?

Answer 1

Parece que estás un poco confundido acerca de lo que es una heurística.

Una definición aproximada es " una suposición simplificadora " o "una conjetura decente"

Por ejemplo, supongamos que tiene que armar un equipo de baloncesto, y tiene hojas informativas sobre las personas que quieren jugar que incluyen su información de contacto, fecha de nacimiento y altura. Puede realizar pruebas en las que evalúa las habilidades específicas de cada candidato; eso requeriría traer a todos los candidatos, sin embargo, y eso podría llevar mucho tiempo. Utiliza una heurística para limitar la búsqueda: solo llame a personas que midan al menos 6'2 '' alto. Esto podría ignorar a algunos grandes jugadores de baloncesto, pero es una suposición bastante decente.

Otro ejemplo de una heurística: está intentando usar la menor cantidad de monedas para pagar una factura. La heurística (un enfoque simplificador) es elegir primero la moneda con el mayor valor (que es menor que el billete restante), restar el valor del billete y repetir. No se garantiza que funcione siempre, pero lo llevará al vecindario correcto la mayor parte del tiempo.

Una heurística para su problema podría ser "nunca mover Ls a la derecha, y nunca mover Rs a la izquierda". - limita el " espacio de búsqueda " de todos los movimientos posibles eliminando algunas de las posibilidades desde el principio.

Answer 2

¿Estás buscando una heurística o un algoritmo? Una heurística puede o no resolver un problema dado. Realmente solo pretende señalarle en la dirección en la que probablemente se encuentra la solución. Un algoritmo realmente debería resolver un problema dado.

Answer 3

Una heurística es generalmente una "pista" que generalmente (pero no siempre) guiará su procedimiento en la dirección correcta. El uso de la heurística acelera sus procedimientos (sus algoritmos), nuevamente, generalmente , pero no siempre. Es como un '' consejo '' al algoritmo que es correcto la mayoría de las veces.

No estoy seguro de lo que estás buscando, ya que la descripción es un poco vaga. Si desea el algoritmo, necesitará estudiar qué efecto tendrá un movimiento en particular en la situación actual y una forma de avanzar para todos los movimientos posibles cada vez, atravesando un árbol de estados (es decir, estados que evolucionarán si haces una secuencia particular de movimientos).

También puede ver que posiblemente importa cuán cerca esté la posición actual de lo que desea lograr (su posición final deseada). Entonces, en lugar de calcular todas las rutas posibles desde su estado inicial hasta Si encuentra el estado final, puede guiar su algoritmo en función de la heurística `` qué tan cerca está el estado actual del deseado '' y solo atraviesan una parte del árbol.