• Start
• >
• Answers
• >
• One Question

"έτσι ώστε η μικρότερη απ' αυτές να είναι όσο το δυνατό μεγαλύτερη."

Τι εννοείς μικρότερη/μεγαλύτερη; Τα μόνα ουσιαστικά γένους θηλυκού στην εκφώνηση σου είναι οι ακμές και οι κορυφές. Παρόλο που το πρόβλημα αρχικά ακούγεται σαν παραλλαγή του TSP δεν είμαι σίγουρος τι είναι το ζητούμενο.

-- Γιώργος Στρατής _~stratis, April 04, 2005

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

-- Νεόφυτος Δημητρίου _~k2pts, April 04, 2005

Και σε μενα ακουγεται NP-complete το πρόβλημα. Για να φτιάξω ένα ευριστικό θα ακολουθούσα τα ακόλουθα βήματα: 1. βρες όλα τα δυνατά μονοπάτια [ή πολλά απο αυτά αν είναι πάρα πολλά] 2. χρησιμοποίησε κάποια προσέγγιση για να επιλέξεις τα κατάλληλα μονοπάτια α. brute force θα ήταν να αρχίσεις απο το μεγαλύτερο, και μετά να επιλέγεις το αμέσως επόμενο που δεν περιλάμβάνει ακμές απ το προηγούμενο β. χρήση γενετικών αλγορίθμων [ουσιαστικά επιλέγεις κάποια σετ απο μονοπάτια [1η γενεά] στην τυχη και εξετάζεις αν αποτελούν λύση. συνδιάζοντας τα καλύτερα απο αυτά τα σετ, προχωρείς στο επόμενο σετ [2η γενεά], κοκ]

-- Νέαρχος Πασπαλλής _~nearchos, April 04, 2005

Να διευκρινίσω ότι λέγοντας ότι φαίνεται ως παραλλαγή του TSP δεν εννοώ, κατ'ανάγκη, ότι είναι και της ίδιας πολυπλοκότητας. Ας απαντήσει ο Αυγουστίνος τις απορίες που έχουν προκύψει και βλέπουμε.

-- Νεόφυτος Δημητρίου _~k2pts, April 04, 2005

Εδώ θα συμφωνήσω με το Νεόφυτο (για αυτό και ζήτησα να ξεκαθαρίσει ακριβώς το ζητούμενο). Μια μικρή λεπτομέρεια μπορεί να κάνει πολυωνυμική την πολυπλοκότητα του προβλήματος. Πάντως προσωπικά δεν έχω πρόθεση να δω αν ανάγεται το πρόβλημα στο TSP για να αποδείξω αν είναι οντως NP.

-- Γιώργος Στρατής _~stratis, April 04, 2005

Χαίρομαι ιδιαίτερα που βρήκα και άλλα άτομα που ενδιαφέρονται για αλγορίθμους στο phigita.

Το λοιπον. Σας δίνω περεταίρω διευκρινήσεις και απολογούμε που δεν τις έγραψα από την αρχή:

Ο γράφος μας είναι ζυγισμένος (weighted), μη κατευθυνόμενος (undirected) και μπορεί δύο κορυφές (vertices) να ενώνονται με περισσότερες από μία ακμές (edges). Επίσης ο γράφος είναι τέτοιος ώστε να υπάρχει πάντα λύση.

Σ'αυτό το πρόβλημα πρέπει να βρούμε Τ μονοπάτια που να μην μοιράζονται τις ίδιες ακμές (μπορούν να μοιράζονται τις ίδιες κορυφές) που να οδηγούν από την κορυφή υπ' αριθμό 1 στην κορυφή Ν (όπως όρισα την αρίθμηση στην αρχή). Εμείς τώρα θέλουμε να μεγιστοποιήσουμε την μικρότερη ακμή που χρησιμοποιούμε στα μονοπάτια αυτά. Δηλαδή η μικρότερη ακμή που περιέχεται στα Τ αυτά μονοπάτια να είναι όσο το δυνατό μεγαλύτερη.

