Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2735 connectés 

  FORUM HardWare.fr
  Programmation
  Java

  Parcours matrice.

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Parcours matrice.

n°1954409
apaachee
Posté le 02-01-2010 à 00:46:54  profilanswer
 

Bonjour à tous ceux qui prendront la peine de lire mes peines... ^^
 
Je possède une matrice de char constituée de 0 , 'r' , ou 'j'. ('r' = pions rouges et 'j' = pions jaunes, '0' = cases vierges).
 
Je dévellope une IA pour un jeu et j'ai besoin de connaitre le chemin le plus court entre un point (i,j) et le bas ou le haut de ma matrice.
 
En sachant que si je calcule pour les jaunes, les points 'r' sont infranchissables, les points 'j' sont de poids nul et les points '0' sont de cout 1.
 
Les déplacements autorisés sont nord,sud,est,ouest.
 
Je ne pose pas de question sur ce forum sans connaissance de cause, cela fait bientôt 5h que je me renseigne sur les algo de Djiksttra et A*, sans trouver quelque chose de concluant pour mon cas particulier, je n'y comprend pas grand chose.
 
Merci !

mood
Publicité
Posté le 02-01-2010 à 00:46:54  profilanswer
 

n°1954432
Profil sup​primé
Posté le 02-01-2010 à 13:22:42  answer
 

Portant A star va bien pour faire ce que tu souhaites.

n°1954436
apaachee
Posté le 02-01-2010 à 13:59:04  profilanswer
 

Merci de ta réponse =) En fait je sais que Astar est parfait pour mon cas, mais je n'ai aucune idée de comment l'implémenter simplement pour ma matrice toute bête :/

n°1954443
Profil sup​primé
Posté le 02-01-2010 à 14:17:05  answer
 

Ben t'écris tes heuristique et tu les file à A star.
 
C'est quoi qui te pose problème, java, a star, ou les heuristique.
j'y connais rien en java et j'écrirais pas les heuristique pour toi.
Par contre je peux me replonger dans A star et te filer un coup de pouce.

n°1954483
apaachee
Posté le 02-01-2010 à 18:50:55  profilanswer
 

Le mot heuristique m'est étranger :/ Ce qui me pose souci c'est que je connais pas l'algorithme A*, les très nombreux sites que j'ai lu dessus sont un peu complexes pour moi et je ne sais pas comment transformer ma matrice en graphe :/

n°1954487
Profil sup​primé
Posté le 02-01-2010 à 19:16:31  answer
 

apaachee a écrit :

Le mot heuristique m'est étranger :/ Ce qui me pose souci c'est que je connais pas l'algorithme A*, les très nombreux sites que j'ai lu dessus sont un peu complexes pour moi et je ne sais pas comment transformer ma matrice en graphe :/


 
Moi non plus !
Alors là, il faut que t'attende une autre âme charitable parce que je sais faire, mais pas expliquer.
 

n°1954512
apaachee
Posté le 02-01-2010 à 21:31:17  profilanswer
 

