Εύρεση τέλειας συνάρτησης κατακερματισμού με τη χρήση στοχαστικού αλγόριθμου (καταργήθηκε 2007)
Η στατική δομή αναζήτησης είναι ένας αφηρημένος τύπος δεδομένων
ο οποίος επιτρέπει την εισαγωγή και την αναζήτηση στοιχείων.
Όλες οι εισαγωγές γίνονται πριν από τις αναζητήσεις με αποτέλεσμα
να είναι δυνατός ο υπολογισμός μιας στατικής δομής που να επιτρέπει
τη γρήγορη εύρεση στοιχείων.
Μια τέτοια δομή μπορεί να βασίζεται σε συνάρτηση κατακερματισμού.
Για παράδειγμα,
το πρόγραμμα gperf υπολογίζει βέλτιστες τέτοιες συναρτήσεις
για χρήση στο τμήμα της λεκτικής ανάλυσης μεταγλωττιστών.
Η πληθώρα των δυνατών συναρτήσεων κατακερματισμού και ο εύκολος τρόπος
αξιολόγησής τους επιτρέπουν τη χρήση γενετικών αλγορίθμων για την
"εξέλιξη" μιας βέλτιστης συνάρτησης από έναν πληθυσμό δυνατών συναρτήσεων.
Η εργασία περιλαμβάνει τη χρήση γενετικών αλγορίθμων για τον υπολογισμό
βέλτιστων συναρτήσεων κατακερματισμού.
Η δυναμική αποτίμηση της συνάρτησης μπορεί να οδηγήσει σε αποδοτικό
αλγόριθμο αναζήτησης.
Βιβλιογραφία
David E. Goldberg.
Genetic Algorithms: In Search of Optimization & Machine Learning.
Addison-Wesley, 1989.
Schmidt, Douglas C. GPERF: A Perfect Hash Function Generator
Second USENIX C++ Conference Proceedings, April 1990.
Donald E. Knuth.
The Art of Computer Programming, volume 3 / Searching
and Sorting.
Addison-Wesley, second edition, 1973.
Andrew Hume.
Grep wars: The strategic search initiative.
In Proceedings of the EUUG Spring 88 Conference, pages 237-245.
European UNIX User Group, 1988.