Σημαντική σημείωση : Δεν θέλουμε να βρούμε τα μονοπάτια αλλά την μεγαλύτερη τιμή/βάρος που μπορεί να έχει η μικρότερη των ακμών στα μονοπάτια αυτά

-- Αυγουστίνος Καδής _~avgoustinos, April 04, 2005

Ναι όντως μοιάζει με TSP. Το μόνο που μπορούμε να επισκεφτούμε μια κορυφή πολλές φορές.

Πάντως η πολυπλοκότητά του πρέπει να είναι πολυωνυμική αφού σήμερα το πρωί έχω βρει μια λύση Ο(Ν^5) [βελτιωμένη φυσκά].

Ξεκινώ με τον γράφο χωρίς ακμές και του βάζω με σειρά τις μεγαλύτερες (εάν υπάρχουν ακμές με το ίδιο βάρος τις βάζω όλες επειδή δεν επηρεάζεται η απάντηση - θα δείτε σε λίγο).
Κάθε φορά που βάζω μια ακμή (ή περισσότερες αν έχουν το ίδιο βάρος) τρέχω τον αλγόριθμο του Ford-Fulkerson (Maximum Flow) με πολυπλοκότητα Ο(E|f|) [E αντιστοιχεί στο P (= Ν^2) μας και f (flow) αντιστοιχεί στο T (=Ν)] βάζοντας σε κάθε ακμή χωρητικότητα 1 (capacity = 1) και αρχική ροή 0 (initial flow).
Μόλις βρεθούν Τ αυξητικά μονοπάτια [στον αλγόριθμο της μέγιστης ροής] (augmenting paths) σταματώ και η απάντηση είναι το βάρος της τελευταίας ακμής που πρόσθεσα στον γράφο.

(ελπίζω να καταλάβετε τι έκανα επειδή δεν έχω χρόνο τώρα για περισσότερες λεπτομέριες θα επανέρθω απόψε)

Έτσι η πολυπλοκότητά του γίνεται : Ο(PΕ|f|) δηλ Ο(N^2 N^2 T) = O(N^4*N) = O(N^5).

Επίσης για κλάδεμα (prunning) επειδή πρέπει Τ γειτονικές ακμές των 1 και 7 αντίστοιχα να είναι μέσα στον γράφο μας [για να μπορούν να σχηματιστούν Τ μονοπάτια], βάζω τις Τ πιο μεγάλες απ'αυτές (Τ στην κορυφή 1 και Τ στην κορυφή 7) και ταυτόχρονα όλες τις ακμές του γράφου που είναι μεταλύτερες και ίσες μ'αυτές.

Τώρα ψάχνω για κανένα θεώρημα που να μας λέει πότε μπορούν να υπάρχουν Τ ξεχωριστά μονοπάτια σε ένα γράφο.

-- Αυγουστίνος Καδής _~avgoustinos, April 04, 2005

Άσχετο, αλλά που σπουδάζεις Αυγουστίνο;

-- Χάρης Μιλητός _~harry, April 05, 2005

Ο Αυγουστίνος έχει μόλις αποφοιτήσει από το λύκειο κι υπηρετεί τη θητεία του σε στρατόπεδο της Λευκωσίας. Είναι —κατά την ταπεινή μου γνώμη— το λαμπρότερο αστέρι της πληροφορικής που έβγαλε ποτέ αυτός ο τόπος και να σημειωθεί ότι τυγχάνει να γνωρίζω πράγματα και καταστάσεις εδώ στην Κύπρο για να μπορώ να κρίνω. Είναι μεγάλη αδικία που έχει να υποστεί την αχρείαστη ταλαιπωρία ενός πανεπιστημίου που δεν είναι ισάξιο του. Πραγματικά λυπάμαι γι αυτό!…

Δεν ισχυρίζομαι ότι δεν θα έχει τη συμπαράσταση των καθηγητών του. Ούτε ακόμη ότι δεν θα τον βοηθήσουν —αν θέλουν— να πάει στα καλύτερα πανεπιστήμια. Το πρόβλημα φοβάμαι είναι ότι έχουν μετρηθεί και βρέθηκαν λίγοι για το σκοπό που επιτελούν πόσω μάλλον για να φέρουν ένα φοιτητή της τάξης του Αυγουστίνου στο επίπεδο που μπορεί να φτάσει.

