Yazan : Şadi Evren ŞEKER
Literatürde tam arama veya etraflı arama olarak geçmektedir. İngilizcede “exhaustive search” terimi kullanılır. Genel olarak, arama algoritmalarının performansını arttırmak için kullanılan bir yöntemdir.
Bir arama algoritmasının tam arama (exhaustive search) olabilmesi için aşağıdaki şartları sağlaması gerekir:
-
Bir değerin bulunmadığını söylemeden önce bütün değerlere bakmış veya bütün ihtimalleri değerlendirmiş olmalıdır.
-
Arama uzayında hareket edilirken (Arama işlemi sırasında) sistematik bir yöntem kullanılmalıdır. Diğer bir deyişle arana değerlere tekrar tekrar bakılmamalı, ve her adımdan sonra hangi değere bakılacağı belirlenmelidir.
Yukarıdaki şartları sağlayan arama algoritmalarına etraflı arama veya tam arama ismi verilir. Ancak yukarıdaki ikinci maddenin bir istisnası bulunur. Bazı durumlarda arama algoritmasını hızlandırmak için rast gele bir değer ataması (randomness) kullanılabilir. Bu durum bir çelişki olarak görülmemelidir. Algoritmanın içerisinde bir rastgelelik bulunsa bile, aranan değerleri tekrar aramaması ve üretilecek olan rastgeleliğin tam kontrol altında tutulması halinde, arama algoritması etraflı arama olarak sınıflandırılabilir.
Etraflı arama algoritmalarını aynı zamanda birer geri izleme algoritması (back tracking algorithm) olarak isimlendirmek mümkündür. Aslında bütün etraflı arama algoritmaları (Exhaustive search algorithms) birer geri izleme algoritmasıdır (back tracking algorithm). Ancak bu cümlenin tersi doğru değildir. Yani bütün geri izleme algoritmalarının etraflı arama algoritması olduğunu söyleyemeyiz. Buradaki fark, etraflı arama algoritmalarının, arama işlemi sırasında aranacak olan değerlerin bir kısmını budamasından kaynaklanır (prunning). Yani bazı değerlerin bakılmasına gerek kalmayacak şekilde arama işlemini hızlandırırlar.
Bu anlamda doğrusal arama (linear search), kaba kuvvet araması (brute force algorithm) gibi temel arama algoritmaları birer etraflı arama kabul edilebilir.