Bandpass probleminin analizi ve çözüm algoritmaları

Bandpass Problemi telekomünikasyon sektöründe, “farklı dalga boylarını bölme ve çoklama” teknolojisi kullanan bir optik iletişim ağında, uygulanabilir en yüksek maliyet indirimini sağlamak için, tek bir kabloda hareket eden farklı dalga boylarındaki bilgi akışının en uygun biçimde paketlenmesini araştıran bir optimizasyon problemidir. Problemin matematiksel modeli için, elemanları {0,1} olan bir A matrisi, herhangi bir sütunda ardışık ve sıfır olmayan elamanların oluşturduğu “Bandpass” olarak isimlendirilen bir küme ve bu kümenin sabit olarak belirlenmiş eleman sayısına karşılık gelen “Bandpass Sayısı” olarak isimlendirilen pozitif bir B tamsayısı verilsin. Problemin amacı, herhangi iki Bandpass kümesinin ortak elemanı olmaması şartı altında, B eleman sayısına sahip Bandpass kümelerinin sayısının en çok olmasını sağlayan bir satır sıralaması bulmaktır. Bu çalışmada, Bandpass Probleminin süresel karmaşıklık analizi yapılmış, problemin NPtam sınıftan olduğu ispatlanmıştır. Problemin özel örnekleri geliştirilmiş, bu örneklerin paylaşıldığı internet kütüphanesi hazırlanmıştır. Problemin çözümü için heuristic bir algoritma geliştirilmiş, örnekler üzerinde yapılan hesaplama denemelerinde elde edilen sonuçlar bilinen en iyi sonuçlarla karşılaştırılmıştır. Öte yandan, Bandpass Problemi’nden esinlenerek DesteCi isminde bir bilgisayar oyunu tasarlanmıştır