A Progressive Search Algorithm for the Minimum Hitting Set Problem

Authors : Hilal ARSLAN, Onur UĞURLU, Vahid KHALİLPOUR AKRAM, Deniz TÜRSEL ELİİYİ

Pages : 867-874

Doi:10.21205/deufmd.2021236914

View : 101 | Download : 6

Publication Date : 2021-09-15

Article Type : Research Paper

Abstract :Sonlu bir evren ve evrenin alt kümelerinin bir birleşimi verildiğinde, birleşimin minimum isabet kümesi, birleşimdeki her kümeyle boş olmayan kesişimi olan evrenin en küçük alt kümesidir. Minimum isabet kümesini bulma, birçok gerçek dünya uygulaması olan bir NP-Hard problemidir. Bu çalışmada, verilen bir birleşimin minimum isabet kümesini bulmak için aşamalı arama tabanlı bir yaklaşım öneriyoruz. Algoritma, boyutu 1 olan isabet kümelerini aramayla başlar ve minimum isabet kümesinin beklenen boyutunu d faktörü kadar artırır. Her başarısız aramadan sonra, algoritma beklenen boyutu d kadar artırır ve beklenen boyuta sahip aday kümeleri oluşturur. Her başarılı aramadan sonra, algoritma son başarısız ve başarılı aramaların ortalamasını alır ve yeni beklenen boyutla aramaya devam eder. Algılanan üst sınır, algılanan alt sınırla çakıştığı zaman algoritma sona erer. d faktörünün farklı değerlerinin algoritmanın performansı üzerindeki etkisi çeşitli veri kümeleri üzerinde denenmiştir. Deneysel sonuçlar, önerilen yöntemin gerçek dünya verileri ve rasgele veriler üzerindeki minimum isabet kümesini etkili bir şekilde hesapladığını ortaya koymaktadır.
Keywords : Minimum İsabet Kümesi, NP Hard Problemler, Aşamalı Arama

ORIGINAL ARTICLE URL