-- Νεόφυτος Δημητρίου _~k2pts, April 05, 2005

Off topic.

Νεόφυτε, ξέρεις όλους τους πληροφορικαραίους που έβγαλε ποτέ η Κύπρος;

-- Γιώργος Στρατής _~stratis, April 05, 2005

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

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

Δεν ξέρω, αλλά στην Κύπρο μπορεί να χαραμισθεί το ταλέντο του, και είναι κάπως κρίμα.

-- Χάρης Μιλητός _~harry, April 05, 2005

Ξέρω αρκετούς… για να μπορώ να λέω αυτά που λέω χωρίς να φοβάμαι οτιδήποτε. Αν θέλεις όμως να κάνεις challenge αυτό που λέω μπορείς να μου φέρεις ένα αντιπαράδειγμα και τότε θα ανακαλέσω χωρίς δεύτερη σκέψη. Εγώ πάντως δεν έχω βρει και δεν έχω δει τέτοιο από το 1994 που γνωρίζω τι γίνεται με τις ολυμπιάδες πληροφορικής καθώς επίσης και δεν έχω βρει και δεν έχω δει κάτι επιδικτύως που να μου αποδεικνύει το αντίθετο. Θα μου πεις βέβαια, τι γίνεται με όλους αυτούς που δεν πήγαν σε ολυμπιάδες, δεν πήγαν στα πανεπιστήμια που ξέρεις, διάπρεψαν αλλά τα έργα τους δεν είναι επιδικτύως; Τότε, δικαιολογημένα, μπορείς να με χαρακτηρίσεις ως άπιστο. Θέλω να δω για να πιστέψω!..

-- Νεόφυτος Δημητρίου _~k2pts, April 05, 2005

Δε βαριέσαι, απλά ρώτησα. Αφού μιλούμε για αλγόριθμους, είναι φοβερός ο νέος αλγόριθμος αναζήτησης που μόλις περιέγραψες (πολυπλοκότητα Ο(1)). Νόου τσάλεντζ χίαρ ντουντ, ο καθένας πιστεύει ότι του αρέσει.

-- Γιώργος Στρατής _~stratis, April 05, 2005

Αφού ξέρεις ότι ΔΕΝ ξέρεις όλα τα άτομα της πληροφορικής που έβγαλε αυτός ο τόπος, γιατί δεν αλλάζεις την πρότασή σου από το λαμπρότερο αστέρι της πληροφορικής που έβγαλε ποτέ αυτός ο τόπος, σε το λαμπρότερο αστέρι της πληροφορικής που έβγαλε ποτέ αυτός ο τόπος από όσους γνωρίζω;

Ζητάς αντιπαράδειγμα για να διαψευστεί η πρότασή σου, θεωρείς αυτόν καλό τρόπο απόδειξης της;

-- Κωνσταντίνος Κωνσταντίνου _{~constandinos}, April 05, 2005

Τσίαρς ττου δατ ;)

-- Νεόφυτος Δημητρίου _~k2pts, April 05, 2005

Κων/νο, το κατά την ταπεινή μου γνώμη είναι ελληνικά νομίζω. Ποια λέξη του δεν κατάλαβες ακριβώς;

-- Νεόφυτος Δημητρίου _~k2pts, April 05, 2005

  Ζητάς αντιπαράδειγμα για να διαψευστεί η πρότασή σου, θεωρείς αυτόν καλό τρόπο απόδειξης της;

Και για να απαντήσω την αρχική σου ερώτηση: ΝΑΙ τον θεωρώ καλό τρόπο απόδειξης σε περιπτώσεις που υπάρχει ελλειπής γνώση. Πρόκειται ακριβώς για ένα ισχυρισμό που γίνεται κάτω από την υπόθεση του κλειστού κόσμου (δηλαδή, αυτά που τυγχάνει να γνωρίζω και να πιστεύω εγώ). Σε περίπτωση που κάποιος έχει να προβάλει πειστικά επιχειρήματα τότε θα ήμουν ενδεχομένως διατεθειμένος να ανακαλέσω.

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

