Β Φάση 20ου ΠΔΠ

[thetrojan01]

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

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

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

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


Το θέμα είναι εδώ: http://osiris.stathis.ch/~stathis/PDP/PDP_20_B.pdf

[thelastnicholas]

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

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

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

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

Υ.Γ. Ελπίζω να θυμάμαι το σωστό πρόβλημα

[thetrojan01]

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

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


thanks!

[userresu]

Αν θυμαμαι καλα το προβλημα, ο αλγοριθμος που ζηταει λεγεται BFS (Breadth First Search) Ψαξτο στη wikipedia και θα το βρεις.

[thetrojan01]

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

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


Merci beaucoup!

[chris]

Έχει κανείς το ενδεικτικό σε C να το "μελετήσω";

[georgeha98]

chris μόλις σου το έστειλα στο msn που έχεις την υπογραφή σου.

[chris]

thanx!

[compileGuy]

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

Η σε C έστω!!