Ez a poszt egy másik MI-s problémának lesz szentelve. Mégpedig az N négyzetnek. Biztos mindenki találkozozz már azzal a kirakós játékkal ahol tipikusan 9 négyzet fér el a táblán, 3x3as felbontásban. Mégpedig csak 8 részből áll a kép és van egy üres hely. A négyzeteket meg lehet ide-oda tologatni és a képet kell visszakapnunk ha jól toljuk... :) Hát ez nem egy grafikus program, és nem is tökéletes, de egyfajta heurisztika van beleépítve. A lényege az az hogy adott végállapot:
1 2 3
4 5 6
7 8 0
és kiinduló állapot:
1 2 0
4 6 3
7 5 8
esetén tud megfelelő operátorsorozatot találni melyet alkalmazva eljutunk a kezdő állapotból a végállapotba!
A heurisztika lényege hogy megnézi hogy mely operátorok alkalmazhatóak az adott állapotra, és ezekről megnézi hogy mennyivel, hány különböző elemmel térnek el a kívánt végállapottól. Illetve nagyon fontos megemlíteni hogy arra sose megy egyből vissza amerről jött! Iletve számon tartja a legkedvezőbb, és második legkedvezőbb utat! Mivel ha a legkedvezőbb az amerről jöttünk akkor jön képbe a második legkedvezőbb út!
Három argumentuma van az első a négyzetek száma a második a kézi kezdő vagy random kezdő állapot, a harmadik pedig kézi vég vagy alap végállapot megadását jelenti!
./n 3 0 0
Kimenete:
################# Itt a kezdőállatpot!! #################
1 2 0
4 6 3
7 5 8
#################################################################
##################### Itt célállapot! ###################
1 2 3
4 5 6
7 8 0
#################################################################
##################Let the hunt begin!!!##########################
############################## 1. kör############################
LE
1 2 3
4 6 0
7 5 8
############################## 2. kör############################
BALRA
1 2 3
4 0 6
7 5 8
############################## 3. kör############################
LE
1 2 3
4 5 6
7 0 8
############################## 4. kör############################
JOBBRA
1 2 3
4 5 6
7 8 0
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int** tabla;
int** celallapot;
int** segedt;
int* olvas;
int tavolsag[4];
int heurisztika[4];
//###########################################################################
// TÖMBÖK INICIALIZÁLÁSA
//###########################################################################
void lefoglal_atmeneti(int darab)
{
int i;
tabla=(int **)malloc(darab*sizeof(int *));
for(i=0;i<darab;i++)
tabla[i]=(int *)malloc(darab*sizeof(int));
}
void lefoglal_celallapot_alap(int darab)
{
int i;
celallapot=(int **) malloc(darab*sizeof(int *));
for(i=0;i<darab;i++)
celallapot[i]=(int*)malloc(darab*sizeof(int));
}
void lefoglal_seged(int darab)
{
int i;
segedt=(int**)malloc(darab*sizeof(int*));
for(i=0;i<darab;i++)
segedt[i]=(int*)malloc(darab*sizeof(int));
}
void lefoglal_olvas(int darab)
{
olvas=(int *)malloc(darab*darab*sizeof(int));
}
//#############################################################################
// INICIALIZÁLÁS VÉGE
//#############################################################################
//#############################################################################
// TÖMBÖK FELTÖLTÉSE
//#############################################################################
void kezi_kezdo(int db)
{
int i,j,k;
for(i=0;i<db*db;i++)
{
printf("Add meg a kezdőállapot %d-ik elemét: ",i+1);
scanf("%d",&olvas[i]);
}
k=0;
for(i=0;i<db;i++)
for(j=0;j<db;j++)
{
tabla[i][j]=olvas[k];
k++;
}
}
void random_kezdo(int darab)
{
int i,j,v;
int *seged=(int*)malloc((darab*darab)*sizeof(int));
for(i=0;i<darab*darab;i++)
{
seged[i]=i;
}
printf("\n");
for(i=0;i<darab;i++)
for(j=0;j<darab;j++)
{
again:
v=rand()%((darab*darab));
if(seged[v]==((darab*darab)+1)) goto again;
else
{
tabla[i][j]=seged[v];
seged[v]=(darab*darab)+1;
}
}
}
void feltolt_celallapot_alap(int darab)
{
int i,j,k;
k=1;
for(i=0;i<darab;i++)
for(j=0;j<darab;j++)
{
celallapot[i][j]=k;
k++;
}
celallapot[darab-1][darab-1]=0;
}
void kezi_celallapot(int darab)
{
int i,j,s;
for(i=0;i<darab*darab;i++)
{
printf("Add meg a vegallapot %d-ik elemet: ",i+1);
scanf("%d",&olvas[i]);
}
s=0;
for(i=0;i<darab;i++)
for(j=0;j<darab;j++)
{
celallapot[i][j]=olvas[s];
s++;
}
}
//#####################################################################
// TÖMBÖK FELTÖLTVE
//#####################################################################
//#####################################################################
// OPERÁTOROK DEFINIÁLÁSA
//#####################################################################
int jobbra(int helye,int darab,int flag)//jobbra megy a nulla
{
int sor,oszlop,seged;
int i,j;
if(helye%darab==0) sor=((int)helye/darab)-1;
else sor=((int)helye/darab);
oszlop=helye-(sor*darab)-1;
if(flag==0)
{
if(oszlop+1<darab)
{
// printf("Vegrehajthato a muvelet!!\n");
seged=tabla[sor][oszlop+1];
tabla[sor][oszlop+1]=0;
tabla[sor][oszlop]=seged;
}
else printf("Nem hajthato vegre!!\n");
}
else if(flag==1)
{
if(oszlop+1<darab) return 1;
else return 0;
}
else if(flag==2)
{
for(i=0;i<darab;i++)
for(j=0;j<darab;j++)
segedt[i][j]=tabla[i][j];
seged=segedt[sor][oszlop+1];
segedt[sor][oszlop+1]=0;
segedt[sor][oszlop]=seged;
}
return 0;
}
int balra(int helye,int darab,int flag)//balra megy a nulla
{
int sor,oszlop,seged;
int i,j;
if(helye%darab==0) sor=((int)helye/darab)-1;
else sor=((int)helye/darab);
oszlop=helye-(sor*darab)-1;
if(flag==0)
{
if(oszlop-1>=0)
{
// printf("Vegrehajthato!\n");
seged=tabla[sor][oszlop-1];
tabla[sor][oszlop-1]=0;
tabla[sor][oszlop]=seged;
}
else printf("Nem hajrható végre!!\n");
}
else if(flag==1)
{
if(oszlop-1>=0) return 1;
else return 0;
}
else if(flag==2)
{
for(i=0;i<darab;i++)
for(j=0;j<darab;j++)
segedt[i][j]=tabla[i][j];
seged=segedt[sor][oszlop-1];
segedt[sor][oszlop-1]=0;
segedt[sor][oszlop]=seged;
}
return 0;
}
int fel(int helye,int darab,int flag)//felfele megy a nulla
{
int sor,oszlop,seged;
int i,j;
if(helye%darab==0) sor=((int)helye/darab)-1;
else sor=((int)helye/darab);
oszlop=helye-(sor*darab)-1;
if(flag==0)
{
if(sor-1>=0)
{
// printf("Vegrehajthato!\n");
seged=tabla[sor-1][oszlop];
tabla[sor-1][oszlop]=0;
tabla[sor][oszlop]=seged;
}
else printf("Nem hajthato vegre!!\n");
}
else if(flag==1)
{
if(sor-1>=0) return 1;
else return 0;
}
else if(flag==2)
{
for(i=0;i<darab;i++)
for(j=0;j<darab;j++)
segedt[i][j]=tabla[i][j];
seged=segedt[sor-1][oszlop];
segedt[sor-1][oszlop]=0;
segedt[sor][oszlop]=seged;
}
return 0;
}
int le(int helye,int darab,int flag)//lefele megy a nulla
{
int sor,oszlop,seged;
int i,j;
if(helye%darab==0) sor=((int)helye/darab)-1;
else sor=((int)helye/darab);
oszlop=helye-(sor*darab)-1;
if(flag==0)
{
if(sor+1<=darab)
{
// printf("Vegrehajthato!\n");
seged=tabla[sor+1][oszlop];
tabla[sor+1][oszlop]=0;
tabla[sor][oszlop]=seged;
}
else printf("Nem hajthato vegre!!\n");
}
else if(flag==1)
{
if(sor+1<darab) return 1;
return 0;
}
else if(flag==2)
{
for(i=0;i<darab;i++)
for(j=0;j<darab;j++)
segedt[i][j]=tabla[i][j];
seged=segedt[sor+1][oszlop];
segedt[sor+1][oszlop]=0;
segedt[sor][oszlop]=seged;
}
return 0;
}
//####################################################################
// OPERÁTOROK VÉGE
//####################################################################
//####################################################################
// NULLA HELYE
//####################################################################
int nulla_helye(int darab)
{
int i,j,hely;
hely=-1;
for(i=0;i<darab;i++)
for(j=0;j<darab;j++)
if(tabla[i][j]==0)
{
if(i==0) hely=j+1;
else hely=i*darab+j+1;
}
return hely;
}
//####################################################################
// HELYE VÉGE
//####################################################################
//####################################################################
// ELTÉRÉS MEGHATÁROZÁSA
//####################################################################
int elteres(int db,int* aktualis[],int* veg[])
{
int i,j;
int k=0;
for(i=0;i<db;i++)
for(j=0;j<db;j++)
if(aktualis[i][j]!=veg[i][j]) k++;
return k;
}
//####################################################################
// ELTÉRÉS MEGHATÁROZVA
//####################################################################
//####################################################################
// KIÍRATÁSOK
//####################################################################
void kiirat(int darab,int* tomb[])
{
int i,j;
for(i=0;i<darab;i++)
{
for(j=0;j<darab;j++)
printf("%d ",tomb[i][j]);
printf("\n");
}
}
//####################################################################
// KIÍRATÁSOK VÉGE
//####################################################################
//####################################################################
// USAGE
//####################################################################
void usage()
{
printf("\nEz a program 4 argumentummal megy csak!!!!!\n");
printf("Így van helyesen indítva: ./1 2 3 4\n");
printf("1->>>>>>> a futtatható neve amit a GCC-től kapott!\n");
printf("2->>>>>>> azt adja meg hogy hányszor hányas legyen!\n");
printf("3->>>>>>> 0 ha kézileg lesz megadva a kezdő állapot!\n");
printf(" 1 ha egy véletlenül generáltat szeretnél!\n");
printf("4->>>>>>> 0 ha kézileg lesz megadva a célállapot!\n");
printf(" 1 ha az alap célállapotot szeretnéd!\n");
}
//####################################################################
// USAGE VÉGE
//####################################################################
//####################################################################
// A FŐPROGRAM
//####################################################################
int main(int argc,char* argv[])
{
int negyzetekszama,poz,i,keziflag,vegflag,s,best,j,merrol,bestketto,bestdb,min,elso,masodik;
int irany[4];
unsigned int seed = (unsigned int) time (NULL);
merrol=99999;
if(argc<4||argc>4) usage();
else
{
negyzetekszama=atoi(argv[1]);
keziflag=atoi(argv[2]);
vegflag=atoi(argv[3]);
srand(seed);
lefoglal_celallapot_alap(negyzetekszama);//célállapotot tartalmazó tömb
lefoglal_atmeneti(negyzetekszama);//aktuális állapot tömbje
lefoglal_seged(negyzetekszama);//heurisztika segítő tömb
lefoglal_olvas(negyzetekszama);//kézi feltöltést segítő tömb
if(keziflag==1) kezi_kezdo(negyzetekszama);//kezdő állapot feltöltése kézileg
else if(keziflag==0) random_kezdo(negyzetekszama);//véletlen generált kezdőállapot
if(vegflag==1) kezi_celallapot(negyzetekszama);//kézi célállapot feltöltlés
else if(vegflag==0) feltolt_celallapot_alap(negyzetekszama);//alap célállapot feltöltés
printf("\n################# Itt a kezdőállatpot!! #################\n");
kiirat(negyzetekszama,tabla);
printf("#################################################################\n\n");
printf("##################### Itt célállapot! ###################\n");
kiirat(negyzetekszama,celallapot);
printf("#################################################################\n\n");
printf("\n");
printf("##################Let the hunt begin!!!##########################\n");
for(j=0;;j++)
{
printf("############################## %d. kör############################\n",j+1);
poz=nulla_helye(negyzetekszama);
irany[0]=jobbra(poz,negyzetekszama,1);
irany[1]=balra(poz,negyzetekszama,1);
irany[2]=fel(poz,negyzetekszama,1);
irany[3]=le(poz,negyzetekszama,1);
for(i=0;i<4;i++)
heurisztika[i]=-1;
for(i=0;i<4;i++)
{
if(irany[i]==1)
{
if(i==0)
{
jobbra(poz,negyzetekszama,2);
heurisztika[i]=elteres(negyzetekszama,celallapot,segedt);
}
else if(i==1)
{
balra(poz,negyzetekszama,2);
heurisztika[i]=elteres(negyzetekszama,celallapot,segedt);
}
else if(i==2)
{
fel(poz,negyzetekszama,2);
heurisztika[i]=elteres(negyzetekszama,celallapot,segedt);
}
else if(i==3)
{
le(poz,negyzetekszama,2);
heurisztika[i]=elteres(negyzetekszama,celallapot,segedt);
}
}
}
best=99999;
for(i=0;i<4;i++)
if(heurisztika[i]<best&&heurisztika[i]!=-1) best=heurisztika[i];
bestdb=0;
for(i=0;i<4;i++)
if(heurisztika[i]==best) bestdb++;
if(bestdb>1)
{
min=0;
for(i=0;i<4;i++)
if(heurisztika[i]==best) {elso=i;break;}
for(i=0;i<4;i++)
{
if(heurisztika[i]==best) min++;
if(min==2) {masodik=i;break;}
}
}
else if(bestdb==1)
{
for(i=0;i<4;i++)
if(heurisztika[i]==best)
{
elso=i;
break;
}
heurisztika[elso]=-1;
masodik=99999;
for(i=0;i<4;i++)
if(heurisztika[i]<masodik&&heurisztika[i]!=-1)
{
masodik=heurisztika[i];
break;
}
heurisztika[elso]=best;
for(i=0;i<4;i++)
if(heurisztika[i]==masodik)
{
masodik=i;
break;
}
}
if((merrol==0&&elso==1)||(merrol==1&&elso==0)||(merrol==2&&elso==3)||(merrol==3&&elso==2))
{
if(masodik==0) jobbra(poz,negyzetekszama,0);
else if(masodik==1) balra(poz,negyzetekszama,0);
else if(masodik==2) fel(poz,negyzetekszama,0);
else if(masodik==3) le(poz,negyzetekszama,0);
else printf("Ez meg whattafuck!!!!!\n");
merrol=masodik;
}
else
{
if(elso==0) jobbra(poz,negyzetekszama,0);
else if(elso==1) balra(poz,negyzetekszama,0);
else if(elso==2) fel(poz,negyzetekszama,0);
else if(elso==3) le(poz,negyzetekszama,0);
else printf("Ez meg whattafuck!!!!!\n");
merrol=elso;
}
if(merrol==0) printf("JOBBRA\n");
else if(merrol==1) printf("BALRA\n");
else if(merrol==2) printf("FEL\n");
else if(merrol==3) printf("LE\n");
kiirat(negyzetekszama,tabla);
if(elteres(negyzetekszama,celallapot,tabla)==0) {printf("Aztakurva ez egy megoldás!!!!\n");break;}
}
}
return 0;
}
