Arama algoritmaları

Arama algoritmaları, bilgisayar biliminde seçili özelliklere göre istenilen bilgileri bulan algoritmalardır. Listeler, metinler ve şekiller üzerinde çalışırlar

Bilgisayar bilimlerinde, çeşitli veri yapılarının (data structures) üzerinde bir bilginin aranması sırasına kullanılan algoritmaların genel ismidir. Örneğin bir dosyada bir kelimenin aranması, bir ağaç yapısında (tree) bir düğümün (node) aranması veya bir dizi (array) üzerinde bir verinin aranması gibi durumlar bu algoritmaların çalışma alanlarına girer.

Yapısal olarak arama algoritmalarını iki grupta toplamak mümkündür.

Uninformed Search (Bilmeden arama)
Informed Search (Bilerek arama)
Arama işleminin bilmeyerek yapılması demek, arama algoritmasının, probleme özgü kolaylıkları barındırmaması demektir. Yani her durumda aynı şekilde çalışan algoritmalara uninformed search (bilmeden arama) ismi verilir. Bu aramaların bazıları şunlardır:

Listeler (diziler (array)) üzerinde çalışan arama algoritmaları:
Doğrusal Arama (Linear Search)
İkili arama (binary search)
Interpolasyon Araması (Ara değer araması, Interpolation Search)
Şekiller (graflar (Graphs) ) üzerinde çalışan algoritmalar
Sabit Maliyetli Arama (Uniform Cost Search)
Floyd Warshall algoritması
Prim’s Algoritması
Kruskal Algoritması
Dijkstra Algoritması
Bellman Ford Algoritması
İkili arama ağacı (Binary Search Tree)
Prüfer dizilimi
Ağaçlarda Sığ öncelikli arama (breadth first search)
Şekillerde (Graph) sığ öncelikli arama (Breadth First Search, BFS)
Derin öncelikli arama (depth first search)
Derin Limitli Arama (Depth Limited Search) Algoritması
Yinelemeli Derinleşen Derin Öncelikli Arama Algoritması (Iterative Deepining Depth First Search, IDDFS)
Patricia Ağaçları
Trie Ağaçları (metin ağaçları, trie trees)
B-ağaçları (B-Tree)
Metin arama algoritmaları (bir yazı içerisinde belirli bir dizgiyi (string) arayan algoritmalar)
Horspool Arama Algoritması
Knuth-Morris Prat arama algoritması
Boyer-Moore Arama algoritması
Kaba Kuvvet Metin Arama Algoritması (Brute Force Text Search, Linear Text Search)
DFA Metin Arama Algoritması
Ters Parça Algoritması (Reverse Factor Algorithm)
Arama işleminin bilerek yapılması ise, algoritmanın probleme ait bazı özellikleri bünyesinde barındırması ve dolayısıyla arama algoritmasının problem bazlı değişiklik göstermesi demektir. Bu algoritmaların bazıları a aşağıda listelenmiştir:

Minimax Ağaçları
Simulated Annealing (Benzetimli Tavlama) algoritması
Tepe Tırmanma Algoritması (Hill Climbing Algorithm)
Arı sürüsü arama algoritması (bees search algorithm)
A* Araması (astar search)
Geri izleme (backtracking)
Işın arama (beam search)

Türleri

İkili arama algoritması

 

Aranılan diziyi ikiye bölecek şekilde bir eleman seçilir. Sağındaki ve solundakilere bakılır. Algoritmanın çalışması için dizinin sıralı olması koşulu bulunmaktadır. Bu şekilde aranan sayı bulunana kadar işlem yapılır. Algoritmanın çalışması örnek üzerinden şu şekilde açıklanmıştır:

[1,2,4,7,9,11,15]

şeklinde bir dizi verilmiş olduğunda, aradığımız sayının da 4 olduğunu kabul ettiğimiz takdirde, dizinin eleman sayısı 7'dir. Bu durumda ortadaki eleman 4. eleman olarak seçilir ve 7 sayısı ile aranan sayı kontrol edilir. 4<7 olduğu için 4. elemanın solundaki sayılara bakılır:

[1,2,4]

şeklinde elde edilen yeni alt dizinin üzerinde algoritma yeniden çalıştırılır. Dizinin eleman sayısı 3'tür ve ortadaki elemanı 2. eleman olarak seçilir. Eleman değeri 2'dir ve aranan değer 4 ile karşılaştırılır. 4>2 olduğu için 2. elemanın sağ tarafında arama devam eder:

[4]

Tek başına aranan elemanın bulunduğu 4 değeri kaldığından dolayı, bu değer ile aranan değer karşılaştırıldığında aranan değere ulaşılmış olur.

Enine arama (Breadth First Search-BFS)

Bütün çizit aramalarında ve özellikle ağaç aramalarında daha sık kullanılır. Başlangıç düğümüne yakın düğümlerin dolaşarak yoluna devam eder. Bir seviye uzaklaşmadan önce, o seviyeye kadar olan bütün düğümleri dolaşmış olması gerekir. Örneğin; ağaç araması sırasında, her satırda soldan sağa olmak üzere sıra ile bulana kadar arama yapar. Aranan düğüme ulaşmadan önce, aranan düğüm ile başlangıç düğümü arasındaki seviyelerde bulunan bütün düğümleri dolaşmak zorunda olması gibi bir dezavantajı vardır. Bu durum, algoritmanın hedefi bulmasını geciktirir. Resimdeki öncelik A-B-C-D-E-F-G-H-I-İ-J

Ayrıca ağaç olmayan bir çizitte de kullanılabilir. Örneğin aşağıdaki şekilde 1'den başlanarak dolaşılması halinde, öncelik 1-2-5-3-4-6 olacaktır.

Derin Öncelikli Arama (Depth First Search-DFS)

Ağaç yapılarında kullanılır. Arama işlemine, Yukarıdan aşağıya sol öncelikli olarak arama yapar. Resimdeki aramada öncelik A-B-C-D-E-F-G-H-I-İ-J şeklindedir.

Enine arama algoritmasında verilen örnek grafın aynısı derin öncelikli olarak aransaydı, muhtemel arama sıralamalarından birisi 1-5-4-6-2-3 olabilirdi

 

 

http://bilgisayarkavramlari.sadievrenseker.com/

https://tr.wikipedia.org/