Uninformed and Informed Search Techniques in Artificial Intelligence

Abstract

In this master thesis the search techniques in Artificial Intelligence are analyzed. The search techniques are grouped into two main categories which are uninformed search techniques and informed search techniques. Such uninformed search techniques as breadth-first search, depth-first search, depth-limited search, iterative deepening search, uniform cost search, and bidirectional search are considered. The best-first search, greedy best-first search, A* search and hill climbing techniques as paradigms of informed search techniques are studied. The completeness, optimality, time complexity, and space complexity properties of all above mentioned search techniques are discussed. The Dijkstra’s algorithm is used to find the shortest paths from the initial node to all other nodes in a weighted digraph.

ÖZ: Bu master tezinde yapay zekanın arama yöntemleri incelenir. Yapay zekada arama yöntemleri sezgisel olmayan ve sezgisel arama yöntemleri olarak iki esas kategoriye ayrılır. Önce genişliğine arama, önce derinliğine arama, derinlik sınırlandırmalı arama, yineli derinleştirmeli arama, düzenli maliyet arama ve çift yönlü arama yöntemleri sezgisel olmayan yöntemler olarak dikkate alınır. En iyi öncelikli arama, açgözlü en iyi öncelikli arama, A* arama ve tepe tırmanma yöntemleri sezgisel arama yöntemlerinin paradigmaları olarak incelenir. Yukarıda adı geçen tüm arama yöntemlerinin tamlık, optimallik, zaman karmaşıklığı ve bellek karmaşıklığı özellikleri tartışılır. Dijkstra algoritması kullanarak ağırlıklı yönlü grafikte başlangıç düğümünden diğer dügümlere gidilebilecek en kısa yol bulunur.