Code :
  1. public int eval(char color,int i,int j){
  2.  // System.out.println("----Voici le plateau, on cherche la valeur des points ("+i+","+j+" )------" );
  3.  // this.affichePlateau();
  4.  // System.out.println("----" );
  5.    int result = 0;
  6.    int chemin = 0;
  7.    int optiBas = 100;
  8.    int nbcasestrouvees,no,temI,temJ;
  9.  
  10.    Plateau tempor = new Plateau(nbCases);
  11.    if(color == 'j')
  12.    tempor = this.copieMatrice();
  13.    else{
  14.   tempor = this.rotationMatrice();
  15.   int[] nouveau = cooApresRotation(i,j);
  16.   i = nouveau[0];
  17.   j = nouveau[1];
  18.  }
  19.  
  20.    Stack stackI = new Stack();
  21.    Stack stackJ = new Stack(); 
  22.    Stack somsave = new Stack();
  23.  
  24.    stackI.push(i);
  25.    stackJ.push(j);
  26.    somsave.push(0);
  27.  
  28.    boolean scancomplete = false;
  29.  
  30.    /*CHEMIN BAS*/
  31.     if(j == (nbCases-1)){
  32.   optiBas = 0;
  33.   scancomplete = true;
  34.     }
  35.  
  36.    while(scancomplete == false){
  37.    nbcasestrouvees = 0;
  38.    Integer iCourant = (Integer)stackI.peek();
  39.    Integer jCourant = (Integer)stackJ.peek();
  40.    // System.out.println("-------------" );
  41.    // System.out.println("AfficheStackI" );
  42.    // afficheStack(stackI);
  43.    // System.out.println("--------------" );
  44.    // System.out.println("AffichestackJ" );
  45.    // afficheStack(stackJ);
  46.    // System.out.println("--------------" );
  47.   
  48.    //On cherche les cases à coté de (i,j) étant jaunes ou vierges
  49.    //A droite
  50.    if(iCourant < nbCases-1){ // On évite derniere colonne
  51.    if((tempor.getcase(iCourant+1,jCourant) == color) || (tempor.getcase(iCourant+1,jCourant) == '0')){ // On vérifie que la case = '0' ou 'color'
  52.    if(!dejaPresent(stackI,stackJ,iCourant+1,jCourant)){ // La case n'est pas déja présente dans la pile
  53.       //On a bien une case a droite
  54.       // System.out.println("Case Trouvée a droite" );
  55.       stackI.push(iCourant+1);
  56.       stackJ.push(jCourant);
  57.       nbcasestrouvees++;
  58.    }
  59.    }
  60.    }
  61.    //A gauche
  62.    if(iCourant != 0){
  63.    if((tempor.getcase(iCourant-1,jCourant) == color) || (tempor.getcase(iCourant-1,jCourant) == '0')){
  64.    if(!dejaPresent(stackI,stackJ,iCourant-1,jCourant)){
  65.     // System.out.println("Case Trouvée a gauche" );
  66.       stackI.push(iCourant-1);
  67.       stackJ.push(jCourant);
  68.       nbcasestrouvees++;
  69.    }
  70.    }
  71.    }
  72.    //En haut
  73.    if(jCourant != 0){
  74.    if((tempor.getcase(iCourant,jCourant-1) == color) || (tempor.getcase(iCourant,jCourant-1) == '0')){
  75.    if(!dejaPresent(stackI,stackJ,iCourant,jCourant-1)){
  76.     // System.out.println("Case Trouvée en haut" );
  77.       stackI.push(iCourant);
  78.       stackJ.push(jCourant-1);
  79.       nbcasestrouvees++;
  80.    }
  81.    }
  82.    }
  83.    //En Bas
  84.    if(jCourant < nbCases-1){
  85.    if((tempor.getcase(iCourant,jCourant+1) == color) || (tempor.getcase(iCourant,jCourant+1) == '0')){
  86.    if(!dejaPresent(stackI,stackJ,iCourant,jCourant+1)){
  87.     // System.out.println("Case Trouvée en bas" );
  88.       if(jCourant+1 == nbCases-1){
  89.       nbcasestrouvees = 0;
  90.       chemin = calculnb(stackI,stackJ,somsave);
  91.       // System.out.println("Chemin de "+chemin);
  92.       if(chemin < optiBas)
  93.       optiBas = chemin;
  94.       }
  95.       else{
  96.       stackI.push(iCourant);
  97.       stackJ.push(jCourant+1);
  98.       nbcasestrouvees++;
  99.       }
  100.    }
  101.    }
  102.    }
  103.    // System.out.println("nbcasestrouvees : "+nbcasestrouvees);
  104.    while(nbcasestrouvees > 1){
  105.    somsave.push(nbObj(stackI) - (nbcasestrouvees-1));
  106.    nbcasestrouvees--;
  107.    }
  108.    if(nbcasestrouvees == 0){
  109.    somsave.pop();
  110.    if(somsave.empty())
  111.    scancomplete = true;
  112.    else{
  113.    no = (Integer)somsave.peek();
  114.    while(nbObj(stackI) != (no+1)){
  115.       temI = (Integer)stackI.pop();
  116.       temJ = (Integer)stackJ.pop();
  117.       tempor.setcase(temI,temJ,'-');
  118.    }
  119.    }
  120.    }
  121.    }
  122.  
  123.    /* Chemin HAUT*/
  124.    chemin = 0;
  125.    int optiHaut = 100;
  126.  
  127.    Plateau temp = new Plateau(nbCases);
  128.    if(color == 'j')
  129.    temp = this.copieMatrice();
  130.    else
  131.    temp = this.rotationMatrice();
  132.  
  133.    Stack sstackI = new Stack();
  134.    Stack sstackJ = new Stack(); 
  135.    Stack ssomsave = new Stack();
  136.  
  137.    sstackI.push(i);
  138.    sstackJ.push(j);
  139.    ssomsave.push(0);
  140.  
  141.    scancomplete = false;
  142.  
  143.    if(j == 0){
  144.   scancomplete = true;
  145.   optiHaut = 0;
  146.  }
  147.    while(scancomplete == false){
  148.    nbcasestrouvees = 0;
  149.    Integer siCourant = (Integer)sstackI.peek();
  150.    Integer sjCourant = (Integer)sstackJ.peek();
  151.   
  152.    //On cherche les cases à coté de (i,j) étant jaunes ou vierges
  153.    //En Bas
  154.    if(sjCourant < nbCases-1){
  155.    if((temp.getcase(siCourant,sjCourant+1) == color) || (temp.getcase(siCourant,sjCourant+1) == '0')){
  156.    if(!dejaPresent(sstackI,sstackJ,siCourant,sjCourant+1)){
  157.       sstackI.push(siCourant);
  158.       sstackJ.push(sjCourant+1);
  159.       nbcasestrouvees++;
  160.     
  161.    }
  162.    }
  163.    }
  164.    //A droite
  165.    if(siCourant < nbCases-1){ // On évite derniere colonne
  166.    if((temp.getcase(siCourant+1,sjCourant) == color) || (temp.getcase(siCourant+1,sjCourant) == '0')){ // On vérifie que la case = '0' ou 'color'
  167.    if(!dejaPresent(sstackI,sstackJ,siCourant+1,sjCourant)){ // La case n'est pas déja présente dans la pile
  168.       //On a bien une case a droite
  169.       sstackI.push(siCourant+1);
  170.       sstackJ.push(sjCourant);
  171.       nbcasestrouvees++;
  172.    }
  173.    }
  174.    }
  175.    //A gauche
  176.    if(siCourant != 0){
  177.    if((temp.getcase(siCourant-1,sjCourant) == color) || (temp.getcase(siCourant-1,sjCourant) == '0')){
  178.    if(!dejaPresent(sstackI,sstackJ,siCourant-1,sjCourant)){
  179.       sstackI.push(siCourant-1);
  180.       sstackJ.push(sjCourant);
  181.       nbcasestrouvees++;
  182.    }
  183.    }
  184.    }
  185.    //En haut
  186.    if(sjCourant != 0){
  187.    if((temp.getcase(siCourant,sjCourant-1) == color) || (temp.getcase(siCourant,sjCourant-1) == '0')){
  188.    if(!dejaPresent(sstackI,sstackJ,siCourant,sjCourant-1)){
  189.     if(sjCourant-1 == 0){
  190.       nbcasestrouvees = 0;
  191.       chemin = calculnb(sstackI,sstackJ,ssomsave);
  192.       // System.out.println("Chemin HAUT :"+chemin);
  193.       if(chemin < optiHaut)
  194.       optiHaut = chemin;
  195.       }
  196.       else{
  197.       sstackI.push(siCourant);
  198.       sstackJ.push(sjCourant-1);
  199.       nbcasestrouvees++;
  200.       }
  201.    }
  202.    }
  203.    }
  204.   
  205.    while(nbcasestrouvees > 1){
  206.    ssomsave.push(nbObj(sstackI) - (nbcasestrouvees-1));
  207.    nbcasestrouvees--;
  208.    }
  209.    if(nbcasestrouvees == 0){
  210.    ssomsave.pop();
  211.    if(ssomsave.empty()){
  212.    scancomplete = true;
  213.    // if(optiHaut == 0)
  214.       // optiHaut = -1000;
  215.    }
  216.    else{
  217.    no = (Integer)ssomsave.peek();
  218.    while(nbObj(sstackI) != (no+1)){
  219.       temI = (Integer)sstackI.pop();
  220.       temJ = (Integer)sstackJ.pop();
  221.       temp.setcase(temI,temJ,'-');
  222.    }
  223.    }
  224.    }
  225.    }
  226.  int opti;
  227.  if((optiBas == 0) && (optiHaut == 0))
  228.   opti = -1000;
  229.  else
  230.   opti = (optiBas + optiHaut)*(-1);
  231.  // System.out.println("OptiBas : "+optiBas+" + " );
  232.  // System.out.println("OptiHaut : "+optiHaut+" DONC " );
  233.  
  234.  System.out.println("Opti : "+opti);
  235.  if(opti<-15){
  236.   System.out.println("----Voici le plateau, on cherche la valeur des points ("+i+","+j+" ) Couleur : "+color+"------" );
  237.   temp.affichePlateau();
  238.   System.out.println("----" );
  239.   System.out.println("OptiBas : "+optiBas+" + " );
  240.   System.out.println("OptiHaut : "+optiHaut);
  241.   System.out.println("-----------------------------------------------------------------" );
  242.  }
  243.    return opti;
  244. }


 
