0
Εργασία: Πρόβληματα Προσπάθειας και Αποτυχίας
Μία εταιρεία που αποτελείται από 12 τμήματα, πρόκειται να μετακομίσει σε ένα καινούργιο κτήριο με τρείς ορόφους. Κάθε όροφος διαθέτει 40 γραφεία. Στον παρακάτω πίνακα δίνονται οι ανάγκες των τμημάτων της εταιρείας σε γραφεία:
Τμήμα Τ1 Τ2 Τ3 Τ4 Τ5 Τ6 Τ7 Τ8 Τ9 Τ10 Τ11 Τ12
Γραφεία 9 6 11 13 9 12 11 11 7 10 11 10
Επί πλέον, τα παρακάτω τμήματα ανά δύο πρέπει να βρίσκονται στον ίδιο όροφο, γιατί οι δραστηριότητές τους σχετίζονται σε μεγάλο βαθμό και πρέπει να συνεργάζονται:
• Τ1 και Τ3,
• Τ2 και Τ4,
• Τ8 και Τ9.
Να βρεθεί η κατανομή των γραφείων στα τμήματα (σε ποιον όροφο δηλαδή θα
καταλάβει γραφεία το κάθε τμήμα).
Υποδείξεις:
• Χρησιμοποιήστε σαν μοντέλο το πρόγραμμα που αναφέρεται στη λύση του
προβλήματος των 8 βασιλισσών. (παράγραφος 8.7 των σημειώσεων)
• Η λύση μπορεί να δημιουργηθεί σαν μία λίστα L, 12 στοιχείων από τριάδες
<D,N,F>, όπου D είναι το τμήμα, Ν ο αριθμός των γραφείων που χρειάζεται
το τμήμα και F είναι ο όροφος που βρίσκονται τα γραφεία. Στο
συγκεκριμμένο πρόβλημα τα D και N είναι γνωστά και το F αναζητείται.
• Μπορεί να οριστεί ένα κατηγόρημα allocate(L,N1,N2,N3), όπου L η λίστα
των παραπάνω τριάδων και Ν1, Ν2, Ν3 είναι αντίστοιχα ο αριθμός των
ελεύθερων γραφείων κάθε ορόφου. Η ερώτηση ?-allocate(L,40,40,40),
επιλύει το πρόβλημα επιστρέφοντας τις τιμές των αντίστοιχων τριάδων.
Δημιουργήστε μία παραλλαγή (γενίκευση) του παραπάνω προβλήματος και
δώστε τη λύση. (Τι θα συμβεί π.χ. αν όλα τα γραφεία κάποιων τμημάτων δεν μπορούν να βρίσκονται στον ίδιο όροφο
Ευχαριστω πολυ!