Προβλήματα Μαθηματικών

Δεκέμβριος 15, 2008

Μπείτε στη σειρά

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 12:29 πμ

queue

N ρομπότ βρίσκονται σε μια πόλη (N τεράστιο) και πρέπει να πάνε στο γιατρό. Κάθε ένα από αυτά ξέρει ποιο ρομπότ είναι το αμέσως προηγούμενό του (αυτό που θα μπει στο ιατρείο δηλ. αμέσως πριν από αυτό), και φυσικά το ρομπότ που θα μπει πρώτο το γνωρίζει.

Τα ρομπότ είναι πολυάσχολα και δεν τους αρέσει να σπαταλάνε το χρόνο τους, γι’ αυτό και το κάθε ρομπότ θέλει να μάθει ποια είναι η σειρά του (αν είναι το 1ο που θα μπει, το 2ο, το τελευταίο κλπ). Θέλουν λοιπόν, συνεργαζόμενα μεταξύ τους, να υπολογίσει το κάθε ένα τη σειρά του.

Οποιοδήποτε ρομπότ μπορεί να επικοινωνήσει (ασύρματα) με οποιοδήποτε άλλο. Επίσης όλα τα ρομπότ είναι συγχρονισμένα, κάνουν δηλ. από μια λογική πράξη κάθε δευτερόλεπτο.

Ένας απλός τρόπος είναι ο 1ος να το πει στον 2ο, ο 2ος στον 3ο κ.ο.κ. Αυτός ο τρόπος παίρνει χρόνο ανάλογο του N για να υπολογίσει τη σειρά του καθενός.

Βρείτε ένα τρόπο να γίνει αυτός ο υπολογισμός πολύ πιο γρήγορα.

Advertisements

