Performance evaluation of heuristic search algorithms

Abstract

ÖZET. » HEURISTIK TARAMA ALGORİTMALARININ PERFORMANS DEGERLENDIRILMSI AL-AYYOUB» Abdel-Elah Yüksek. Lisans Tezi» Bilgisayar Bölümü' Tez Yöneticisi* Doç. E«r» Müren Gökeri ARALIK» 1987, 162 sayfa Bir çok yapay zeka problemi bazı alternatiflerden yola çıkarak çözüm arayışa içerisindedir» ve bunlar heuristik'ten yararlanarak taramaya kılavuzluk edip» elde edilen çözümle rin verimli olmasını sallamaktadırlar* Yapay zeka sistemle rinin performansları önemli ölçüde tarama hızlarına» âerekli belleâe ve problemin özellisine baâlıdır» Bu tez» tarama problemleri ve heuristik tarama algoritmalarının performansı üzerinde yapılan deneysel araştırmaları anlatmaktadır» Tarama algoritmalarını test etmek için sienel bir model bazı programların yardımıyla sunulacaktır* Heuristik araştırma algoritmalarını performanslarını karşılaştıran teknik tanıtılıp» algoritmalar «truplar halinde toplanacaktır (bazı koşullara baâlı kalarak daha sonra açık lanacaktır)» Bir sfrup algoritmalar için bir 'performans tab losu` tutmak yeterli olacaktır» Bu problem-baâımsız tablo kullanılarak» verilen herhansii bir problem ortamında» bir algoritmanın diierinden daha verimli olmasını nicel olarak deleri eridir i lebi liriz» Anahtar kelimeleri» Heuristik araştırma» zaman-karmaşıklıâı » Performans VII

ABSTRACT PERFORMANCE EVALUATION OF HEURISTIC SEARCH ALGORITHMS AL-AYYOUB» Abdel-Elah M.S» Thesis in Computer Engineering Supervisor» Assoc» Prof» Dr. Müren Gökeri December» 1987» 164 pages Man» Artificial Intelligence problems deal in searching for solutions from many alternatives» and depend upon heuri stics to guide the search and to ensure efficiently* obtained results» The performance of any Artificial Intelligence system often critically depends on the speed of the search» memory space reouired for the search and nature of the solution» This thesis documents an empirical research done on search problems and performances of heuristic search algorithms» A general model is presented that defines methods designed to test the performance of search algorithms using a set of computer program» A technique of comparing the performance of heuristic search algorithms is introduced as a way of treating the algorithms in gruops (according to some criterion will be mentioned later) and a single so called 'Performance Table` is enough for algorithms in one group» Using this domain independent table we can make Qualitative statements about when one algorithm is more efficient than another in any given problem domain» Key words* Heuristic search» Time-complexity» performance. VI