Θέμα: csd::Τμημα επιστημης υπολογιστων προγραμμα σπουδων

[bugman]

Αν παρατήρησες στην εικόνα παραπάνω το πρόβλημα δίνει μια λύση (από τις πολλές) βάσει ενός πίνακα (με λίστες γίνεται αυτός), όπου τα ζευγάρια πχ 1,3 δηλώνονται και ως 3,1, και έτσι η σειρά 1 έχει το 3 ως μη αποδεκτό και η σειρά 3 το ένα ως μη αποδεκτό.
Αντί να ψάχνουμε τις λίστες αυτές σειριακά, δουλεύουμε με πίνακα κατακερματισμού και βγαίνει άμεσα η αναζήτηση (αν υπάρχει ή όχι). Υπάρχει και άλλος τρόπος, να κοιτάμε τα νούμερα της λίστας "αποκλεισμών" (για κάθε νούμερο που εξετάζουμε), αλλά με την προυπόθεση ότι και η λίστα των υπαλλήλων είναι και αυτή με κλειδί. Έτσι αν έχουμε π.χ. 30 σχέσεις (τριάντα ζευγάρια όπως το (1,3)), ξεκινάμε από το πρώτο που θεωρούμε ότι θα μείνει, έστω το 1 και "αποκλείουμε" το 3 (βάζουμε 0 εκεί που ήταν 3), μετά πάμε στο επόμενο ζευγάρι, αν το πρώτο νούμερο το βρίσκουμε στο πίνακα 0 τότε το αφήνουμε και πάμε στο επόμενο, μέχρι που και τα τριάντα θα τελειώσουν. Εδώ οι διαφορετικές λύσεις βγαίνουν με ανακάτεμα των κανόνων (των ζευγαριών).
Και ο πρώτος τρόπος (όπως την υλοποίησα) όπως και ο άλλος τρόπος, έχουν την εφαρομογή ανάλογα με το τι έχουμε. Αν έχουμε περισσότερα ζευγάρια από του υπαλλήλους τότε συμφέρει ο πρώτος, αν έχουμε πολλούς υπαλλήλους με μικρό αριθμό ζευγαριών συμφέρει ο δεύτερος.

Ασφαλώς αν μιλάμε για έναν αλγόριθμο που θα έβρισκε όλες τις λύσεις..τότε θέλουμε χιλιετίες για να τις βρούμε! Να προσθέσω εδώ ότι στο δικό μου αλγόριθμο δεν επιλέγω μια τυχαία λύση, ώστε να δω αν βγαίνει, αλλά ξεκινάω με την παραδοχή ότι ο πρώτος διαθέσιμος από μια στοίβα είναι "καλεσμένος", και αποκλείω από τη στοίβα όσους δεν είναι συμβατοί με αυτόν, μετά πάω στον επόμενο (αν είναι 0 τότε πάω στο επόμενο κ.ο.κ). Για το λόγο αυτό πριν ξεκινήσω κάνω ένα ανακάτεμα. Έτσι κάθε φορά που τρέχουμε το πρόγραμμα έχουμε άλλη λύση! Επειδή γράφονται σε στοίβα, στο τέλος αφαιρούνται τα κενά και ζητάμε έναν αριθμό, αλλά θα πάρουμε λιγότερα αν δεν υπάρχει αυτός ο αριθμός, άρα ενδέχεται η λύση που θα βρεθεί να μην είναι ικανοποιητική! Οπότε πάμε για άλλη!

[gbougioukas]

Ασφαλώς αν μιλάμε για έναν αλγόριθμο που θα έβρισκε όλες τις λύσεις..τότε θέλουμε χιλιετίες για να τις βρούμε!

Όχι, δεν μιλάμε για αλγόριθμο που θα έβρισκε όλες τις λύσεις, μία αρκεί.

[bugman]

Η δεύτερη λύση, με την χρήση μόνο των κανόνων είναι πολύ γρήγορη, με το που πατάς το enter παίρνεις την απάντηση!
Αυτό μάλιστα έτρεξε σε Linux με Wine. Δεν χρειάστηκε λίστα, μόνο πίνακες!

