Arama algoritması

Vikipedi, özgür ansiklopedi
(Arama algoritmaları sayfasından yönlendirildi)

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

Türleri[değiştir | kaynağı değiştir]

İkili arama algoritması[değiştir | kaynağı değiştir]

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 (Sığ öncelikli arama)[değiştir | kaynağı değiştir]

Bütün çizge aramalarında ve özellikle ağaç aramalarında daha sık kullanılır. Başlangıç düğümüne yakın düğümleri 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 şeklindedir.

Öncelik sırası A-B-C-D-E-F-G-H-I-İ-J
Öncelik sırası A-B-C-D-E-F-G-H-I-İ-J

Ayrıca ağaç olmayan bir çizgede 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.

Öncelik sırası 1-2-5-3-4-6
Öncelik sırası 1-2-5-3-4-6

Derin Öncelikli Arama (Depth First Search-DFS)[değiştir | kaynağı değiştir]

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.

Öncelik sırası A-B-C-D-E-F-G-H-I-İ-J
Öncelik sırası A-B-C-D-E-F-G-H-I-İ-J

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

Öncelik sırası 1-5-4-6-2-3
Öncelik sırası 1-5-4-6-2-3

Ayrıca bakınız[değiştir | kaynağı değiştir]

Dış bağlantılar[değiştir | kaynağı değiştir]