Έχοντας αναφέρει τα παραπάνω, μπορεί να εξακολουθείς να θέλεις να πιστέψεις κάτι διαφορετικό κι αυτό το σέβομαι. Αυτό όμως δεν μειώνει κατά τίποτα το τι πιστεύω εγώ —όντας αυτός που είμαι, όποιος κι αν είμαι— για κάποιων δεκαοκτώ χρονών που έχει ξεφυλλίσει το βιβλίο των CLR και κατέχει —τουλάχιστον— τις βασικές αρχές προγραμματισμού σε αντίθεση ακόμη και με πολλούς από τους αποφοιτήσαντες σε κλάδους πληροφορικής.

-- Νεόφυτος Δημητρίου _~k2pts, April 05, 2005

Βασικά, η γνώμη σου, δεν είναι ταπεινή.

-- Κωνσταντίνος Κωνσταντίνου _{~constandinos}, April 05, 2005

Τότε, απλά κατά την γνώμη και σ'ευχαριστώ που με διορθώνεις.

-- Νεόφυτος Δημητρίου _~k2pts, April 05, 2005

Τότε, απλά κατά την γνώμη [μου] και σ'ευχαριστώ που με διορθώνεις.

-- Νεόφυτος Δημητρίου _~k2pts, April 05, 2005

Αυγουστίνε, συγγνώμη αν έπαιξα τον ρόλο της "σιεροκουτάλας". Τελικά μια ερώτηση κάνω και όλοι τσακώνονται ! LOL :P.

-- Χάρης Μιλητός _~harry, April 05, 2005

Κων/νο, απολογούμαι που ήμουν εριστικός. Σήμερα δεν είναι μια από τις καλύτερες μου μέρες. «Ζώντας και ψευτοζώντας» που λέει κι ο ποιητής.

-- Νεόφυτος Δημητρίου _~k2pts, April 05, 2005

Συγχωρώ σε. Κατά βάθος είμαι καλός! :-)

-- Κωνσταντίνος Κωνσταντίνου _{~constandinos}, April 05, 2005

Τώρα μπόρεσα και εγώ να μπω στο διαδίκτυο. Περίμενα με ανυπομονησία να δω τι λύσεις βρήκατε και εσείς. Μόλις είδα ότι είχα 26 απαντήσεις τρελάθηκα. Νόμιζα ότι θα το έχουμε ξεσκίσει το πρόβλημα. Αλλά έκανα λάθος όμως. Όπως και να έχει εγώ δεν πρόκειται να επέμβω στην συζήτησή σας για μένα και ελπίζω να λήξει σύντομα επειδή δεν ωφελεί σε τίποτα. Επίσης δεν μπορώ να ακούω για πανεπιστήμια όταν έχω ακόμα 17 μήνες μπροστά μου :) Όσο για το πρόβλημά μας, βρήκα ακόμη μια καλύτερη λύση. Μάλλον βελτίωση:

Αντί κάθε φορά που προσθέτω μια καινούρια ακμή στον γράφο, να τρέχω τον αλγόριθμο για μέγιστες ροές (Ford-Fulkerson) και να ξαναυπολογίζω από την αρχή όλα τα αυξητικά μονοπάτια (για να βρω την μέγιστη ροή), θα ψάχνω για ένα μόνο αυξητικό μονοπάτι πάνω στο δίκτυο που υπάρχει μέχρι στιγμής.

Σημειώνω πως ψάχνω μόνο ένα αυξητικό μονοπάτι επειδή προσθέτω μόνο μια ακμή με ροή 1. Έτσι η πολυπλοκότητα του αλγορίθμου μας πέφτει στο Ο(PE) = Ο(P^2) = O(N^4) αλλά πιστεύω πως γενικότερα θα έχει πολύ καλές επιδόσεις.

