Un taquin en java avec un parcours en largeur !

Moderator: Mod

Un taquin en java avec un parcours en largeur !

Postby S » Wed Apr 14, 2010 12:53 am

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:1:6a40e2a7a0]
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");
}
}

[/code:1:6a40e2a7a0]

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 ^^
S
Projets
 
Posts: 271
Joined: Thu Mar 27, 2008 2:46 am

Return to Java

Who is online

Users browsing this forum: No registered users and 1 guest

cron