Περίληψη:
Ένα από τα πιο κλασσικά καθημερινά προβλήματα, είναι το πρόβλημα του περιπλανώμενου πωλητή, το οποίο ορίζεται ως η βέλτιστη διαδρομή από θέμα κόστους που θα πρέπει να ακολουθήσει κάποιος, ώστε να περάσει από όλα τα προκαθορισμένα σημεία και να επιστρέψει στην αφετηρία με το λιγότερο δυνατό κόστος. Η έννοια του κόστους θα αναλυθεί παρακάτω. Στη παρούσα πτυχιακή εργασία κάνουμε μια εισαγωγή στη θεωρία των Heuristic αλγορίθμων οι οποίοι βρίσκουν εφαρμογή σε πολλά απλά καθημερινά προβλήματα. Η έννοια του Heuristic έγκειται στο γεγονός, ότι θα πρέπει να χαλαρώσουμε τους περιορισμούς μας και να υπολογίσουμε μόνο τις περιπτώσεις όπου θα μας δώσουν μια ικανοποιητική λύση. Η λύση δεν θα είναι ενδεχομένως η καλύτερη δυνατή, αλλά θα είναι κοντά στην βέλτιστη με αμελητέα σχεδόν απόκλιση.
Το πρόβλημα του περιπλανώμενου πωλητή είναι από τα πλέον γνωστά. Σύμφωνα με αυτό ζητάμε ποια είναι η ελάχιστη διαδρομή που θα πρέπει να ακολουθήσουμε ώστε ξεκινώντας από τη πόλη-αφετηρία (αρχικός κόμβος), να περάσουμε μια φορά από όλες τις πόλεις (όλους τους κόμβους του δικτύου) και όλα αυτά με το ελάχιστο κόστος. Η υλοποίηση του αλγορίθμου έγινε στη γλώσσα C.
Τέλος σε προβλήματα βελτιστοποίησης και συγκεκριμένα σε προβλήματα ανάθεσης εργασιών με το ελάχιστο δυνατό κόστος, βρίσκει εφαρμογή ο αλγόριθμος Branch and Bound. Και στα δύο προβλήματα οι αλγόριθμοι που θα χρησιμοποιήσουμε είναι ευρετικοί και χαλαρώνουν κάποιες συνθήκες, ώστε να έχουμε από άποψη χρόνου γρήγορα αποτελέσματα, ακόμα και για μεγάλο αριθμό εισόδων με λύσεις που είναι πολύ κοντά στη βέλτιστη. Η υλοποίηση του αλγορίθμου έγινε στη γλώσσα C.