Τώρα δεν ξέρω αν έχετε την ώρα και την όρεξη να βρείτε πιο γρήγορη λύση αλλά οποιεσδήποτε βελτιώσεις είναι ευπρόσδεκτες.

Δεν πρέπει να ξεχάσω να σας ευχαριστήσω και για τα καλά σας λόγια …

Στον Γιώργο: Για ποιον αλγόριθμο μιλάς με πολυπλοκότητα Ο(1); Αναφερόσουν στα σχόλια του Νεόφυτου ή στον αλγόριθμό μου;

-- Αυγουστίνος Καδής _~avgoustinos, April 05, 2005

Αυγουστίνο, στην 1η έκδοση του αλγόριθμου σου τι είναι το 7;

Επίσης, δεν γνωρίζω κανέναν θεώρημα που να σου λέει πότε ένα γράφημα έχει Τ διαφορετικά μονοπάτια, αλλά φαντάζομαι αυτό το έλυσες ήδη με τον αλγόριθμο σου [αν υπάρχει ροή τουλάχιστον Τ σε ένα γράφο που αντιστοιχείς χωρητικότητα ακριβως 1 σε κάθε ακμή, τότε ΠΡΕΠΕΙ να υπάρχουν τουλάχιστον Τ ξεχωριστά μονοπάτια: η απόδειξη δεν είναι δύσκολη!].

-- Νέαρχος Πασπαλλής _~nearchos, April 06, 2005

Για το ’κλάδεμα’ που κάνεις αφήνωντας μόνο τις Τ μεγαλύτερες ακμές των 1 και Ν έχω τις αμφιβολίες μου! Αυτό θα ήταν σωστό, αν άφηνες μόνο τις Τ μεγαλύτερες ακμές ΓΙΑ ΚΑΘΕ κορυφή που ήταν συνδεδεμένη με την 1 [ή αντίστοιχα την Ν].

Φυσικά μπορώ να κάνω λάθος, αλλα καλό είναι να το διευκρινήσουμε.

-- Νέαρχος Πασπαλλής _~nearchos, April 06, 2005

Αν έχω ερμηνεύσει σωστά τα στοιχεία που παράθετεις τότε πρόκειται για το πρόβλημα των ξένων μονοπατιών ως προς τις ακμές τους —μια αναζήτηση για τους όρους edge-disjoint + paths + problem + multiflows θα σου αποκαλύψει τη γνώση που αναζητείς. Το εν λόγω πρόβλημα έχει διαφορετική πολυπλοκότητα για κατευθυνόμενους (NP-hard) και μη-κατευθυνόμενους γράφους. Τα παρακάτω θεωρήματα μπορεί να είναι, μπορεί και να μην σου είναι χρήσιμα:

  Max-flow Min-cut Theorem, Ford Fulkerson [1956]
  In every network, the maximum value of a feasible flow equals the minimum capacity of a source/sink cut.

  Integrality Corollary
  If all capacities in a network are integers, then there is a maximum flow assigning integral flow to each edge. Furthermore, some maximum flow can be partitioned into flows of unit value along paths from source to sink.

-- Νεόφυτος Δημητρίου _~k2pts, April 06, 2005

Η πολυπλοκότητα Ο(1) αναφερόταν στον ευρετικό αλγόριθμο αναζήτησης του Νεόφυτου (ήταν αστείο… τελικά όχι τόσο αστείο). Βασικά τρέχει ένα priority queue. Κάθε φορά που γνωρίζει/ακούει για κάποιον, αναθέτει στο άτομο μια τιμή, και αναλόγως της τιμής τον εισάγει στην αντίστοιχη θέση του priority queue. Επειδή πάντα αυτός με την πιο ψηλή τιμή είναι πρώτος, η αναζήτηση γίνεται σε σταθερό χρόνο. Μπορεί εύκολα να αποδειχθεί ότι η μέθοδος αυτή προσεγγίζει μονοτονικά την πραγματική λύση καθώς ο Νεόφυτος γνωρίζει περισσότερους Κυπραίους πληροφορικαραίους (κάνοντας την υπόθεση ότι ο Νεόφυτος χρησιμοποιεί σωστά κριτήρια και είναι ακριβοδίκαιος). Αστείο και πάλι, μην εξάπτεστε.

