yazan: Şadi Evren ŞEKER

Algoritma teorisinde meşhur problemlerden birisidir. NP-Complete problemlere iyi bir örnektir. Problemin tanımı aşağıdaki şekildedir:

verilen eksi ve artı tam sayılar kümesinin herhangi bir alt kümesinin toplamının 0 olduğunu bulmak.

Bu problemin kontrol edilmesi oldukça basittir ancak verilen sayı kümesinden yukarıdaki tanımı sağlayan bir alt küme bulmak kolay değildir.

Problemin örnek çözümü:

verilen sayı kümesi : { 1,4,-5,2,7,-4,2,9} olsun. Bu sayı kümesinin öyle bir alt kümesi var mıdır ki toplamı 0 olsun?

evet böyle bir alt küme buluna bilir örnek:
{-4,4} veya {-4,2,2} veya {1,4,-5} veya {9,-4,-5} … gibi

yukarıdaki örnek için bütün çözümleri verecek bir yöntemin geliştirilmesi mümkün olsa bile bu yöntemin çalışmas süresi problem kümesi büyüdükçe çok çok yüksek değerlere çıkacaktır.

daha fazla bilgi için.
NP-Complete
NP-Hard
tanımlarına bakabilirsiniz.

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


− 3 = iki