Κεφάλαιο 3

Υλοποίηση του λογισμικού μέρους

Στο κεϕάλαιο αυτό παρουσιάζεται το λογισμικό που αναπτύχθηκε και τα στάδια

που περιλαμβάνει. Επιπλέον, δίνονται και ερμηνεύονται οι αλγόριθμοι που χρησι-

μοποιήθηκαν.

3.1

Γενική επισκόπηση του λογισμικού

Ο προτεινόμενος αλγόριθμος αποτελείται από τέσεσρα κύρια στάδια (σχήμα

3.1). Το πρώτο στάδιο ασχολείται με την αρχικοποίηση του αλγορίθμου. Η είσοδος

του αλγορίθμου περιλαμβάνει: το μέγεθος και την μορϕολογία του περιβάλλοντος,

τις θέσεις στις οποίες βρίσκονται εμπόδια καθώς και τις προδιαγραϕές των οχη-

μάτων (όπως τύπος, ταχύτητα και αρχικές θέσεις). Αυτά τα δεδομένα μπορούν να

διαβαστούν απευθείας από ένα αρχείο κειμένου (text file). Ο αλγόριθμος αποθη-

κεύει στη συνέχεια όλα τα δεδομένα στη μνήμη για ταχύτερη πρόσβαση κατά την

εκτέλεση. Το δεύτερο στάδιο ασχολείται με την εύρεση συνδεδεμένων περιοχών.

Αρχικά, εντοπίζονται (αν υπάρχουν) οι περιοχές που δεν είναι προσβάσιμες από

το έδαϕος. Έπειτα, ο αλγόριθμος βρίσκει την βέλτιστη διαδρομή που ενώνει τις

συγκεκριμένες περιοχές. Στην περίπτωση που το περιβάλλον εισόδου αποτελείται

απο δισδιάστατο χώρο, το βήμα αυτό παραλείπεται. Στο τρίτο στάδιο, η συνολική

περιοχή χωρίζεται σε πολλαπλές υποπεριοχές, μια για κάθε όχημα. Αυτό το στά-

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

με την εκχώρηση περιοχής στα οχήματα. Στην περίπτωση ενός μόνο οχήματος, ο

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

περαιτέρω υπολογισμούς. Στο τέταρτο και τελευταίο στάδιο, για κάθε υποπεριοχή,

υπολογίζεται η διαδρομή κάλυψης. Η έξοδος του αλγορίθμου περιλαμβάνει ένα αρ-

28