En yakın nokta problemleri için projeksiyon tabanlı yaklaşımlar üzerine bir çalışma

Yükleniyor...
Küçük Resim

Tarih

2013

Dergi Başlığı

Dergi ISSN

Cilt Başlığı

Yayıncı

Ege Üniversitesi

Erişim Hakkı

info:eu-repo/semantics/openAccess

Özet

Bu tezde en yakın çift problemi için yeni bir çözüm öneren yakın zamanda sunulmuş QuickCP algoritması (Dalkılıç ve Ergun, 2012) tekdüze, üstel ve normal dağılımlarda incelenmiştir. Veri noktaları çizgisel sıralanma sergilediğinde QuickCP algoritmasının performansı önemli ölçüde düştüğünden, QuickCP algoritmasının rastgeleleştririlmiş QuickCP adında yeni bir sürümü geliştirilmiştir. QuickCP algoritmasının rasgeleleştirme süreci, Gram-Schmidt metoduyla elde edilen ortonormal baz vektörler kullanmaktadır. QuickCP ve rastgeleleştirilmiş QuickCP algoritmaları, noktaların en yakın çiftini bulmak için klasik Böl ve Fethet algoritması ile Kaba Kuvvet algoritmasına karşı çok boyutlu uzaylarda ve farklı dağılımlarda test edilmiştir. QuickCP ve Kaba Kuvvet algoritmalarının çok boyutlu uzaylara genişletilmesi kolay iken, klasik Böl ve Fethet algoritması ile rastgeleleştirilmiş QuickCP algoritmalarının çok boyutlu uzaylara genişletilmesi bu çalışmanın bir parçası olarak geliştirilmiştir. Geniş ölçüde yapılan karşılaştırmalar 2, 3, 4 ve 5 boyutlu öklit uzaylarında rastgeleleştirilmiş QuickCP algoritmasının çizgisel sıralamalı dağılımlar dâhil tüm dağılımlarda rakiplerinden daha iyi performans sergilediğini göstermektedir.

Açıklama

Anahtar Kelimeler

En yakın çift problemi, böl ve fethet, olasılık dağılımı, rastgeleleştirilmiş algoritma, çok boyutlu uzay., Closest pair problem, divide and conquer, probability distribution, randomized algorithm, multidimension space., Uluslararası Bilgisayar A.B.D.

Kaynak

WoS Q Değeri

Scopus Q Değeri

Cilt

Sayı

Künye