A Progressive Search Algorithm for the Minimum Hitting Set Problem

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.