Sırt çantası sorunu doğrusal programlama'daki sorunlara benzese de, sırt çantası sorunu neden doğrusal programlama algoritmaları kategorisinin altında yer almıyor.Neden Sırt Çantası problemini çözüyoruz? doğrusal programlama olarak kabul edilmez?
Sırt çantası tamsayı doğrusal programlama program olarak yazılabilir. Normal doğrusal programlamadan farklı olarak, bu problem, çözümdeki değişkenlerin tamsayı olmasını gerektirir. Tamsayılı doğrusal programlama NP-tamamlanırken, doğrusal programlamanın polinom zamanında çözülebilir olduğu bilinmektedir.
Okuyucu için alıştırma: 3SAT'nin tamsayı doğrusal programlamaya indirgenebileceğini gösterin.
Diğer bilgiler: MAX-3SAT (3SAT'nin varyantı olan memnun sayılar sayısını en üst düzeye çıkarmak istediğimiz) gibi sorunlar için yaklaşık algoritmalar vardır. Öncelikle MAX-3SAT'yi bir tamsayı doğrusal program olarak yazarsınız. Ardından, 'u lineer programa, tamsayı kısıtlamasını kaldırarak gevşetin. Ardından, doğrusal programı polinom zamanında çözersiniz. Son olarak, gerçek x verilen i ∈ [0,1], tamsayı bunları yuvarlak ya da rastgele tam sayı çözüm üretmek y i y i = 1 olasılığı x i olduğu.
Tamamlayıcı olarak: http://stackoverflow.com/q/3128001/395857 –
Genel olarak, verilen NP problemini ILP'ye indirgemek genellikle nispeten kolaydır. –
@ yes123 Doğrusal programlamada, doğrusal değil, zaman kısıtlamalarıdır. – fgb