Cristina Sichim

Profil

Colegi

Coleg pentru

Puncte iTeach: 35

Perspico - implementare Java

Cristina SichimColegiul National Ferdinand I, Bacau31 aug. 2020

Jocul constă în 15 plăcuţe pătrate ce sunt încadrate într-un cadru de dimesiune 4x4, o poziţie fiind liberă şi marcată cu 0.Orice plăcuţă vecină cu o poziţie liberă poate fi mutată în locul ei.Cele 15 plăcuţe sunt numerotate de la 1 la 15.
Se începe dintr-o stare iniţială, corespunzătoare unei distribuţii oarecare a celor 15 plăcuţe numerotate 1-15 şi a locului liber în cele 16 poziţii posibile şi trebuie să se ajungă pe un drum cât mai scurt într-o configuraţie finală. Un exemplu de configuraţie poate fi:

Problema se rezolvă pe un arbore ce are cel mult 4 fii. În acest arbore există două tipuri de noduri: expandate ( aflate în lista prim0) şi neexpandate( aflate în lista prim1). Pentru fiecare nod se păstrează legătura către tata, configuraţia obţinută, 2 câmpuri f şi g, în care f precizează distanţa până la configuraţia finală şi g care indică numărul de paşi realizaţi.

Algoritmul de generare

Pas1. Adaugă în lista prim0 configuraţia iniţială ce are g=0. Calculează f. Tatal este null.
Pas2. Cât timp lista prim0 nu este vidă şi nu am ajuns la configuraţia finală se execută:
Pas 2.1. selectează din lista prim0 nodul p pentru care f+g = minim
Pas 2.2. expandează acest nod
Pas 2.3.pentru fiecare din nodurile obţinute( fii nodului p expandat) execută:
Pas 2.3.1. stabileşte g=g(p)+1 şi calculează f
Pas 2.3.2. verifică dacă acest nod este în prim0 sau în prim1
Pas 2.3.2.3 dacă da , se verifică dacă valoarea lui g actuală este mai mică decât cea a nodului găsit. În caz afirmativ se redirecţionează câmpul tată către nodul p ( am găsit un drum mai scurt). Dacă a fost găsit în prim1 el se va scoate şi se va adăuga în prim0.
Pas 2.3.2.3. Dacă nu atunci se adaugă în prim0
Pas 3. dacă algoritmul se încheie atunci când am terminat lista prim0 înseamnă că problema nu are soluţie iar altfel se afişează recursiv drumul utilizând câmpul tata.

Pentru configuraţiile din exemplu se generează:
Am considerat aici f= numărul de căsuţe nenule care nu sunt puse la locul lor

Interfaţa grafică este realizată cu ajutorul unui cadru ( obiect de tip Frame) pe care am plasat un panou( obiect de tip Panel) utilizat pentru gruparea următoarelor componente:
 Câmpuri de text needitabile pentru indicarea matricii iniţiale şi a celei finale
 Buton pentru generarea soluţiei
 GridLayout pentru introcerea şi afişarea matricilor

Pentru generarea soluţiei, introducem cele două stări şi după aceea apăsăm butonul de generare.

În urma generării rezultă obiecte care reprezintă stările intermediare şi cere se afizează în continuare, după Câmpul text needitabil.

Exemple

mport java.awt.*;
import java.awt.event.*;

class Ex5 {

public static int n=4;
public static P p,q,aux;
public static F f;

public static void main(String[] s){

//F
f =new F("Perspico");

f.setLayout(new GridLayout(0,n,n,1));

p=new P(4);f.add(p);
q=new P(4);f.add(q);

TextField t=new TextField(" Configuratii intermediare:");f.add(t);
t.setEditable(false);

HModif HM=new HModif(f.b1,f.b2,f.t,p,q);

f.b1.addActionListener(HM);
f.b2.addActionListener(HM);
f.t.addActionListener(HM);
f.setSize(800,200);
f.setVisible(true);
}

}

class F extends Frame implements ActionListener{
Button b1,b2;
TextField t;
F(String title){ setTitle(title);setLayout(new FlowLayout());
                 t=new TextField("Configratie initiala");add(t);
                 t.setEditable(false);
                 t=new TextField("Configuratie finala ");add(t);
                 t.setEditable(false);

                 b1=new Button("Genereaza solutie");add(b1);
                 b2=new Button("");add(b2);
                 b2.setVisible(false);
                 b1.addActionListener(this);
                 b2.addActionListener(this);
                 addWindowListener(
          new WindowAdapter(){
             public void windowClosing(WindowEvent e){System.exit(0);}
                             }
                                );
                }

public void actionPerformed(ActionEvent e)
{ System.out.println("Buton apasat");}

}

