Heuristique pour le problème des tuiles coulissantes

Question

L’idée est de déplacer tous les éléments de droite vers la gauche et la gauche vers la droite, avec un espace vide au milieu. Les éléments peuvent soit sauter par-dessus une ou deux pièces dans un espace vide.

LLL[ ]RRR

J'essaie de penser à une heuristique pour cette tâche. L'heuristique est-elle censée aider à trouver une solution possible ou renvoie-t-elle réellement un certain nombre de déplacements comme solution? Comment pourrais-je exprimer une telle heuristique?

Answer 1

On dirait que vous êtes un peu confus sur ce qu'est une heuristique.

Une définition approximative est "une hypothèse simplificatrice". ou "une estimation décente"

Par exemple, supposons que vous deviez constituer une équipe de basket-ball et que vous disposiez de fiches d'informations sur les personnes souhaitant jouer à cette liste répertoriant leurs informations de contact, leur date de naissance et leur taille. Vous pouvez organiser des essais au cours desquels vous testez les compétences spécifiques de chaque candidat. cela nécessiterait cependant la présence de tous les candidats et cela pourrait prendre beaucoup de temps. Vous utilisez une heuristique pour affiner la recherche - appelez uniquement les personnes âgées d’au moins 6'2 " grand. Cela peut ignorer de grands joueurs de basket, mais c'est une hypothèse plutôt décente.

Autre exemple d'heuristique: vous essayez d'utiliser le plus petit nombre de pièces pour payer une facture. L'heuristique (une approche simplificatrice) consiste à choisir en premier la pièce dont la valeur est la plus grande (inférieure à la facture restante), soustrayez la valeur de la facture et répétez l'opération. Cela n’est pas garanti de fonctionner à chaque fois, mais cela vous amènera la plupart du temps dans le bon quartier.

Une heuristique pour votre problème pourrait être "ne déplacez jamais les Ls vers la droite, ni les Rs vers la gauche". - il réduit l'espace de "recherche" " de tous les mouvements possibles en éliminant certaines des possibilités dès le début.

Answer 2

Vous recherchez une heuristique ou un algorithme? Une heuristique peut ou non résoudre un problème donné. Il s’agit en réalité simplement de vous indiquer la direction dans laquelle la solution se trouve. Un algorithme devrait vraiment résoudre un problème donné.

Answer 3

Une heuristique est généralement un "indice". qui généralement (mais pas toujours) guidera votre procédure dans la bonne direction. L'utilisation de l'heuristique accélère vos procédures (vos algorithmes), encore une fois, généralement , mais pas toujours. C'est comme un "conseil". à l'algorithme qui est correct le plus souvent.

Je ne suis pas sûr de ce que vous recherchez, car la description est un peu vague. Si vous souhaitez utiliser l’algorithme, vous devrez étudier les effets d’un mouvement particulier sur la situation actuelle et la manière de procéder pour chaque mouvement possible, en parcourant en fait une arborescence d’états (c’est-à-dire vous effectuez une séquence particulière de mouvements).

Vous pouvez également constater que le rapprochement de la position actuelle par rapport à ce que vous souhaitez atteindre (votre position finale souhaitée) est important. Ainsi, au lieu de calculer tous les chemins possibles de votre vous trouvez l'état final, vous pouvez guider votre algorithme en fonction de l'heuristique "à quel point l'état actuel est-il proche de celui souhaité" et ne traversez qu'une partie de l'arbre.