background image

στην αντίστοιχη υποπεριοχή του.

Όπως έχουμε ήδη αναϕέρει, οι πίνακες αξιολόγησης E

i

αρχικά περιέχουν πλη-

ροϕορίες απόστασης μεταξύ κάθε χωροpixel και οχήματος. Η βασική ιδέα του αλ-

γορίθμου DARP είναι ότι κάθε πίνακας αξιολόγησης E

i

μπορεί να τροποποιηθεί

κατάλληλα, προκειμένου να εξισωθεί ο αριθμός των χωροpixel k

i

για κάθε όχημα.

Με άλλα λόγια, ο αλγόριθμος DARP επιχειρεί να δημιουργήσει υποπεριοχές ίσου

μεγέθους για κάθε όχημα. Ωστόσο, δεδομένου ότι στην περίπτωσή μας κάθε όχημα

μπορεί να έχει διαϕορετική ταχύτητα κίνησης, απαιτούνται ορισμένες τροποποι-

ήσεις στο συγκεκριμένο τμήμα. Αρχικά, διατηρείται ένας συντελεστής ταχύτητας

W F

i

για κάθε όχημα. Βάσει του συντελεστή ταχύτητας του κάθε οχήματος, προσ-

διορίζεται το ποσοστό της συνολικής περιοχής που θα διατεθεί σε κάθε όχημα. Τα

οχήματα που μπορούν να κινούνται ταχύτερα θα αντιστοιχούν σε μια υψηλότερη

τιμή W F

i

. Για παράδειγμα, εάν το όχημα Α (πράσινο) είναι δύο ϕορές πιο γρήγορα

από το όχημα Β (κόκκινο), στο όχημα Α θα αντιστοιχεί W F = 2 ενώ στο όχημα Β

θα αντιστοιχεί W F = 1. Μετά την ολοκλήρωση της εκτέλεσης του τροποποιημένου

αλγορίθμου DARP, αναμένεται ότι η υποπεριοχή που αντιστοιχεί στο όχημα Α θα

είναι διπλάσια της υποπεριοχής του οχήματος Β. (σχήμα 3.7).

Ο αλγόριθμος DARP έχει ως έξοδο έναν πίνακα του οποίου οι τιμές υποδηλώ-

νουν σε ποιό όχημα έχει ανατεθεί το κάθε χωροpixel. Στο σχήμα 3.6 βλέπουμε τον

διαμοιρασμό της συνολικής περιοχής για το σχήμα 3.4.

3.7

Υπολογισμός Ελαχίστου Γεννητικού Δέντρου

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

είναι απαραίτητο να υπολογιστεί το Ελάχιστο Γεννητικό Δέντρο (ΕΓΔ) για κάθε

υποπεριοχή, ώστε να υπολογιστεί στο επόμενο στάδιο το μονοπάτι κάλυψης της

κάθε υποπεριοχής. Η διαδικασία αυτή ϕέρει μεγάλο υπολογιστικό κόστος. Είναι

απαραίτητο λοιπόν να χρησιμοποιηθεί ένας αποδοτικός και γρήγορος αλγόριθμος.

Οι τρεις κυρίαρχοι [18] αλγόριθμοι που επιλύουν το συγκεκριμένο πρόβλημα είναι:

ο αλγόριθμος του Borůvka, [36] ο αλγόριθμος του Prim [12] και ο αλγόριθμος του

Kruskal [26].

39