J'ai fait un algo (assez lourd j'en conviens) pour le problème que dois traiter. En bref je cherche le chemin le plus court du point (i,j) au bas de la matrice, puis au haut. Etant au coeur du problème depuis maintenant une 20e d'heure, mes explications peuvent paraître légères, si besoin de détailler quelquechose j'y suis tout disposé !
 
J'ai l'impression qu'il ne marche pas sur les cases 'enfermées'... :/

n°1954552
Profil sup​primé
Posté le 03-01-2010 à 13:14:18  answer
 

Salut,  
 
T'as tout mis en vrac, j'ai pas l'habitude de java, j'arrive pas à lire.
Ce que je sais c'est que a star fais une 30aine de lignes avec Java.
Avec Ada aussi par ailleurs.

n°1954651
apaachee
Posté le 04-01-2010 à 00:13:13  profilanswer
 

Hmm la je bloque vraiment avec mon algo interminable. On commence par ou pour A* et ma matrice ? =)

n°1954654
Profil sup​primé
Posté le 04-01-2010 à 01:09:55  answer
 

Ca c'est A *
 

Algorithme A-étoile
 
Début
  ouverts = { état initial }
  fermés  = vide
  succès  = faux
  Tant que (ouverts non vide) et (non succès) faire
    choisir n dans les ouverts tel que f(n) est minimum
    Si est_final(n) Alors succès=vrai
    Sinon ouverts = ouverts privé de n
          fermés  = fermés + n
          Pour chaque successeurs s de n faire  
            Si (s n'est ni dans ouverts ni dans fermés)
            Alors
              ouverts = ouverts + s
              père(s) = n
              g(s) = g(n) + coût(n,s)
            Sinon
              Si (g(s) > g(n) + coût(n,s)) Alors
                père(s) = n
                g(s) = g(n) + coût(n,s)
                Si (s se trouve dans fermés) Alors
                  fermés  = fermés  - s
                  ouverts = ouverts + s
                Fin si
              Fin si
            Fin si
          Fin pour
    Fin si
  Fin TQ
Fin  


 
 
Ca c'est une vue de l'implémentation avec le langage Ada, je l'ai tradui du code java.
 

Code :
  1. -----------------------------------------------------------------------
  2.      --               Resolution du Jeu du Taquin                         --
  3.      -----------------------------------------------------------------------
  4.      procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
  5.      -----------------------------------------------------------------------
  6.      --                      Algorithme A* ou Astar                       --
  7.      -----------------------------------------------------------------------
  8.         Succes : Boolean := Boolean'Value("FALSE" );
  9.         Noeud_Courant : T_Place_Ensemble;
  10.         Nouveau_Successeur : T_Matrice;
  11.      begin
  12.         ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
  13.         Vider(Ensemble => Dans.Ferme);
  14.         while not Est_Vide(Dans.Ouvert) and not Succes loop
  15.            Noeud_courantt := L_Element_Min(Ensemble => Dans.Ouvert).all;
  16.            if -- la j'ai pas le test je comprend plus -- then
  17.              Succes := Boolean'Value("TRUE" );
  18.            else
  19.               Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
  20.               ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
  21.               for I in Mouvement'range loop
  22.                  if (Mouvement(I)
  23.                     (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
  24.                      Ordonnee(Noeud_Courant.Matrice ,0),
  25.                      Noeud_Courant.Matrice) /= 0) then
  26.    
  27.                     -- generer la nouvelle matrice
  28.                     Nouveau_Successeur := Noeud_Courant.Matrice;
  29.                     Permuter(Nouveau_Successeur,
  30.                              Mouvement(I)
  31.                              (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
  32.                               Ordonnee(Nouveau_Successeur ,0),
  33.                               Nouveau_Successeur);
  34.    
  35.    
  36.    
  37.    
  38.                     -- la je pense que l'algo doit varier en fonction de sont utilisation
  39.    
  40.                     if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
  41.                       not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
  42.                        -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
  43.    t louche
  44.                        Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
  45.                        g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
  46.                     elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
  47.                        Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
  48.                        g(s) = g(n) + coût(n,s);
  49.                        if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
  50.                           -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
  51.                           -- le reste, c'est pire donc
  52.                           fermés  = fermés  - S;
  53.                           ouverts = ouverts + S;
  54.                           --
  55.                           -- je doit me planter quelque part !!!!!
  56.                        end if;
  57.                     end if;
  58.                  end if;
  59.               end loop;
  60.    
  61.            end if;
  62.    
  63.         end loop;
  64.    
  65.      -----------------------------------------------------------------------
  66.      --                     Fin algorithme A* ou Astar                    --
  67.      -----------------------------------------------------------------------


 
 
De mémoire, il est quasi correcte, si non, je me ferait taper sur les doigts.


Message édité par Profil supprimé le 04-01-2010 à 01:10:16
mood
Publicité
Posté le 04-01-2010 à 01:09:55  profilanswer
 

n°1954656
Profil sup​primé
Posté le 04-01-2010 à 01:17:05  answer
 

A non, le code Ada est un mélange avec du pseudo code...
 
il faut savoir de quoi il s'agit, c'est un jeu du taquin.
 
Les ligne commentées sont les instruction Ada manquante dans l'implémentation, je vais tenter de récupérer mieux.

n°1954723
apaachee
Posté le 04-01-2010 à 10:57:37  profilanswer
 

Merci beaucoup pour ce début, je planche dessus cet après-midi !

n°1955133
apaachee
Posté le 05-01-2010 à 14:25:35  profilanswer
 

Voila mon Astar. Ce qui me chagrine dans cet algo c'est qu'il ne prend pas en compte la valeur des cases. si 6 cases sont gratuites en allant voir un peu plus haut il ne le verra pas, comment faire ?

Code :
  1. public int Astar(int idepart, int jdepart, int iarrivee, int jarrivee){
  2.  int resultat;
  3.  Stack LOI = new Stack();//ListeOuverteI
  4.  Stack LOJ = new Stack();//ListeOuverteJ
  5.  Stack LFI = new Stack();//ListeFermeeI
  6.  Stack LFJ = new Stack();//ListeFermeeJ
  7.  Stack tempEucl = new Stack();//Distances Euclidiennes avant tri
  8.  Stack tempI = new Stack();//les i trouves avant tri
  9.  Stack tempJ = new Stack();//les j trouves avant tri
  10.  //On calcule les distances entre "point à proximité du point de départ" et "point d'arrivée"
  11.  double te;
  12.  if(this.caseADroite(idepart,jdepart)){
  13.   te = distanceEuclidienne(idepart+1,jdepart,iarrivee,jarrivee);
  14.   if(this.getcase(idepart+1,jdepart) == '0')//Malus si case vide
  15.    te = te + 5;
  16.   tempEucl.push(te);
  17.   tempI.push(idepart+1);
  18.   tempJ.push(jdepart);
  19.  }
  20.  if(this.caseAGauche(idepart,jdepart)){
  21.   te = distanceEuclidienne(idepart-1,jdepart,iarrivee,jarrivee);
  22.   if(this.getcase(idepart-1,jdepart) == '0')//Malus si case vide
  23.    te = te + 5;
  24.   tempEucl.push(te);
  25.   tempI.push(idepart-1);
  26.   tempJ.push(jdepart);
  27.  }
  28.  if(this.caseEnHaut(idepart,jdepart)){
  29.   te = distanceEuclidienne(idepart,jdepart-1,iarrivee,jarrivee);
  30.   if(this.getcase(idepart,jdepart-1) == '0')//Malus si case vide
  31.    te = te + 5;
  32.   tempEucl.push(te);
  33.   tempI.push(idepart);
  34.   tempJ.push(jdepart-1);
  35.  }
  36.  if(this.caseEnBas(idepart,jdepart)){
  37.   te = distanceEuclidienne(idepart,jdepart+1,iarrivee,jarrivee);
  38.   if(this.getcase(idepart,jdepart+1) == '0')//Malus si case vide
  39.    te = te + 5;
  40.   tempEucl.push(te);
  41.   tempI.push(idepart);
  42.   tempJ.push(jdepart+1);
  43.  }
  44.  //On trie les distances trouvées
  45.  Stack tri = new Stack();
  46.  tri = tri(tempEucl);
  47.  //On ajoute à LOI et LOJ les différentes coordonnées trouvées en fonction de leur distance (plus grosse distance en BAS)
  48.  Stack tempIsave = new Stack();
  49.  Stack tempJsave = new Stack();
  50.  while(!tri.empty()){
  51.   Integer itri = (Integer)tri.pop();
  52.   while(!tempI.empty()){
  53.    if(itri == nbObj(tempI)){
  54.     LOI.push(tempI.peek());
  55.     LOJ.push(tempJ.peek());
  56.    }
  57.    tempIsave.push(tempI.pop());
  58.    tempJsave.push(tempJ.pop());
  59.   }
  60.   while(!tempIsave.empty()){
  61.    tempI.push(tempIsave.pop());
  62.    tempJ.push(tempJsave.pop());
  63.   }
  64.  }
  65.  boolean fin;
  66.  while(fin == false){
  67.   if(LOI.empty()){
  68.    resultat = 1000;
  69.    fin == true;
  70.   }
  71.   else{
  72.    //Case Courante
  73.    int i = LOI.pop();
  74.    int j = LOI.pop();
  75.    //On vide les piles de traitement
  76.    while(!tempEucl.empty())
  77.     tempEucl.pop();
  78.    while(!tri.empty())
  79.     tri.pop();
  80.    while(!tempI.empty()){
  81.     tempI.pop();
  82.     tempJ.pop();
  83.    }
  84.    if((this.caseADroite(i,j)){
  85.     if(!dejaPresent(LFI,LFJ,i+1,j)){
  86.      te = distanceEuclidienne(i+1,j,iarrivee,jarrivee);
  87.      if(this.getcase(i+1,j) == '0')//Malus si case vide
  88.       te = te + 5;
  89.      te += distanceEuclidienne(i,j,iarrivee,jarrivee);
  90.      tempEucl.push(te);
  91.      tempI.push(i+1);
  92.      tempJ.push(j);
  93.     }
  94.    }
  95.    if((this.caseAGauche(i,j)){
  96.     if(!dejaPresent(LFI,LFJ,i-1,j)){
  97.      te = distanceEuclidienne(i-1,j,iarrivee,jarrivee);
  98.      if(this.getcase(i-1,j) == '0')//Malus si case vide
  99.       te = te + 5;
  100.      te += distanceEuclidienne(i,j,iarrivee,jarrivee);
  101.      tempEucl.push(te);
  102.      tempI.push(i-1);
  103.      tempJ.push(j);
  104.     }
  105.    }
  106.    if((this.caseEnHaut(i,j)){
  107.     if(!dejaPresent(LFI,LFJ,i,j-1)){
  108.      te = distanceEuclidienne(i,j-1,iarrivee,jarrivee);
  109.      if(this.getcase(i,j-1) == '0')//Malus si case vide
  110.       te = te + 5;
  111.      te += distanceEuclidienne(i,j,iarrivee,jarrivee);
  112.      tempEucl.push(te);
  113.      tempI.push(i);
  114.      tempJ.push(j-1);
  115.     }
  116.    }
  117.    if((this.caseEnBas(i,j)){
  118.     if(!dejaPresent(LFI,LFJ,i,j)){
  119.      te = distanceEuclidienne(i,j+1,iarrivee,jarrivee);
  120.      if(this.getcase(i,j+1) == '0')//Malus si case vide
  121.       te = te + 5;
  122.      te += distanceEuclidienne(i,j,iarrivee,jarrivee);
  123.      tempEucl.push(te);
  124.      tempI.push(i);
  125.      tempJ.push(j+1);
  126.     }
  127.    }
  128.    // Si la case objectif est atteinte alors aller à solution,
  129.    if(){
  130.     fin = true;
  131.     resultat = solution();
  132.    }
  133.    // sinon :  
  134.    else{
  135.     // empiler les nœuds voisins dans la liste ouverte du moins bon score au meilleur,  
  136.     tri = tri(tempEucl);
  137.     while(!tri.empty()){
  138.      Integer itri = (Integer)tri.pop();
  139.      while(!tempI.empty()){
  140.       if(itri == nbObj(tempI)){
  141.        LOI.push(tempI.peek());
  142.        LOJ.push(tempJ.peek());
  143.       }
  144.       tempIsave.push(tempI.pop());
  145.       tempJsave.push(tempJ.pop());
  146.      }
  147.      while(!tempIsave.empty()){
  148.       tempI.push(tempIsave.pop());
  149.       tempJ.push(tempJsave.pop());
  150.      }
  151.     }
  152.     // empiler le nœud courant dans la liste fermée.
  153.     LFI.push(i);
  154.     LFJ.push(j);
  155.    }
  156.   }
  157.  }
  158.  return resultat;
  159. }


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Java

  Parcours matrice.

 

Sujets relatifs
Exporter en csv une matrice stockée en baseType de donnée abtrait : Matrice
[C] [resolu] lecture matrice alloué dynamiquement[Résolu] Tri d'une matrice
[C] pb pour passer une matrice en parametre d'un fonctionAllocation de matrice 3D pondérée
recherche matrice phpAdressage de matrice, performances
produit des matrice en vbaParcours Arborescence
Plus de sujets relatifs à : Parcours matrice.


Copyright © 1997-2018 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR