Το πρόβλημα των ιεραποστόλων και κανιβάλων αφορά τη μεταφορά ενός αριθμού ιεραποστόλων και κανιβάλων από την αριστερή όχθη ενός ποταμού στη δεξιά όχθη, χρησιμοποιώντας μια βάρκα με περιορισμένη χωρητικότητα. Το πρόβλημα απαιτεί ότι σε καμία στιγμή δεν πρέπει να υπάρχουν περισσότεροι κανίβαλοι από ιεραποστόλους σε οποιαδήποτε όχθη, εκτός εάν δεν υπάρχουν ιεραπόστολοι.
Η λύση υλοποιείται με τον αλγόριθμο αναζήτησης A*, ο οποίος βρίσκει την πιο αποδοτική διαδρομή προς την τελική κατάσταση. Η υλοποίηση περιλαμβάνει:
state.py: Περιγράφει την κατάσταση του προβλήματος, συμπεριλαμβανομένων των ιεραποστόλων, των κανιβάλων και της θέσης της βάρκας. Περιέχει επίσης τη συνάρτηση ευρετικής αξιολόγησης που χρησιμοποιεί το ελάχιστο απαιτούμενο πλήθος διασχίσεων.
minimum_required_trips = (2 * (left_m + left_c) - 1) // (boat_capacity - 1)-
a_star.py: Υλοποιεί τον αλγόριθμο A*, ο οποίος διατηρεί μια λίστα από καταστάσεις προς εξερεύνηση και επιστρέφει τη βέλτιστη λύση. -
main.py: Εκτελεί τον αλγόριθμο για μια συγκεκριμένη διαμόρφωση του προβλήματος και εμφανίζει το αποτέλεσμα.N = 3 # Number of missionaries/cannibals M = 2 # Boat capacity K = 50 # Max allowed trips
Η ευρετική που χρησιμοποιείται βασίζεται στον ελάχιστο αριθμό ταξιδιών που απαιτούνται για τη μεταφορά όλων των ατόμων στη δεξιά όχθη, λαμβάνοντας υπόψη τη χωρητικότητα της βάρκας. Προστίθεται ένα πέναλτι σε μη έγκυρες καταστάσεις για να αποτρέψει μη επιθυμητές διαδρομές. Η παράμετρος που αφαιρείται είναι ο κανόνας ότι δεν πρέπει να υπάρχουν περισσότεροι κανίβαλοι από ιεραποστόλους σε οποιαδήποτε όχθη.
Για να εκτελέσετε τον κώδικα, χρησιμοποιήστε την ακόλουθη εντολή:
python main.py Μπορείτε να αλλάξετε τις παραμέτρους N (αριθμός ιεραποστόλων/κανιβάλων), M (χωρητικότητα της βάρκας) και K (μέγιστος αριθμός διασχίσεων) μέσα στο αρχείο main.py.