class P extends Panel{
TextField[][] tf;
P(int nr){ tf=new TextField[nr][nr];
           for(int i=0;i<nr;i++)
              for(int j=0;j<nr;j++)
               {tf[i][j]=new TextField(""+i,2); add(tf[i][j]);}


          }
        }

class HModif implements ActionListener{
Button b1,b2; TextField t; P p,q;String s;

HModif(Button b1,Button b2,TextField t,P p,P q) {this.b1=b1;this.b2=b2;this.t=t;this.p=p;this.q=q;}

public void actionPerformed(ActionEvent e){
if(e.getSource() instanceof Button)
   if(e.getActionCommand().equals("Genereaza solutie"))
   { perspico y=new perspico();
     perspico.maine();
    }
}

}

class nod{
int[][] m;int poz0_l,poz0_c;
int n=Ex5.n;

nod tata,urm,pfiu,ufiu;
int f,g;
nod(){}
void afis(){for(int i=1;i<=n;i++)
              {for(int j=1;j<=n;j++) IO.write(m[i][j]+" ");
               IO.writeln();
               }
             IO.writeln("f= "+f+"g= "+g);
             }
} // de la clasa

class perspico{

static nod prim0,ultim0,prim1,ultim1,fiuminim,p,fin,pfiu,ufiu;

//selectez din lista0 nodul cu valoarea minima si-l duc in lastai

static int h(int[][] m1,int[][] m2,int n) //distanta Manhattan
{ int s=0;
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           for(int k=1;k<=n;k++)
               for(int l=1;l<=n;l++)
                 if(m2[i][j]==m1[k][l] && m2[i][j]!=0)
                    s=s+Math.abs(i-k)+Math.abs(j-l);
     return s;
    }

static void traverseaza(nod q1)
    { if(q1!=null){traverseaza(q1.tata);
                    Ex5.aux=new P(4);Ex5.f.add(Ex5.aux);
                   for(int i=1;i<=q1.n;i++)
                    for(int j=1;j<=q1.n;j++)
                        Ex5.aux.tf[i-1][j-1].setText(""+q1.m[i][j]);
                  }
     }

static nod selectez_minim()
{

        int m=prim0.f+prim0.g,m1=prim0.g;
        fiuminim=prim0;
        for(nod p=prim0;p!=null;p=p.urm)if(m>p.f+p.g || m==p.f+p.g && m1>p.g)
                           { m=p.f+p.g;m1=p.g;fiuminim=p;}

//il scoate din prim0

        if(prim0==ultim0) prim0=ultim0=null;
           else
              if(fiuminim==prim0) prim0=prim0.urm;
                else
                   { for(p=prim0;p.urm!=fiuminim;p=p.urm);
                     if(ultim0==fiuminim){ultim0=p;p.urm=null;}
                        else p.urm=fiuminim.urm;
                    }

//il adaug in prim1

fiuminim.urm=null;

        if(prim1==null){prim1=ultim1=fiuminim;}
              else{ultim1.urm=fiuminim;
                   ultim1=fiuminim;
                   }
      return fiuminim;
   }//select

static nod cauta(nod q,nod l)
   { //in lista l
     for(nod p=l;p!=null;p=p.urm)
       if(h(q.m,p.m,p.n)==0)return p;
    return null;

}//cauta_nod

static nod expandeaza_nod(nod q)
{
pfiu=null;

     for(int k=1;k<=4;k++)
      {
        nod aux=new nod();

        aux.m=new int[q.n+1][q.n+1];
        for(int ii=1;ii<=q.n;ii++)
          for(int jj=1;jj<=q.n;jj++)
            aux.m[ii][jj]=q.m[ii][jj];
        aux.n=q.n;
         int sw=0;
        switch(k)
        { case 1: if(q.poz0_l>1){ aux.m[q.poz0_l][q.poz0_c]=aux.m[q.poz0_l-1][q.poz0_c];
                                  aux.m[q.poz0_l-1][q.poz0_c]=0;sw=1;
                                  aux.poz0_l= q.poz0_l-1;aux.poz0_c=q.poz0_c;
                                 }break;

          case 2: if(q.poz0_c<q.n){ aux.m[q.poz0_l][q.poz0_c]=aux.m[q.poz0_l][q.poz0_c+1];
                                  aux.m[q.poz0_l][q.poz0_c+1]=0;sw=1;
                                  aux.poz0_l= q.poz0_l;aux.poz0_c=q.poz0_c+1;
                                 }break;
          case 3: if(q.poz0_l<q.n){ aux.m[q.poz0_l][q.poz0_c]=aux.m[q.poz0_l+1][q.poz0_c];
                                  aux.m[q.poz0_l+1][q.poz0_c]=0;sw=1;
                                  aux.poz0_l= q.poz0_l+1;aux.poz0_c=q.poz0_c;
                                  }break;
          case 4: if(q.poz0_c>1){ aux.m[q.poz0_l][q.poz0_c]=aux.m[q.poz0_l][q.poz0_c-1];
                                  aux.m[q.poz0_l][q.poz0_c-1]=0;sw=1;
                                  aux.poz0_l= q.poz0_l;aux.poz0_c=q.poz0_c-1;
                                 }

}

        if(sw==1)
         {
          //IO.writeln("adaug fiul:");aux.afis();

           aux.tata=q;aux.g=q.g+1;aux.f=h(fin.m,aux.m,q.n);aux.urm=null;
           if(pfiu==null){pfiu=ufiu=aux;}
             else{ufiu.urm=aux;ufiu=aux;}
         }
      }
     return pfiu;

} // void expandeaza

static   void afis_lista(nod l)
   { for(nod p1=l;p1!=null;p1=p1.urm)
        { p1.afis();IO.writeln("");}
   }

public static void maine()
      {
        prim0=new nod();fin=new nod();
        int i,j,gata=0;

        prim0.n=Ex5.n;
        int n1=prim0.n;
        prim0.m=new int[n1+1][n1+1];
        String s;
        for(i=1;i<=n1;i++)
           for(j=1;j<=n1;j++)
              {
                s=Ex5.p.tf[i-1][j-1].getText();
            try {
              prim0.m[i][j] = Integer.parseInt(s);
                 }
             catch (NumberFormatException e)
              {
                Ex5.p.tf[i-1][j-1].setText(""+0);
              }

if(prim0.m[i][j]==0){prim0.poz0_l=i;prim0.poz0_c=j;}}

fin.m=new int[n1+1][n1+1];

        fin.n=n1;
        for(i=1;i<=n1;i++)
           for(j=1;j<=n1;j++)
           {
                s=Ex5.q.tf[i-1][j-1].getText();
            try {
            fin.m[i][j] = Integer.parseInt(s);
                 }
             catch (NumberFormatException e)
              {
                Ex5.q.tf[i-1][j-1].setText(""+0);
              }

           }

        prim0.g=0;prim0.f=h(prim0.m,fin.m,n1);prim0.urm=null;ultim0=prim0;
        prim0.tata=null;

        IO.writeln("plec de la");
        for(i=1;i<=n1;i++)
          { for(j=1;j<=n1;j++) IO.write(prim0.m[i][j]+" ");

            IO.writeln("");
          }

        IO.writeln("ajung in ");
        for(i=1;i<=n1;i++)
          { for(j=1;j<=n1;j++) IO.write(fin.m[i][j]+" ");
            IO.writeln("");
          }

        // prelucrez lista0

nod p;

        while(prim0!=null)
          {

               fiuminim=selectez_minim();

           if(fiuminim.f==0){traverseaza(fiuminim);prim0=null;gata=1;}
              else{ pfiu=null;
                    pfiu=expandeaza_nod(fiuminim);

                     while(pfiu!=null)
                       { p=pfiu;pfiu=pfiu.urm;

                         nod x=cauta(p,prim0);

                         if(x!=null)
                              {if(p.g<x.g) x.tata=fiuminim;}

                            else
                                 { nod y=cauta(p,prim1);

                                   int adauga=0;
                                   if(y!=null)
                                       if(p.g<y.g) {y.tata=fiuminim;
                                                       adauga=1;
                                                   }

                                   if(adauga==1 || y==null)
                                      { // adaug in prim0
                                       p.urm=prim0;
                                       prim0=p;
                                       //eventual il sterg din prim1
                                       if(adauga==1)
                                          {
                                          nod r=prim1;
                                          if(y==prim1) prim1=prim1.urm;
                                            else
                                               {//merg inaintea lui
                                                while(r.urm!=y) r=r.urm;
                                                r.urm=y.urm;
                                                if(r.urm==null)ultim1=r;

}

}}}}}}
if(gata==0)IO.write("nu exista solutii");

} }

1 comentariu21 de accesări