Dərs vəsaiti baki -2018 azərbaycan döVLƏt neft və SƏnaye universiteti

Şək. 4.1. Məmulatların yerləşdirilməsi variantlarını əks etdirən binar ağac
Məmulatların bir ədədinin çəkisi aşağıdakı kimi olsun: soyuducu - 100kq, generator- 75kq, kondisioner- 50kq. Mötərizədə məmulatların sayı göstərilib. S-soyuducunun, G- generatorun, K-kondisionerin şərti işarələridir. Məmulatların çəkisi verilmişsə, hər dəfə müqayisə quran zaman ən azı 2 budaqlanma yerinə yetirilərsə, 3 məhsula görə variantlar qurulanda mümkün variantların sayı 2²=4 olar. Nəzərə alsaq ki, hər dəfə budaqlanma 2 yox, daha artıq ola bilər, onda mümkün variantların sayı daha da çox ola bilər. Əgər n sayda yük olsa, ən azı 2^n-1 variant qurulur. Məsələn, n=101 olsa, 2¹⁰⁰≈10³⁰ variant araşdırılmalıdır.
Saniyədə 1 milyard əməliyyat yerinə yetirən kompüter bu variantları qurmaq üçün nə qədər zaman sərf edər?
10³⁰:10⁹ saniyə = 10²¹ saniyə ≈ 10^{7 ∙} 3170978 il.
Belə hesablamaları yerinə yetirmək praktiki olaraq qeyri-mümkündür. Əgər yükləmə haqqında məsələyə məmulatların bir ədədinin qiymətlərini də daxil etsək və daşınan məmulatların ümumi çəkisinin maksimal olması tələbi ilə yanaşı, həm də bunun maksimal dəyərə malik olması tələbini də irəli sürsək, məsələ daha da qəlizləşər.
7.Kommivoyajer haqqında məsələnin alqoritminin mürəkkəbliyinin qiymətləndirilməsi. Kommivoyajer elə şəxsə deyilir ki, o hansısa bir firmanın (şirkətin, müəssisənin) nümayəndəsi olaraq bu firmanın digər şəhərlərdə yerləşən nümayəndəliklərinin hamısını yoxlamaq üçün minimum xərclə ezamiyyətə gedib geri qayıtmalıdır. Fərz edək, firma 4 nömrəli şəhərdə fəaliyyət göstərir, onun nümayədəlikləri 2,3,4 nömrəli şəhərlərdədir.
Bu halda kommivoyajerin alternativ ezamiyyə marşrutları aşağıdakılar olacaq:
4 – 1 – 2 – 3 – 4 , 4 – 1 – 3 – 2 – 4, 4 – 2 – 1 – 3 – 4,
4 – 2 – 3 – 1 – 4, 4 – 3 – 1 – 2 – 4, 4 – 3 – 2 – 1 – 4.
Deməli, yol variantlarının sayı düsturu ilə qiymətləndirilir. Burada n şəhərlərin ümumi sayını göstərir. n=21 olduqda məsələnin optimal həllini tapmaq üçün tələb olunan vaxtı qiymətləndirək. 20! nəzərə alaraq hesablama aparsaq ≈ 63,42 il vaxt tələb olunar.
Göründüyü kimi, hesablama alqoritminin praktiki olaraq çətinliyi məsələyə aid giriş informasiyasının ölçüsündən asılıdır. Bu ölçünü n parametri ilə işarə edək.
Əgər alqoritmin davamiyyəti n-dən asılı polinomla ifadə olunarsa, bu alqoritmə polinomial alqoritm deyilir. Tutaq ki, hər hansı A alqoritminin mürəkkəbliyini (davamiyyətini) n-dən asılı funksiya kimi ifadə etmək olar. Bu funksiyanı f_A(n) ilə işarə edək. Əgər bu funksiyanın analitik yazılışı məlum olarsa, onda alqoritmin davamiyyəti haqqında mülahizə yürütmək olar.
f _A(n) = eⁿ - bu eksponensial asılılığı ifadə edir,
n^k+pn+q- bu polinomial asılılığı ifadə edir.
Baxılan misallarda 1-ci halda n artdıqca, f eksponensial sürətlə artır, 2-ci halda isə f-in artımı bir qədər aşağı sürətlidir. Əgər funksiyanın analitik yazılışı məlum olmazsa, onda bu naməlum funksiyanın hansısa bir analitik yazılışı məlum olan funksiyaya nisbətinin limitini qiymətləndirməyə çalışırlar.
P_k(n) olaraq n-dən asılı k tərtibli çoxhədli (polinom) daxil edək. Əgər f_A(n) funksiyası P_k(n) çoxhədlisinə nəzərən“O” xassəsinə malik olarsa, onda bu alqoritmə polinomial alqoritm deyilir.
Elmi ədəbiyyatda qeyd olunur ki, əgər verimiş məsələnin determinik Türinq maşını ilə həlli üçün sərf olunan zaman giriş informasiyasından polinomial asılı funksiya ilə ifadə oluna bilərsə, onda bu məsələyə P sinfinə aid olan məsələ deyilir.
Əgər verimiş məsələnin qeyri-deteminik Türinq maşını ilə həlli üçün sərf olunan zaman giriş informasiyasından polinomial asılı funksiya ilə ifadə oluna bilərsə, onda bu məsələyə NP sinfinə aid olan məsələ deyilir. Qeyd edək ki, qeyri-determinik Türinq maşını elə maşına deyilir ki, onun növbəti vəziyyəti əvvəlki vəziyyətindən birqiymətli olaraq asılı deyil. Ona görə də bu maşının işinin nəticəsini həll ağacının qurulması ilə təsvir etmək olar. Maşının işi o zaman nəticə verir ki, hansısa addımda qurulan budaqlardan birinin sonu (yəni ağacın yarpaq tipli düyünlərindən biri) məsələnin məqsəd situasiyasını ifadə etsin.
Yuxarıda baxılan məsələlər NP sinfinə aiddir, çünki budaqlanma zamanı məmulatların sayı təsadüfi olaraq, əvvəldən razılaşdırılmamış qanunauyğunluqla yerinə yetirilmişdir. NP sinfinə aid olan bəzi məsələlər bunlardır:
- kommivoyajer məsələsi,
- bul funksiyaları haqqında məsələ (verilmiş bul düsturu əsasında bu düsturu eyniliklə vahidə çevirən dəyişənlər yığımının varlığının araşdırılması),
- verilmiş qrafın verilmiş ölçülü tam alt qraflarının (kliklərin) tapılması məsələsi,
- verilmiş qrafda hamilton dövrlərinin varlığının araşdırılması məsələsi,
-xətti bərabərsizliklər sisteminin tam həllinin olmasının araşdırılması məsələsi,
- və s.
P sinfi NP sinfinə daxildir. NP sinfinə aid olan hər hansı məsələnin polinomial həllinin tapılmasının mümkünsüzlüyünü iddia etmək əsassızdır. Lakin, ümümiyyətlə, ixtiyari NP-məsələsinin P-həllinin tapılmasının mümkünlüyünü hələ sübut edən olmayıb. Mütəxəssislər NP və P siniflərinin ekvivalent olmaması təklifi ilə daha çox razılaşırlar.
NP sinfinin bir alt çoxluğunu NP-tam məsələlər sinfi təşkil edir. Bunlar elə məsələlərdir ki, hər bir NP-məsələ müəyyən çevirmələrlə bu sinfə aid olan məsələyə gətirilə bilər. Buradan nəticə çıxır ki, əgər NP-tam məsələ üçün P-həlli tapılarsa, onda P-həlli ixtiyari NP-məsələsi üçün də tapıla bilər.
NP-tam sinfinə aid olan bəzi məsələlər bunlardır:
- kommivoyajer məsələsi,
- bul funksiyaları haqqında məsələ (verilmiş bul düsturu əsasında bu düsturu eyniliklə vahidə çevirən dəyişənlər yığımının varlığının araşdırılması),
- verilmiş qrafın verilmiş ölçülü tam alt qraflarının (kliklərin) tapılması məsələsi,
- verilmiş qrafda düyünlərin rənglənməsi haqqında məsələ,
- sürüşkən xanalı kvadrat məsələsi, və s.
NP-tam sinfinin bir alt sinfini güclü mənada NP-tam sinfi təşkil edir ki, bu da aşağıdakı əlamətlərə malikdir:
1. bunlar ədədi parametrli məsələ deyil (yəni bu məsələlərdə rast gəlinən kəmiyyətlərin maksimal qiyməti yuxarıdan giriş informasiyasının həcmindən asılı olan polinomla məhdudlaşıb),
2. bunlar NP sinfinə aiddir,
3. bunlar NP-tam tipli məsələlərdir.