11 Σχόλια »

  1. Νομίζω πως σκέφτηκα το προφανές αλλά επειδή κανένας άλλος δεν έχει δώσει μια απάντηση αποφάσισα να αναρτήσω το σκεπτικό μου.
    Εφόσον το 1ο στην σειρά robot γνωρίζει ότι είναι πρώτο και κάθε robot γνωρίζει πιο robot είναι το αμέσως προηγούμενο στην σειρά τότε σίγουρα ξέρουμε και το τελευταίο robot γιατί είναι αυτό που ξέρει πως δεν έχει κανένα άλλο robot πίσω του και επομένως ξέρουμε και το προτελευταίο είναι αυτό που έχει ως πισινό του το τελευταίο robot.

    Άρα τα ρομπότ μπορούν να στοιχίζονται αμφίδρομα ένα στην αρχή και ένα στο τέλος μέχρι να τελειώσουν την στοίχιση τους κάπου στην μέση σε χρόνο N/2 δηλαδή.

    Έχω σκεφτεί και μερικές μεθόδους πολύ γρηγορότερες αλλά έχω κάποιες απορίες…

    Τα robot γνωρίζουν τον πληθυσμό τους; πχ (αν N=3.000.000) τα robot γνωρίζουν πως συνολικά είναι 3.000.000; η απλά ξέρουν πως είναι πολλά;

    Μπορούν να κάνουν μια λογική διεργασία κάθε δευτερόλεπτο αλλά είναι απαραίτητο όλη η Ν ομάδα robot να επεξεργάζεται μια κοινή λογική διεργασία; Δεν μπορούν τα robot ας πούμε να χωριστούν σε ομάδες (έστω τυχαίας σειράς και πληθυσμού) και η κάθε ομάδα να επεξεργάζεται την «δική της» λογική διεργασία ανά μονάδα χρόνου;

    Μου αρέσει!

    Σχόλιο από johnstef — Δεκέμβριος 21, 2008 @ 11:00 πμ

  2. johnstef:

    «Κάθε ρομπότ γνωρίζει το αμέσως προηγούμενό του στη σειρά» σημαίνει ότι γνωρίζει μετά από ποιό ρομπότ θα επισκεφτεί το γιατρό. Επομένως το τελευταίο δε γνωρίζει αρχικά ότι είναι τελευταίο. Βέβαια θα μπορούσε εύκολα να το μάθει σε ένα βήμα, όμως ο αλγόριθμος μπορεί να γίνει πολύ ταχύτερος από Ν/2.

    Σχετικά με τις άλλες ερωτήσεις σου, τα ρομπότ δεν γνωρίζουν πόσα είναι, και μπορούν να χωριστούν σε ομάδες (ακόμη και ομάδες του ενός) που κάθε μια θα κάνει τη δική της επεξεργασία.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Δεκέμβριος 21, 2008 @ 12:58 μμ

  3. “Κάθε ρομπότ [u]γνωρίζει[/u] το [b]αμέσως προηγούμενό[/b] του στη σειρά” άρα το robot εκείνο που δεν θα γνωρίζει κάποιο robot ως αμέσως προηγούμενο του στην σειρά (επειδή δεν υπάρχει) ξέρει ότι είναι το τελευταίο 🙂

    Όμως κατάλαβα που στοχεύει αυτό σας το σχόλιο. 🙂

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

    Μου αρέσει!

    Σχόλιο από johnstef — Δεκέμβριος 21, 2008 @ 5:17 μμ

  4. Οκ συγγνώμη το παρεξήγησα (και δεν επιδέχεται διόρθωση το σχόλιο μου γι’ αυτό στέλνω νέο σχόλιο) απλά κατάλαβα την διαδικασία “ανάποδα” όταν αναρτούσα την απάντηση μου 🙂

    Μου αρέσει!

    Σχόλιο από johnstef — Δεκέμβριος 21, 2008 @ 5:23 μμ

  5. Υπόδειξη:

    Κάθε robot κατ’ αρχήν ρωτάει το μπροστινό του (αυτόν που μπαίνει αμέσως πριν από αυτό στο ιατρείο) ποιο robot είναι το μπροστινό του. Μετά …

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Φεβρουαρίου 3, 2009 @ 11:17 μμ

  6. ειναι της τάξης του λογάριθμου του Ν με βάση το 2

    Μου αρέσει!

    Σχόλιο από vangelisvangelis — Απρίλιος 21, 2009 @ 12:04 μμ

  7. vangelisvangelis

    Σωστό αλλά γιατί;

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 22, 2009 @ 8:53 μμ

  8. Μετά την πρώτη ερώτηση κάθε robot έχει μάθει τα 2 (2 στην πρώτη) μπροστινά του (1 <= Μπροστινά <= 2 ) (π.χ. α, β). Έπειτα κάθε robot ρωτάει (δεύτερη ερώτηση) αυτό που του έδειξε το μπροστινό του (το β) ποια είναι κατά σειρά τα μπροστινά του και μαθαίνει τα 4 (συνολικά) (2 στην δεύτερη) μπροστινά του (2 <= Μ <= 4 ) (α, β, γ, δ) (γιατι και το β με αντίστοιχο τρόπο είχε μάθει τα 2 μπροστινά του). Έπειτα κάθε robot θα ρωτήσει (τρίτη ερώτηση) το τελευταίο στη σειρά που του υποδείχθηκε (το δ, το οποίο με τη σειρά του έχει μάθει τα 4 μπροστινά του) και θα μάθει τα 8 (2 στην τρίτη) μπροστινά του (4 <= Μ <= 8)…
    Στην Χ-οστή ερώτηση κάθε robot θα μάθει τα 2 στην Χ μπροστινά του που στη χειρότερη περίπτωση είναι της τάξης του Ν. Το Χ λοιπόν είναι ο λογάριθμος του Ν με βάση το 2. Λαμβάνοντας υπόψη ότι κάθε ερώτηση, απάντηση και πράξη χρειάζεται ένα δευτερόλεπτο τα συνολικά δευτερόλεπτα είναι της τάξης του λογάριθμου του Ν με βάση το 2.

    Μου αρέσει!

    Σχόλιο από vangelisvangelis — Απρίλιος 23, 2009 @ 4:38 μμ

  9. vangelisvangelis

    Λίγη προσοχή στη λεπτομέρεια: έτσι που περιγράφεις τον αλγόριθμό σου το κάθε ρομπότ μαθαίνει τελικά όλα τα μπροστινά του. Αυτό δε μπορεί να γίνει σε χρόνο O(\log N) αφού και μόνο το να διαβάσει το ποια είναι αυτά απαιτεί χρόνο \gtrsim N.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 23, 2009 @ 8:04 μμ

  10. Σωστό. Ας πούμε λοιπόν πως τα robot κρατούν δύο μεταβλητές μια για τη σειρά τους και μια για το ποιος είναι ο μπροστινός τους. Στην αρχή θέτουν τη μεταβλητή «σειρά» ιση με 1 και τη μεταβλητή «μπροστινός» με τον μπροστινό τους εκτός από τον πρώτο που δεν έχει. Κάθε robot ζητάει τις δύο αυτές μεταβλητές. Με μια προσθεση κάθε φορά βρίσκει τη σειρά του. Με το πέρασμα της δεύτερης μεταβλητής στην ουσία ζητάει από αυτόν που του υπεδειξε αυτός που ρώτησε, να του δείξει ποιον του έδειξε για μπροστινό του ο προηγούμενος που ρώτησε. Αυτό γίνεται όσο η μεταβλητή δεν είναι κενή που σημαίνει οτι έχει φτάσει στον πρώτο. Έτσι δεν χρειάζεται να διαβάσει όλα αυτά που είναι μπροστά του.

    Μου αρέσει!

    Σχόλιο από vangelisvangelis — Απρίλιος 27, 2009 @ 12:37 μμ

  11. Ωραία.

    Αυτή η τεχνική ονομάζεται pointer jumping.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Απρίλιος 27, 2009 @ 12:42 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: