La modification de cette 8-puzzle code pour imprimer les états intermédiaires à atteindre la solution

Sur les 8 Puzzle Problème

//Largeur de la Première Utilisation de la Recherche dans la commune de Huit Puzzle Problème.

import java.util.*;
class EightPuzzle {
Queue<String> q = new LinkedList<String>();    //Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
Map<String,Integer> map = new HashMap<String, Integer>(); //HashMap is used to ignore repeated nodes
public static void main(String args[]){
String str="087465132";                 //Input the Board State as a String with 0 as the Blank Space
EightPuzzle e = new EightPuzzle();      //New Instance of the EightPuzzle
e.add(str,0);                           //Add the Initial State
while(e.q.peek()!=null){
e.up(e.q.peek());                   //Move the blank space up and add new state to queue
e.down(e.q.peek());                 //Move the blank space down
e.left(e.q.peek());                 //Move left
e.right(e.q.remove());              //Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new string to the Map and Queue
void add(String str,int n){
if(!map.containsKey(str)){
map.put(str,n);
q.add(str);
}
}
/* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(String str){
int a = str.indexOf("0");
if(a>2){
String s = str.substring(0,a-3)+"0"+str.substring(a-2,a)+str.charAt(a-3)+str.substring(a+1);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void down(String str){
int a = str.indexOf("0");
if(a<6){
String s = str.substring(0,a)+str.substring(a+3,a+4)+str.substring(a+1,a+3)+"0"+str.substring(a+4);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void left(String str){
int a = str.indexOf("0");
if(a!=0 && a!=3 && a!=6){
String s = str.substring(0,a-1)+"0"+str.charAt(a-1)+str.substring(a+1);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void right(String str){
int a = str.indexOf("0");
if(a!=2 && a!=5 && a!=8){
String s = str.substring(0,a)+str.charAt(a+1)+"0"+str.substring(a+2);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
}

Je veux modifier le code pour qu'il imprime les états intermédiaires utilisés pour atteindre la solution, au lieu de dire le niveau sur lequel la solution a été atteint.

Par exemple, étant donné ce conseil

1 4 2
3 0 5
6 7 8

(sous forme de Chaîne 142305678)

Je veux imprimer:

1 4 2
3 0 5
6 7 8

(comme la Chaîne 142305678)

1 0 2
3 4 5
6 7 8

(comme la Chaîne 102345678)

0 1 2
3 4 5
6 7 8

(comme la Chaîne 012345678)

En regardant le code, je crois que c'intermédiaire de chaînes se sont stockées par le biais de la méthode add dans la File d'attente:

void add(String str,int n){
if(!map.containsKey(str)){
map.put(str,n);
q.add(str);
}
}

Je n'ai aucune expérience de travail avec table de hachage, comment pourrais-je regarder dans les états intermédiaires qui y sont stockées?

InformationsquelleAutor andandandand | 2009-12-10
  1. 4

    Voici comment j'ai résolu votre requête pour obtenir la piste reliant commencer à objectif:

    1. Organisé les importations de rendre explicite ce qui l'utilitaire de classes sont utilisés.
    2. Renommé les variables afin d'en clarifier le sens/le rôle de chacun.
    3. Ajouté le stateHistory carte d'associer chaque état à son prédécesseur.
    4. Refait la copie de l'achèvement-vérifier le code de chaque méthode de mouvement dans un checkCompletion méthode.
    5. Modifié le add méthode pour prendre de nouveaux et anciens états (intériorisé la profondeur de recherche à cette méthode) et pour maintenir la stateHistory carte ainsi que l' stateDepth carte et agenda file d'attente.
    6. Modifié le checkCompletion méthode à pied de la stateHistory arrière de l'objectif d'état (une fois) à l'état d'origine (celle qui n'a aucun prédécesseur).

    L'exécution de la modification du code produit de cette sortie:

    Solution Exists at Level 28 of the tree
123456780 at 28
123450786 at 27
120453786 at 26
102453786 at 25
152403786 at 24
152043786 at 23
152743086 at 22
152743806 at 21
152743860 at 20
152740863 at 19
150742863 at 18
105742863 at 17
145702863 at 16
145072863 at 15
045172863 at 14
405172863 at 13
475102863 at 12
475162803 at 11
475162083 at 10
475062183 at 9
475602183 at 8
475682103 at 7
475682130 at 6
475680132 at 5
470685132 at 4
407685132 at 3
487605132 at 2
487065132 at 1
087465132 at 0

    Modification d'imprimer la séquence de avant la commande (démarrer-à-objectif, plutôt que vers l'arrière de l'objectif-à-start) est laissée en exercice de l'étudiant.

    import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class EightPuzzle {
Queue<String> agenda = new LinkedList<String>();    //Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
Map<String,Integer> stateDepth = new HashMap<String, Integer>(); //HashMap is used to ignore repeated nodes
Map<String,String> stateHistory = new HashMap<String,String>(); //relates each position to its predecessor
public static void main(String args[]){
String str="087465132";                                 //Input the Board State as a String with 0 as the Blank Space
EightPuzzle e = new EightPuzzle();              //New Instance of the EightPuzzle
e.add(str, null);                                                   //Add the Initial State
while(!e.agenda.isEmpty()){
String currentState = e.agenda.remove();
e.up(currentState);                                       //Move the blank space up and add new state to queue
e.down(currentState);                                     //Move the blank space down
e.left(currentState);                                     //Move left
e.right(currentState);                          //Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new string to the Map and Queue
void add(String newState, String oldState){
if(!stateDepth.containsKey(newState)){
int newValue = oldState == null ? 0 : stateDepth.get(oldState) + 1;
stateDepth.put(newState, newValue);
agenda.add(newState);
stateHistory.put(newState, oldState);
}
}
/* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(String currentState){
int a = currentState.indexOf("0");
if(a>2){
String nextState = currentState.substring(0,a-3)+"0"+currentState.substring(a-2,a)+currentState.charAt(a-3)+currentState.substring(a+1);
checkCompletion(currentState, nextState);
}
}
void down(String currentState){
int a = currentState.indexOf("0");
if(a<6){
String nextState = currentState.substring(0,a)+currentState.substring(a+3,a+4)+currentState.substring(a+1,a+3)+"0"+currentState.substring(a+4);
checkCompletion(currentState, nextState);
}
}
void left(String currentState){
int a = currentState.indexOf("0");
if(a!=0 && a!=3 && a!=6){
String nextState = currentState.substring(0,a-1)+"0"+currentState.charAt(a-1)+currentState.substring(a+1);
checkCompletion(currentState, nextState);
}
}
void right(String currentState){
int a = currentState.indexOf("0");
if(a!=2 && a!=5 && a!=8){
String nextState = currentState.substring(0,a)+currentState.charAt(a+1)+"0"+currentState.substring(a+2);
checkCompletion(currentState, nextState);
}
}
private void checkCompletion(String oldState, String newState) {
add(newState, oldState);
if(newState.equals("123456780")) {
System.out.println("Solution Exists at Level "+stateDepth.get(newState)+" of the tree");
String traceState = newState;
while (traceState != null) {
System.out.println(traceState + " at " + stateDepth.get(traceState));
traceState = stateHistory.get(traceState);
}
System.exit(0);
}
}
}
    • "Merci" pour faire ses devoirs pour lui. Je suis sûr que c'est dans son intérêt à long terme ... PAS.
    • Je suis en train d'essayer de résoudre 8-puzzle problème au moyen de l'algorithme A*. Est-il possible pour vous de s'il vous plaît regardez dans ma question ici stackoverflow.com/questions/13053455/... . Personne n'a répondu jusqu'à présent. Ce n'est PAS mes devoirs ou quelque chose. Je ne suis demander ce parce que vous avez répondu à une question sur 8-puzzle et vous permettrait de comprendre le code plus facilement. Je vous remercie.
    InformationsquelleAutor joel.neely
  2. 0

    En fait, la solution semble être stockées dans la file d'attente. La carte est uniquement utilisé pour détecter plusieurs états.

    Quand il est terminé, pop chaque élément de la file d'attente et l'imprimer.

    • Je l'ai fait en plaçant: while(!q.isEmpty()){ System.out.println(q.poll()); } dans chaque direction méthode lorsque la solution est trouvée et a obtenu trop inutile Cordes, je pense que j'ai besoin d'accéder à la table de hachage.
    • Qu'entendez-vous par "inutile chaînes"?
    • Je veux dire des mesures qui n'étaient pas ceux utilisés pour arriver à la solution.
    • Ce code ressemble à supprimer des éléments de la file d'attente lorsqu'il est établi qu'ils sont des culs-de-sac. Il ne semble "prendre le long chemin" pour aller quelque part, mais il doit produire une solution viable, sans retour en arrière.
    InformationsquelleAutor Anon.
  3. 0

    Une petite amélioration à Joel Neely version: initialisation e.stateDepth.put(null, -1); simplifie la logique dans la méthode add, int newValue = stateDepth.get(oldState) + 1;.

    • Vous avez raison; il est préférable de pousser la décision de la normale-code cas.
    InformationsquelleAutor trashgod
  4. 0

    Vous avez juste besoin d'ajouter une ligne de code pour imprimer les états intermédiaires.
    Dans la fonction ajouter, insérer le code

        System.out.println(str+" "+ "level"+map.get(str));

    L'ensemble du code ressemblera à ceci.

        import java.util.*;
class EightPuzzle {
Queue<String> q = new LinkedList<String>();    //Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
Map<String,Integer> map = new HashMap<String, Integer>(); //HashMap is used to ignore repeated nodes
public static void main(String args[]){
String str="087465132";                 //Input the Board State as a String with 0 as the Blank Space
EightPuzzle e = new EightPuzzle();      //New Instance of the EightPuzzle
e.add(str,0);                           //Add the Initial State
while(e.q.peek()!=null){
e.up(e.q.peek());                   //Move the blank space up and add new state to queue
e.down(e.q.peek());                 //Move the blank space down
e.left(e.q.peek());                 //Move left
e.right(e.q.remove());              //Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new string to the Map and Queue
void add(String str,int n){
if(!map.containsKey(str)){
map.put(str,n);
q.add(str);
System.out.println(str+" "+ "level"+map.get(str));
}
}
/* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(String str){
int a = str.indexOf("0");
if(a>2){
String s = str.substring(0,a-3)+"0"+str.substring(a-2,a)+str.charAt(a-3)+str.substring(a+1);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void down(String str){
int a = str.indexOf("0");
if(a<6){
String s = str.substring(0,a)+str.substring(a+3,a+4)+str.substring(a+1,a+3)+"0"+str.substring(a+4);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void left(String str){
int a = str.indexOf("0");
if(a!=0 && a!=3 && a!=6){
String s = str.substring(0,a-1)+"0"+str.charAt(a-1)+str.substring(a+1);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void right(String str){
int a = str.indexOf("0");
if(a!=2 && a!=5 && a!=8){
String s = str.substring(0,a)+str.charAt(a+1)+"0"+str.substring(a+2);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
}

    La sortie ressemble à ceci.sortie

    Cependant, il imprime aussi les états qui ne contribuent pas à atteindre l'objectif de l'état.

    InformationsquelleAutor Rajshree Rai