A New Approach to 0/1 Knapsack Problem with Greedy and Heuristic Searches in Integer Programming

Tam Sayı Programlamada Açgözlü ve Sezgisel Aramalar ile 0/1 Sırt Çantası Problemine Yeni Bir Bakış

Abstract

Tam sayılı programlama, bir çeşit optimize edilmiş Lineer Programlama LP olarak adlandırılan doğrusal programlama yöntemidir. Amaç doğrusal programlamada meydana gelebilecek gerçekçi olmayan sonuçları ortadan kaldırmaktır. LP birçok mühendislik alanına uygulanmaktadır. Bu çalışmada, LP yöntemine sezgisel bir yaklaşım eklenerek çok bilinen ve birçok mühendislik probleminin kaynağı olan sırt çantası problemine uygulanmıştır. Yapılan deneysel uygulamalarda önerilen yöntemin özyinelemeli, kesmeli ve optimize edilmiş yöntemlere göre daha az hesaplana zamanı içerisinde sonuç verdiği gözlemlenmiştir.

Özet

Tam sayılı programlama, bir çeşit optimize edilmiş Lineer Programlama olarak adlandırılan doğrusal programlama yöntemidir. Amaç doğrusal programlamada meydana gelebilecek gerçekçi olmayan sonuçları ortadan kaldırmaktır. Tam sayılı Programlama birçok mühendislik alanına uygulanmaktadır. Bu çalışmada, Tam sayılı Programlama yöntemine sezgisel ve açgözlü bir yaklaşım eklenerek çok bilinen ve birçok mühendislik uygulamasının kaynağı olan “sırt çantası” problemine uygulanmıştır. Ayrıca Yığın veri yapısı kullanılarak alan karmaşıklığı en aza indirilmiş ve daha hızlı sonuçlara ulaşılmıştır. Yapılan deneysel uygulamalarda önerilen yöntemin özyinelemeli, kesmeli ve optimize edilmiş yöntemlere göre daha az hesaplama zamanı içerisinde sonuç verdiği gözlemlenmiştir