7-puzzle προβλημα...

[sheik]

Guys λιγο help αν μπορειτε.

Εχω μια εργασια,μεχρι τη Παρασκευη να παραδωσω στην Τεχνητη Νοημοσυνη.

Πρεπει να λυσω μια παραλλαγη του γνωστου 8-puzzle προβληματος με τις λιγοτερες δυνατες κινησεις.

Μονο που η ασκηση μου ειναι το 7-puzzle προβλημα,με 2 κενα τετραγωνακια δηλαδη και σε καθε βημα επιτρεπονται να κινηθουν και τα 2 τετραγωνακια.

Ο αλγοριθμος αναζητησης πρεπει να ειναι ο Α*

 

Εχω ασχοληθει ,εκανα καποια πραγματα αλλα εχω κολλησει στις συνθηκες κινησης των κενων τετραγωνων.Στο πως να υλοποιησω δηλαδη τους (παμπολους) διαφορετικους συνδυασμους που προκυπτουν κατα την επεκταση μιας καταστασης.

Το γαμωτο ειναι οτι πρεπει να την παραδωσω Παρασκευη,Τεταρτη παραδιδω αλλη ασκηση στα Λειτουργικα Συστηματα και ταυτοχρονα πρεπει να διαβασω για Δευτερα-Τριτη που δινω 2 μαθηματα συνεχομενα,οποτε καταλαβαινετε πως πεφτει πολυ ξυλο

 

Οποιος γνωριζει κατι επι του θεματος,ας δωσει τα φωτα του.

 

 

EDIT: Οι ευριστικες συναρτησεις που πρεπει να χρησιμοποιησω ειναι 2.Η μια το αθροισμα των αποστασεων Manhattan και η αλλη ο αριθμος των τετραγωνων που βρισκονται σε λαθος θεση συμφωνα με την τελικη κατασταση.

[sheik]

Οριστε τι εχω κανει μεχρι στιγμης.Το main προγραμμα σταματαει αφου ελεγξω οτι η τρεχουσα κατασταση δεν ειναι μια τελικη κατασταση ή δεν εχει ξαναλεγθει νωριτερα.Στη συνεχεια πρεπει να υλοποιησω την επεκταση των παιδιων της τρεχουσας καταστασης,την εφαρμογη των ευριστικων σε αυτα και την εισαγωγη τους στο μετωπο αναζητησης, γι'αυτο και ζηταω τη συμβουλη σας,επειδη ειναι αρκετα δυσκολο να το κανει κανεις με την εννοια οτι υπαρχουν πολλες περιπτωσεις και τις θελω συγκροτημενες στο μυαλο μου.

Οποιος εχει να πει κατι που ισως βοηθησει ας το κανει ΤΩΡΑΑΑΑ!:mrgreen:

 

>#include<stdio.h>




struct STATE{
      int A[3][3];
      int g;            /*   g(n}   */
      int h;           /*   h(n)=max{h1,h2}  */
      int e;           /*   e(n)=g(n)+h(n)    */
      bool expanded;
      struct STATE *next;
      };
      
      
struct STATE *head;          /*  1o stoixeio Metwpou anazhthshs   */
struct STATE *close;         /* 1o stoixeio kleistou synolou   */

bool AlreadyExpanded(struct STATE *current);
bool IsFinalState(struct STATE *current);
void DeleteState(struct STATE *current);



main(){
      int i,j,num;
      struct STATE root,CurrentState;
      printf(" Dwse diadoxika ta stoixeia tou pinaka \n");
      printf(" Gia ta kena tetragwna dwse thn timh 0 \n\n");
      for(i=0;i<3;i++){
         for(j=0;j<3;j++){
                  printf("Dwse to [%d,%d] stoixeio ",i+1,j+1);
                  scanf("%d",&num);
                  root.A[i][j]=num;
                  }
         }
         
         for(i=0;i<3;i++){
            for(j=0;j<3;j++){
               printf(" [%d,%d]=%d",i+1,j+1,root.A[i][j]);
               }
               printf("\n");
         }
         }
         
         close=NULL;        /* arxikopoihsh kleistou synolou  */
         
         head=&root;        /*   eisagwgi rizas sto M.A   */
         CurrentState=&root;    /*   Trexousa katastash=arxikh katastash   */
         
         while(!IsFinalState(CurrentState)){
               DeleteState(CurrentState);                   /* Afairesh apo to M.A  */
               if(AlreadyExpanded(CurrentState)==false){
                            
               
                                            
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
         
bool IsFinalState(struct STATE *current){
    if((current->A[0][0]==0)&&(current->A[1][1]=0)){
             if((current->A[0][1]==1)&&                         &
                (current->A[0][2]==2)&&                         &
                (current->A[1][0]==4)&&                         &
                (current->A[1][2]==3)&&                         &
                (current->A[2][0]==5)&&                         &
                (current->A[2][1]==6)&&                         &
                (current->A[2][2]==7)){
                                       return(true);
                                       }
                }
                return(false);
    }
    
    
void DeleteState(struct STATE *current){
    struct STATE *q;
    
    q=head;
    
    while(q->next!=current){
       q=q->next;
       }
       
       q->next=current->next;
       }
       
         
bool AlreadyExpanded(struct STATE *current){
    struct STATE *q;
    int count=0;
    q=close;
    while(q!=NULL){
         for(i=0;i<3;i++){
            for(j=0;j<3;j++){
               if(q->A[i][j]==current->A[i][j]) count++;
               }
            }
          if(count==9) return(true);
         }
    return(false);
}

 

 

Για οποιον δεν εχει καταλαβει τι ακριβως ειναι αυτο το προβλημα,οριστε μια εικονα με το 8-puzzle προβλημα:

 

Moνο που στο 7-puzzle υπαρχουν 2 κενα τετραγωνα τα οποια μπορουν να κινουνται με καθε δυνατο συνδυασμο.