ο κώδικας είναι στο blog.

[gbougioukas]

Από όσο μπορώ να καταλάβω από τον κώδικα, πρόκειται για 11 μη-επιτρεπτά ζεύγη. Τι γίνεται για 100.000 μη-επιτρεπτά ζεύγη;

[apoldem]

Το πρόβλημα με την δεξίωση είναι πρόβλημα γράφων. Κατασκευάζουμε αρχικά έναν πλήρη γράφο με τους 500 υπαλλήλους (όλοι είναι συνδεδεμένοι με όλους). Μετά αφαιρούμε τις ακμές με αυτούς που είναι μαλωμένοι. Στον γράφο που θα μείνει ψάχνουμε αν υπάρχει έστω μία κλίκα μεγέθους 150.
Για το πρόβλημα της εύρεσης κλίκας δεδομένου μεγέθους: https://en.wikipedia.org/wiki/Clique_problem#Cliques_of_fixed_size.

Απ' ότι λέει η wikipedia δεν υπάρχει κανένας έξυπνος αλγόριθμος. Το μόνο που μπορούμε να κάνουμε είναι να αποκλείσουμε τους υπαλλήλους με λιγότερες από 150 ακμές, αφού αυτοί σίγουρα δεν μπορούν να να συμμετέχουν σε καμιά κλίκα μεγέθους 150.

Στην χειρότερη περίπτωση (δλδ, κανένας δεν αποκλείεται & όλοι οι έλεγχοι αποτυγχάνουν λίγο πριν βρούμε μια κλίκα & κλίκα τελικά δεν υπάρχει) θα χρειαστούμε (500^150)*(150^2) συγκρίσεις. Παρόλα αυτά το πρόβλημα θεωρείται πολυωνυμικό ως προς το μέγεθος των υπαλλήλων, αφού το 150 είναι fixed και έτσι και το 500^150 είναι ένα πολυώνυμο βαθμού 150.

[evry]

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

Αυτά σε περίπτωση που κάποιος δεν ξέρει κάποιον γρήγορο αλγόριθμο για εύρεση μιας 150-κλίκας.

[bugman]

Έχω βάλει δυο εκδόσεις. Η "Αργή" κάνει 2.2 δευτερόλεπτα για να δώσει τα 150 νούμερα (ταξινομημένα, γιατί στην αρχή τα έχει ανακατεμένα).
Η δεύτερη έκδοση είναι ακαριαία, και με πολύ μικρό κώδικα (μόνο πίνακες). Σε αυτήν ανακατεύω τη σειρά των κανόνων και μετά τους εφαρμόζω άμεσα, δηλαδή παίρνω το πρώτο νούμερο κοιτάω αν δεν έχει αποκλειστεί (Δεν έχει το 0 δηλαδή) και αν όντως δεν έχει παίρνω το δεύτερο και άμεσα αποκλείω το δεύτερο. Ουσιαστικά οι επαναλήψεις είναι όσοι οι κανόνες αλλά όχι σε όλο το μέγεθος του κώδικα γιατί αν έχει αποκλειστεί κάποιο άτομο, τότε δεν κοιτάμε το δεύτερο στο ζευγάρι (του κανόνα). Εδώ η τεχνική λέγεται lookup table. Οι υπάλληλοι είναι σε έναν πίνακα με σημαίες, έτσι ο υπάλληλος 123 έχει σημαία που δείχνει αν έχει αποκλειστεί ή όχι. Οι δείκτες του πίνακα είναι οι κωδικοί των υπαλλήλων. (το πρώτο πρόγραμμα δουλεύει και με νούμερα άσχετα μεταξύ τους, δηλαδή πραγματικούς κωδικούς).

Για γράφους δεν γνωρίζω τίποτα! Δεν το έχω διδαχθεί, ούτε έπεσε ποτέ κάποιο πρόβλημα για να το λύσω.