-- Γιώργος Στρατής _~stratis, April 06, 2005

Απολογούμαι Νέαρχε για το 7. Το 7 είναι το Ν του δοκιμαστικού γράφου που σχεδίασα στο χαρτί. Να το υπολογίζεις σαν Ν. Όσον αφορά τις Τ γειτονικές ακμές του 1 και του Ν είμαι σίγουρος πως είναι σωστο. Μάλλον δεν το εξήγησα σωστά για να το καταλάβετε. Η σκέψη μου ήταν πως για να υπάρχουν Τ μονοπάτια που να οδηγούν από το 1 στο Ν πρέπει να χρησιμοποιηθούν Τ γειτονικές ακμές του 1 και του Ν αντίστοιχα. (Δηλαδή δεν υπάρχει περίπτωση να έχουν λιγότερες από Τ γειτονικές οι 1 και η Ν στην τελική απάντηση). Έτσι δεν υπάρχει περίπτωση η απάντησή μας να είναι μεγαλύτερη από την μικρότερη απ' αυτές τις Τ ακμές. Δηλαδή, εάν πάρω τις Τ μεγαλύτερες ακμές γειτονικές του 1 ή του Ν, δεν υπάρχει περίπτωση η απάντησή μας να είναι μεγαλύτερη από την μικρότερη αυτών των ακμών επειδή εάν δεν χρησιμοποιηθούν αυτές οι Τ ακμές θα χρησιμοποιηθούν μικρότερες (γειτονικές του 1 ή του Ν) –> μικρότερη απάντηση. Έτσι ξεκινώ την αναζήτησή μου για ακμές μεγέθους ίσου με την μικρότερη από τις Τ πιο μεγάλες γειτονικές του 1 ή του Ν.

-- Αυγουστίνος Καδής _~avgoustinos, April 06, 2005

Ευχαριστώ Νεόφυτε για τα σχόλιά σου. Απ' ότι φαίνεται (χρησιμοποιώντας την αναζήτηση που προτείνεις) το πρόβλημα που προσπαθούμε να λύσουμε είναι το finding edge-disjoint paths πάνω σε μή κατευθυνόμενο γράφο με τον τον περιορισμό ότι πρέπει να χρησιμοποιούνται όσο μεγαλύτερες ακμές γίνεται. Και αυτό λύνεται με δίκτυα. Τότε πρέπει να το προσεγγίσαμε σωστά το πρόβλημα. Ωραία. Πάμε καλα … Τα πρώτο από τα θεωρήματα που έγραψες το έχω υπόψην μου και το χρησιμοποίησα για να αποδείξω πως προσθέτωντας μια ακμή χωριτηκότητας 1 στον γράφο η ροή μπορεί να αυξηθεί κατά 1 μόνο. Έτσι τρέχω μόνο μια φορά τον αλγόριθμο που βρίσκει επαυξητικά μονοπάτια κάθε φορά που βάζω μια ακμή.

-- Αυγουστίνος Καδής _~avgoustinos, April 06, 2005

Αν και υπάρχει κάποια δόση ειρωνείας στον αλγόριθμό σου έχει την πλάκα του. Ξεχνάς όμως και την πολυπλοκότητα του να μάθει τα άτομα ο Νεόφυτος που είναι περισσότερη από Ο(lgN) επειδή χρειάζεται και κάποιο preprocessing. Το μόνο που είμαι σίγουρος διαβάζοντας αυτόν τον αλγόριθμο είναι πως είσαι και εσύ έτσι ταραμένος σαν και εμένα. Σκέφτου εγώ πριν λίγο καιρό σκεφτόμουνα αλγόριθμο για να ελαχιστοποιήσω τον χρόνο της εφόδου μου! (κάνοντας έφοδο Ν άτομα ταυτόχρονα με διαφορετικές διαδρομές…) Νεόφυτε, δεν φαντάζομαι να πειράχτηκες από την ανάλυση της πολυπλοκότητας του τρόπου σκέψης σου :)

