Απορία στα προβλήματα βελτιστοποίησης.

Ξεκίνησε από Avengeil, 05 Ιουν 2014, 09:33:53 ΜΜ

« προηγούμενο - επόμενο »

Avengeil

Καλησπέρα,
       η απορία μου προέρχεται από ένα περσινό Σ-Λ στα επαναληπτικά.
    Αναφέρει: Η εύρεση του μικρότερου από πέντε αριθμούς είναι πρόβλημα βελτιστοποίησης.

Έχει κανείς το χρόνο και τη διάθεση να μου εξηγήσει πώς βγαίνει λάθος?

Ευχαριστώ εκ των προτέρων και για τη βοήθεια στο παραπάνω αλλά γενικότερα την όλη προσφορά μέσω του site.

Αποστολάτος Άκης

Καλησπέρα.. Αν εισαι μαθητης(μαθητρια) καλή επιτυχία αυριο. Βελτιστοποίηση σημαίνει ότι επιλέγω από αρκετές λύσεις εκεινη που ικανοποιεί καλύτερα καποιο κριτήριο. Το να βρεις το ελάχιστο δεν είναι βελτιστοποίηση, είναι υπολογισμος. βελτιστοποίηση θα ήταν αν είχες αρκετές λύσεις κ με καποιο κριτήριο ξεχώριζες μια. πχ τη μικροτερη λύση της x^2 - 10*x - 2 = 0 (δυολύσειε - επιλέγεις τη μικρότερη)

Avengeil


petrosp13

Παπαδόπουλος Πέτρος
Καθηγητής Πληροφορικής


petrosp13

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

nikolasmer

Μερεντίτης Νικόλαος
Πληροφορικός

evry

Προφανώς και είναι λάθος.
Με το σκεπτικό αυτό και ο υπολογισμός αθροίσματος ειναι πρόβλημα βελτιστοποίησης αφού το άθροισμα γίνεται update σε κάθε επανάληψη.
(Για την ιστορία στις απαντήσεις της επιτροπής ήταν Λάθος. Το θυμάμαι γιατί τότε ήμουν συντονιστής στο ένα από τα 2 βαθμολογικά επαναληπτικών που υπάρχουν στη χώρα)

Γενικά σε αυτό το μάθημα λέμε ότι όταν ένα πρόβλημα έχει πολλές λύσεις και επιλέγουμε αυτή με το ελάχιστο κόστος, αυτό είναι πρόβλημα βελτιστοποίησης.
Φυσικά υπάρχει και μια άλλη έννοια της βελτιστοποίησης που έχει τις ρίζες της στην αριθμητική ανάλυση αλλά νομίζω ότι οι συγγραφείς δεν είχαν αυτό υπόψιν τους. Το αντίστοιχο εδάφιο στο βιβλίο είναι ξεκάθαρο. π.χ. συντομότερο μονοπάτι (dijkstra), TSP, κλπ.

Όπως και να έχει, φυσικά εξαρτάται από το τι ορίζουμε πρόβλημα βελτιστοποίησης, αλλά το να χαρακτηρίσουμε την εύρεση ελαχίστου μιας σειράς αριθμών ως πρόβλημα βελτιστοποίησης θα ήταν μάλλον εκφυλλισμός του ορισμού όπως τον αντιλαμβανόμαστε εμείς οι πληροφορικοί.
Οι οικονομολόγοι-μαθηματικοί εξετάζουν προβλήματα βελτιστοποίησης χωρίς περιορισμούς όπου έχεις μόνο την αντικειμενική συνάρτηση. Εδώ ίσως να κόλλαγε το ελάχιστο. Αλλά πάλι είναι ακραίο. Με βάση αυτά που λέει το βιβλίο νομίζω δεν υπάρχει περιθώριο να το χαρακτηρίσει κάποιος σωστό.
What I cannot create I do not understand -- Richard Feynman
http://evripides.mysch.gr

petrosp13

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

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