Τεχνητή Νοημοσύνη

[sirah90]

Θεωρούμε το πρόβλημα όπου n άνθρωποι βρίσκονται στη μία όχθη ενός ποταμού και

θέλουν να περάσουν όλοι στην απέναντι όχθη. 2 άτομα κάθε φορά. Έχουν μόνο ένα

φακό που πρέπει να κρατάει κάποιος από αυτούς που περνούν την γέφυρα.Όταν 2 άνθρωποι διασχίζουν την

γέφυρα μαζί δεν έχει σημασία ποιος κρατάει το φακό.

Για την επίλυση του προβλήματος χρειάζεται να χρησιμοποιήσω τον αλγόριθμο τυφλής

αναζήτησης BFS.

Αν μπορεί κάποιος παρακαλώ να βοηθήσει με συμβουλές και κώδικα σε C ή C++.

[Alchemist`]

Θεωρούμε το πρόβλημα όπου n άνθρωποι βρίσκονται στη μία όχθη ενός ποταμού και

θέλουν να περάσουν όλοι στην απέναντι όχθη. 2 άτομα κάθε φορά. Έχουν μόνο ένα

φακό που πρέπει να κρατάει κάποιος από αυτούς που περνούν την γέφυρα.Όταν 2 άνθρωποι διασχίζουν την

γέφυρα μαζί δεν έχει σημασία ποιος κρατάει το φακό.

Για την επίλυση του προβλήματος χρειάζεται να χρησιμοποιήσω τον αλγόριθμο τυφλής

αναζήτησης BFS.

Αν μπορεί κάποιος παρακαλώ να βοηθήσει με συμβουλές και κώδικα σε C ή C++.

 

Μας δίνει δεδομένα, αλλά δεν μας λες πιο είναι το ερώτημα...

 

Με τον όρο BFS, εννοείς τον αλγόριθμο best fs?

[V.I.Smirnov]

@Αlchemist

 

Προφανώς εννοεί τον αλγόριθμο Breath Fisrst Search που χρησιμοποιείται για

να σαρώνεται ένα δέντρο κατά τα επίπεδα των 'αδελφικών' κόμβων (sibling nodes).

 

Ήμουν έτοιμος να δώσω ενδεικτικό κώδικα επ' αυτού :

σάρωση ενός δέντρου με ΒFS για την εύρεση της διαδρομής (αν υπάρχει) μεταξύ δυο θέσεων.

Αλλά δεν ξέρω πώς μπορεί να χρησιμοποιηθεί ο BFS για το δοθέν πρόβλημα.

Ας μας πει και ίσως βάλω αυτό που έγραψα στα γρήγορα.

Έξάλλου ο BFS δεν είναι κάτι εξεζητημένο, είναι εύκολο να βρεθεί παράδειγμα.

 

-

[sirah90]

Αρχικά με βάση το πρόβλημα δημιουργώ μια αρχική κατάσταση (0,0,...n) όπου το πρώτο στοιχείο συμβολίζει το φακό. Αυτή η αρχική κατάσταση είναι η ρίζα ενός δέντρου. Μετά πρέπει να αναπτύξω το δέντρο έτσι ώστε να παίρνει όλες τις περιπτώσεις για τα άτομα που μπορούν να διασχίσουν τη γέφυρα. Με κάποιο τρόπο πρέπει να κρατάω τις καταστάσεις που έχω επισκεφτεί. Έτσι λοιπόν, για τον κάθε κόμβο, πρέπει να δηλώσω μια κατάσταση(πίνακας με n+1 στοιχεία), τον πατρικό κόμβο(μέσω ενός pointer), την ενέργεια που εκτελούμε κάθε φορά(ακέραιος), το κόστος του μονοπατιού(ακέραιος) και το βάθος(ακέραιος). Πρέπει να δημιουργήσω μια δομή όπου θα κρατάω όλους τους κόμβους, δηλαδή ένα μέτωπο αναζήτησης. Αυτό μπορώ να το υλοποιήσω με μια ουρά. Και στη συνέχεια, στο τέλος της ουράς πρέπει να βάλω τον Breadth First Search(BFS). Είναι σημαντικό κάθε φορά να κρατάω τις καταστάσεις που έχω επισκεφτεί.

[V.I.Smirnov]

Να μια απλή υλοποίηση του BFS για να καταλάβεις πώς δουλεύει.

Φτιάχνεις ένα δέντρο όπου οι κόμβοι του παριστάναουν θέσεις και ζητάς την διαδρομή μεταξύ δυο θέσεων.

Αν υπάρχει, την βρίσκει και την τυπώνει, αλλιώς εκτυπώνει μήνυμα.

Όλα υλοποιούνται με πίνακες για απλότητα και συντομία.

Είναι μια αρχή στο πρόβλημά σου.

 

>/*
 Breadth First Search implementation demo

----------------
 V.I.Smirnov
----------------

*/

#include <stdio.h>
#include <string.h>
#include <assert.h>

#define NUM_NODES  10
#define MAX_QUEUE  10

//             from       to 
int adjMatrix[NUM_NODES][NUM_NODES];
int visited[NUM_NODES];

int queue[MAX_QUEUE];
int write, read;

#define WRAP(x)  ((x == (MAX_QUEUE)-1) ? 0 : x+1)


void initAdjMatrix()
{
 memset( (void *) adjMatrix, 0, sizeof(adjMatrix) );
 memset( (void *) visited,   0, sizeof(visited) );

 return;
}


void makeEdge(int from, int to)
{
 assert(from < NUM_NODES );
 assert(to < NUM_NODES );

 adjMatrix[from][to] = 1;

}


void initQueue()
{
 write = read = 0;

 return;
}


int empty()
{
  return (write == read) ? 1 : 0;
}


void enqueue(int elem)
{
 queue[write] = elem;
 write = WRAP(write);

 return;
}


int dequeue()
{
 int elem;

 assert( !empty() );
 elem = queue[read];
 read = WRAP(read);

 return elem;
}


void dfs(int start, int goal)
{
 int node, i;

 enqueue(start);

 while (!empty()) 
 {

   // Open a new node
   node = dequeue();

   if (node == goal) 
   {
     printf("%d Goal\n", node);
     return;
   }

   if (visited[node]) continue;
   else visited[node] = 1;

   printf("%d ", node);

   // Enqueue each of the children of the current node onto the queue.
   for (i = 0 ; i < NUM_NODES ; ++i) 
     if (adjMatrix[node][i] == 1) enqueue(i);

 }

 printf("Goal not found.\n");

 return;
}


int main()
{
 initAdjMatrix();
 initQueue();

 // Build a graph in the adjacency matrix
 makeEdge(1,2); 
 makeEdge(1,3); 
 makeEdge(1,4); 
 makeEdge(2,5); 
 makeEdge(3,5); 
 makeEdge(3,6); 
 makeEdge(4,7); 
 makeEdge(5,8); 
 makeEdge(5,9); 

 dfs(1, 9);

 return 0;
}

 

Σε παρακαλώ αν τελικά λύσεις το πρόβλημα, βάλε την λύση για να την δούμε κι' εμείς...

 

-

[sirah90]

Ωραίος ρε φίλε σ'ευχαριστώ πολύ!!