-- Αυγουστίνος Καδής _~avgoustinos, April 06, 2005

Απολογούμαι που δεν ξεχώρησα τις παραγράφους στις προηγούμενες 3 απαντήσεις μου

-- Αυγουστίνος Καδής _~avgoustinos, April 06, 2005

  Νεόφυτε, δεν φαντάζομαι να πειράχτηκες από την ανάλυση της πολυπλοκότητας του τρόπου σκέψης σου :)

Καθόλου ;)

-- Νεόφυτος Δημητρίου _~k2pts, April 06, 2005

Η έφοδος είναι η καλύτερη εφαρμογή του TSP. Είχα λύσει το πρόβλημα για το στρατόπεδο που υπηρέτησα (Τσέρι). Εδώ πρέπει να σημειώσω ότι στην αρχή είχα τεράστια προβλήματα με το περίπολο. Λόγω της στοχαστικότητας της κίνησης του κάποιες ακμές είχαν μεταβλητό μήκος (ή και αγνωστο αναλόγως του που θα αποφάσιζε να τακκώσει* ο περιπολάρχης) και απογοητεύτηκα πλήρως. Λίγο μετά συνειδητοποίησα ότι είναι πιο εύκολο να συμφωνώ με τον περιπολάρχη που να τακκώννει σε συγκεκριμένη ώρα. Θίνκινγκ άουτ οβ δε ποξ που λεν και οι εγγλέζοι.

*τακκώννω = κολοβαρώ

-- Γιώργος Στρατής _~stratis, April 06, 2005

Είσαι ωραίος!

-- Αυγουστίνος Καδής _~avgoustinos, April 06, 2005

Ήρθε επιτέλους και ο Γιάννης να γράψει στο phigita! Τι κάνεις ρε Νεόφυτε, με θυμάσαι ή μας ξέχασες? Πως τα περνάτε? Σκεφτόμουν και εγώ να στέλνω κανά προβληματάκι στο site για επίλυση! Όσο αφορά τον Αυγουστίνο είναι όντως ο ΚΑΛΥΤΕΡΟΣ στην πληροφορική σε ΕΛΛΑΔΑ ΚΑΙ ΚΥΠΡΟ αυτή τη στιγμή αν και άτυχος στους διαγωνισμούς!!! ΥΓ: Μπήκα ομάδα μαθηματικά Νεόφυτε βασικός!!!

-- Γιάννης Παναγέας _~panageasj, April 11, 2005

Γιάννη, καλώς όρισες και νιώθε άνετα να συμμετέχεις κι εσύ στην κοινότητα. Δεν νομίζω να διαφωνεί κανένας απ'όσους σε γνωρίζουν ότι σκίζεις στα μαθηματικά —όσοι ήταν στη Λευκάδα πέρσι το καλοκαίρι, ξέρουν τι εννοώ ;). Συγχαρητήρια πάντως για την επιτυχία σου και ευχές για κάθε καλό στο μέλλον!..

ΥΓ. Συντακτικό Σχόλιο-Υπενθυμίση: Νεόφυτε και Γιάννη είστε εκτός θέματος ;)

-- Νεόφυτος Δημητρίου _~k2pts, April 11, 2005

Πρέπει να σημειώσουμε πως ο Γιάννης διακρίθηκε στην Πανελλήνια Ολυμπιάδα Μαθηματικών και θα συμμετάσχει φέτος το καλοκαίρι στην Βαλκανική και Παγκόσμια Ολυμπιάδα Μαθηματικών στην Ρουμανία και Μεξικό αντίστοιχα.

Είναι μαθηματική διάνοια ο τύπος. Όχι πως στην Πληροφορική μένει πίσω.

-- Αυγουστίνος Καδής _~avgoustinos, April 11, 2005

Φύτο, τελικά νομίζω το phigita θα πρέπει να ονομαστεί Mensa. :)

ΥΓ: Ελπίζω τα παιδιά να εκλάβουν στο σχόλιο ως κομπλιμέντο. Μπράβο και στους δυο.

-- Χάρης Μιλητός _~harry, April 11, 2005