Β Φάση 20ου ΠΔΠ

Συζητήσεις για προετοιμασία για τον διαγωνισμό, online διαγωνισμούς, βιβλία προγραμματισμού και αλγορίθμων, και όλων των σχετικών.
Απάντηση
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Β Φάση 20ου ΠΔΠ

Δημοσίευση από thetrojan01 »

Γεια σας, παιδιά!

Μπορεί κάποιος να μου εξηγήσει πώς λύνεται το sabotage, δηλαδή το θέμα Β φάσης του 20ου ΠΔΠ? Εκεί είχα κολλήσει και δεν τα κατάφερα. Και δεν καταλαβαίνω τον τρόπο όταν διαβάζω τον κώδικα ενδεικτικών λύσεων που έχουν δημοσιευθεί.

Α) Αν μπορείτε παρακαλώ να μου πείτε τουλάχιστον πώς θα δοκιμαστούν όλες οι διαδρομές και ποιος είναι ο μηχανισμός με τον οποίο θα βρεθεί η μικρότερη;

Β) Υπάρχει κάποιος πολύ γνωστός αλγόριθμος με τον οποίο λύνεται αυτό το πρόβλημα;


Το θέμα είναι εδώ: http://osiris.stathis.ch/~stathis/PDP/PDP_20_B.pdf
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
thelastnicholas
Δημοσιεύσεις: 74
Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm

Re: Β Φάση 20ου ΠΔΠ

Δημοσίευση από thelastnicholas »

Υπάρχουν πολύ τρόποι για να λυθεί.

Το πρόβλημα εντάσσεται στην κατηγορία των Shortest Path. Παρόλα αυτά πρόκειται για ειδική περίπτωση αφού ο γράφος είναι μη ζυγισμένος (όλες οι ακμες κοστίζουν το ίδιο δηλαδή) .

Στον πιο απλό (σχετική έννοια, μάλλον πιο βασικό και που λειτουργεί μονο στο συγκεκριμενο είδος προβλήματος) η λογική είναι "περίπου" ίδια με την 2^Ν λύση του θέματος του λυκείου. Δηλαδή βασίζεται στην αναδρομή.

Φυσικά μπορείς να υλοποιήσεις οποιονδήποτε άλλο shortest path αλγόριθμο.

Υ.Γ. Ελπίζω να θυμάμαι το σωστό πρόβλημα :D
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Β Φάση 20ου ΠΔΠ

Δημοσίευση από thetrojan01 »

μάλλον ναι. Ευχαριστώ πολύ...

και άλλες απαντήσεις; οκοκ έψαξα στα αγγλικά το λύμμα που μου έδωσες ;) και βρήκα κάτι που κολλά πάνω στην ενδεικτική λύση: Single-Source Shortest Path in Unweighted Graphs


thanks!
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Β Φάση 20ου ΠΔΠ

Δημοσίευση από userresu »

Αν θυμαμαι καλα το προβλημα, ο αλγοριθμος που ζηταει λεγεται BFS (Breadth First Search) Ψαξτο στη wikipedia και θα το βρεις.
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Β Φάση 20ου ΠΔΠ

Δημοσίευση από thetrojan01 »

ναι ναι, το βρήκα.

και μάλιστα βρήκα και τα εξής:
http://www.algorithmist.com/index.php/Shortest_Path


Merci beaucoup!
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Β Φάση 20ου ΠΔΠ

Δημοσίευση από chris »

Έχει κανείς το ενδεικτικό σε C να το "μελετήσω";
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
georgeha98
Δημοσιεύσεις: 48
Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm

Re: Β Φάση 20ου ΠΔΠ

Δημοσίευση από georgeha98 »

chris μόλις σου το έστειλα στο msn που έχεις την υπογραφή σου.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Β Φάση 20ου ΠΔΠ

Δημοσίευση από chris »

thanx!
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Β Φάση 20ου ΠΔΠ

Δημοσίευση από compileGuy »

Αν θέλει κάποιος μου στέλνει ενδεικτική λύση για το ίδιο πρόβλημα σε c++!!!

Η σε C έστω!! :?
Απάντηση