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.
255 views