«Ο Αρχιμήδης θα μνημονευθεί όταν ο Αισχύλος θα έχει λησμονηθεί, διότι οι γλώσσες πεθαίνουν, μα οι μαθηματικές ιδέες όχι.» G.Hardy


Κυριακή 20 Οκτωβρίου 2013

Ένα πρόβλημα κανιβάλων και η τεχνητή νοημοσύνη.

  
Αllen Newell  ,  Herbert Simon

Αllen Newell  ,  Herbert Simon

"Ιεραπόστολοι...!Μα δεν βλέπετε, αγαπητέ μου, πως οι ιεραπόστολοι είναι η μέριμνα του Θεού για τους εξαθλιωμένους και υποσιτισμένους κανίβαλους; Κάθε φορά που είναι ένα βήμα προ του να πεθάνουν από ασιτία, ο ύψιστος, μέσα στην απέραντη φιλευσπλαχνία του ,τους στέλνει αμέσως , μια ντουζίνα από στρουμπουλούς  και καλοκάγαθους ιεραποστόλους ."

                                                                                                                         Oscar Wilde

                
1955
Allen Newell and Herbert Simon Allen Newell (IA’57), Herbert Simon, and J. C. (Cliff) Shaw create the “Logic Theorist,” the first thinking machine at Carnegie Tech.
- See more at: http://www.cit.cmu.edu/about_cit/timeline.html#sthash.dUZVcl7U.dpuf
1955
Allen Newell and Herbert Simon Allen Newell (IA’57), Herbert Simon, and J. C. (Cliff) Shaw create the “Logic Theorist,” the first thinking machine at Carnegie Tech.
- See more at: http://www.cit.cmu.edu/about_cit/timeline.html#sthash.dUZVcl7U.dpu
  Μακράν του πολιτικά ορθού η σημερινή ανάρτηση καθώς αφορά ένα κλασικό γρίφο διάσχισης ποταμών με κανίβαλους .Το 1957, οι Αllen Newell ,J.Οι Shaw και Herbert Simon,  προγραμματιστές της Rand Corporation δημιούργησαν ένα από τα  πρώτα προγράμματα τεχνητής νοημοσύνης με την ονομασία General Problem Solver. Στρατολόγησαν μια ομάδα ατόμων που είχαν ως χόμπι την επίλυση λογικών γρίφων και τους έθεσαν δέκα λογικά προβλήματα, κατέγραψαν τον τρόπο που τα έλυσαν και συστηματοποίησαν τις ευρετικές μεθόδους που χρησιμοποίησαν για να γράψουν τον  κώδικα του General Problem Solver.Ένα από τα δέκα αυτά προβλήματα άνηκε στον Μάρτιν Γκάρντνερ και είχε τίτλο οι κανίβαλοι και οι ιεραπόστολοι.(Ενδελεχή αναφορά στο πρόβλημα με χρήση θεωρίας γράφων  στο σύνδεσμο Directed graphs and cannibals,σελ 102).
Το πρόβλημα ήταν το εξής :

"Στην όχθη ενός ποταμού βρίσκονται τρεις ιεραπόστολοι και τρεις κανιβαλοι. Αντικειμενικός σκοπός είναι και τα 6 άτομα- κανίβαλοι και ιεραπόστολοι- να φτάσουν στην άλλη όχθη. Υπάρχει μια βάρκα που μπορούν χρησιμοποιήσουν, υπό την προϋπόθεση ότι σε κάθε διέλευση του ποταμού θα πρέπει να επιβαίνει τουλάχιστον ένα  άτομο και το πολύ δυο. Δεν επιτρέπεται σε καμία περίπτωση σε μια από τις δυο όχθες να βρεθούν περισσότεροι κανίβαλοι από ιεραποστόλους γιατί τότε θα τους φάνε. Στον ποταμό βρίσκονται ανθρωποφάγοι  κροκόδειλοι. Με ποιο τρόπο μπορούν οι τρεις  ιεραπόστολοι και οι τρεις  κανίβαλοι να μεταβούν στην άλλη όχθη χωρίς να υπάρξει κάποιο ατύχημα;"

(Η λύση στα σχόλια)

  Για την ιστορία, η πρώτη φορά που εμφανίστηκε παρόμοιο πρόβλημα (river crossing problem) ήταν στο βιβλίο Propositiones ad Acuendos Juvenes (Προβλήματα που ακονίζουν το μυαλό που γράφτηκε από τον Αλκουίνο της Υόρκης (732-811),Βενεδικτίνο μοναχό και λόγιο της αυλής του Καρλομάγνου.

Τέτοιου είδους προβλήματα σύμφωνα με το διαδίκτυο τίθενται σε υποψήφιους για πρόσληψη σε εταιρείες λογισμικού όπως η Google ή η Microsoft αλλά ίσως πρόκειται για αστικό μύθο.Προβλήματα με πολλαπλές αναφορές σε πολλούς ιστοτοπους όπως το παρακάτω:
 
  Τέσσερα άτομα πρέπει να διασχίσουν μια γέφυρα βράδυ με τη βοήθεια ενός φακού που έχουν μαζί τους. Μπορούν να περνούν τη γέφυρα έως δυο άτομα. Καθένας από τους παραπάνω διασχίζει τη γέφυρα σε διαφορετικό χρόνο. Ειδικότερα ,
ο πρώτος χρειάζεται τουλάχιστον 1 λεπτό,

ο δεύτερος χρειάζεται τουλάχιστον 2 λεπτά,

ο τρίτος χρειάζεται τουλάχιστον 5 λεπτά και

ο τέταρτος χρειάζεται τουλάχιστον 10 λεπτά.

  Με ποιόν τρόπο θα μπορέσουν να περάσουν όλοι από το ένα άκρο της γέφυρας ως το άλλο σε 17 λεπτά; 
( Η λύση στα σχόλια)

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


Περαιτέρω πληροφορίες
https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem
Μπορείτε να προσπαθήσετε να λύσετε το πρόβλημα των κανιβάλων στην διαδραστική εφαρμογή.https://www.novelgames.com/en/missionaries/

2 σχόλια:











  1. 1)
    Περνάνε πρώτα δύο κανίβαλοι και επιστρέφει ένας κανίβαλος.
    Περνάνε δύο κανίβαλοι και επιστρέφει ένας κανίβαλος.
    Περνάνε δύο ιεραπόστολοι και επιστρέφει ένας ιεραπόστολος και ένας κανίβαλος.
    Περνάνε δύο ιεραπόστολοι και επιστρέφει ένας κανίβαλος.
    Περνάνε δύο κανίβαλοι και επιστρέφει ένας κανίβαλος.
    Τέλος, περνάνε οι δύο τελευταίοι κανίβαλοι.




    2)Πρώτα θα περάσει ο 1ος με τον 2ο (2 λεπτά) και θα γυρίσει πίσω ο 1ος με το φακό (3 λεπτά). Μετά θα δώσει το φακό στον 3ο που θα φύγει με τον 4ο (13 λεπτά) και θα δώσουν τον φακό στον 2ο να γυρίσει πίσω (15 λεπτά).Τέλος θα φύγουν ο 1ος με τον 2ο (17 λεπτά) και θα έχουν όλοι περάσει τη γέφυρα!

    ΑπάντησηΔιαγραφή

Related Posts Plugin for WordPress, Blogger...