S'enregistrer | Rechercher | FAQ | Liste des Membres | Groupes d'utilisateurs | Connexion

  Nom d'utilisateur:    Mot de passe:       

  

Poster un nouveau sujet   Répondre au sujet Page 1 sur 1
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
MessagePosté le: Mer Avr 14, 2010 12:53 am    Sujet du message: Un taquin en java avec un parcours en largeur ! Répondre en citant

S
Projets


 
Inscrit le: 27 Mar 2008
Messages: 271



Salut,
je poste ici ma solution du taquin en java avec un parcours en largeur c'est loin d'être la solution la plus optimal mais c'est une résolution par essaye de tous les possibilité sans surcharge dans un arbre. Plus tard je posterais une solution avec l'algorithme A* un classique en IA.

Code:

package taquin_;

import java.util.*;
import java.io.*;

public class taquin {
//les attributs

    private char[] taq = {'7', '2', '3', '8', '1', '5', '4', '6', '0'};
    private char[] but = {'1', '2', '3', '8', '0', '4', '7', '6', '5'};
    private char[] last_coup = {'0', '0', '0', '0', '0', '0', '0', '0', '0'};

    private char[] o;
    private boolean trouver = false;
    private int pro = 0;
    private int nbnd = 0;
//2liste de string open et close
    private LinkedList open = new LinkedList();
    private LinkedList close = new LinkedList();
    private int po;

    //les methodes
    public taquin() {//initaliser la liste et les attributs
        open.add(taq);
        po = 0;
    }

// deplacemnet de case dans le taquin
    void deplacer() {

        while (!open.isEmpty() && !trouver) {
            o = (char[]) open.get(0);
            open.remove();
            veribut(o);
            if (verf(close.iterator(), o) != true && !trouver) {
                close.add(o);
                for (int i = 0; i < o.length; i++) {
                    if (o[i] == '0') {
                        po = i;
                        break;
                    }
                }
                switch (po) {
                    case 0: {
                        perm(o, po, 1);
//                affi1(o);
                        perm(o, po, 3);

//                affi1(o);
                        break;
                    }
                    case 1: {
                        perm(o, po, 0);

//                affi1(o);
                        perm(o, po, 2);

//                affi1(o);
                        perm(o, po, 4);

//                affi1(o);
                        break;
                    }
                    case 3: {
                        perm(o, po, 0);

//                affi1(o);
                        perm(o, po, 4);

//                affi1(o);
                        perm(o, po, 6);

//                affi1(o);
                        break;
                    }
                    case 2: {
                        perm(o, po, 1);

//                affi1(o);
                        perm(o, po, 5);

//                affi1(o);
                        break;
                    }
                    case 4: {
                        perm(o, po, 1);
//                affi1(o);
                        perm(o, po, 3);

//                affi1(o);
                        perm(o, po, 5);

//                affi1(o);
                        perm(o, po, 7);

//                affi1(o);
                        break;
                    }
                    case 5: {
                        perm(o, po, 2);

//                affi1(o);
                        perm(o, po, 4);

//                affi1(o);
                        perm(o, po, 8);

//                affi1(o);
                        break;
                    }
                    case 6: {
                        perm(o, po, 3);

//                affi1(o);
                        perm(o, po, 7);

//                affi1(o);
                        break;
                    }
                    case 7: {
                        perm(o, po, 6);

//                affi1(o);
                        perm(o, po, 4);

//                affi1(o);
                        perm(o, po, 8);

//                affi1(o);
                        break;
                    }
                    case 8: {
                        perm(o, po, 7);

//                affi1(o);
                        perm(o, po, 5);

//                affi1(o);
                        break;
                    }
                    default:
                        break;
                }
            }

        }
        if (trouver) {
            System.out.println("" + close.size());
            System.out.println("solution trouver avec une profondeur de " + pro);
            System.out.println("on a generďż˝  " + nbnd + " noeuds");
        } else {
            if (open.isEmpty()) {
                System.out.println("pas de solution ");
            }
        }
    }

//fonction qui verifier si l'etat existe dans la liste close
    public boolean verf(Iterator b, char[] a) {
        boolean test = false;
        char[] tes;
        int i;

        while (b.hasNext()) {
            tes = (char[]) b.next();
            for (i = 0; i < a.length; i++) {
                if (a[i] != tes[i]) {
                    break;
                }
            }
            if (i > 8) {
                test = true;
                continue;
            }
        }
        return (test);
    }

//la fonction qui permute 2 cases
    public void perm(char[] s, int a, int b) {
        char x;
        char[] w = {'0', '0', '0', '0', '0', '0', '0', '0', '0'};
        for (int i = 0; i < s.length; i++) {
            w[i] = s[i];
        }

        x = w[a];
        w[a] = w[b];
        w[b] = x;
        nbnd++;
        open.add(w);
    }
//verifier si le but est atteint
    public void veribut(char[] ob) {
        int i;
        for (i = 0; i < ob.length; i++) {
            if (ob[i] != but[i]) {
                break;
            }
        }
        if (i > 8) {
            trouver = true;
        }

    }

    public void affi1(char[] ofin) {
        int i;
        int j;
        int e = 0;
        System.out.println("");
        System.out.println("");
        for (i = 0; i <= 2; i++) {
            for (j = 0; j <= 2; j++) {
                if (ofin[e] == 0) {
                    System.out.print("| |");
                } else {
                    System.out.print("|" + ofin[e] + "|");
                }
                e++;
            }
            System.out.println("");
        }
    }
    public static void main (String[] args){

//   new Fenetre();/*
    taquin ta=new taquin();
    long debut=new Date().getTime();
    System.out.println("traitement en cours...");
    ta.deplacer();
    long fin=new Date().getTime();
    System.out.println("le temps ecouler pour l'execution est "+(fin -debut)+"mills");
}
}



J'ai pas trouvé aussi ou placer mon pro c'est la variable de la profondeur, mon problème et que je simule l'existence d'un arbre donc j'ai pas de point observable ou je sais que j'ai changé de niveau dans l'arbre; si quelqu'un a une idée je suis preneur ^^
Voir le profil de l'utilisateur Envoyer un message privés
Poster un nouveau sujet   Répondre au sujet Page 1 sur 1

  


 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum



129144 Attacks blocked