P და NP, ალგორითმის არჩევა

ზოგ ამოცანას ცნობილი სწრაფი ალგორითმი არ აქვს და მისი დროულად ამოცნობა დღეებს გიზოგავს, რომლებსაც სავარაუდოდ არარსებული ამოხსნის ძებნაში დახარჯავდი. ეს გაკვეთილი გზამკვლევს ასრულებს და ინსტრუმენტის არჩევის სახელმძღვანელოს გაძლევს.

მოწინავე⏱ 15 წთ

←ეყრდნობა

10ბიტმასკური დპბიტმასკური დპ კომივოიაჟერს O(2ⁿ·n²)-ში ხსნის: n!-ზე უკეთესია, მაგრამ მაინც ექსპონენციალურია, და ასე გამოიყურება NP-რთული.100-1 ზურგჩანთის ამოცანა0-1 ზურგჩანთა NP-რთულია; მისი O(n·W) ცხრილი სწრაფია მხოლოდ მანამ, სანამ W პატარაა.8მინიმალური დამფარავი ხე: კრასკალი და პრიმიმინიმალური დამფარავი ხე მეტრიკულ კომივოიაჟერს ოპტიმუმზე მაქსიმუმ ორჯერ გრძელ მარშრუტს აძლევს: სირთულესთან გამკლავების კლასიკური გზა.

გზას უხსნის→

აქ გზამკვლევი სრულდება. გადახედე, რა გზა გაიარე.

1ისწავლე 2ითამაშე 3შეამოწმე 4ივარჯიშე

ისწავლე

იდეა, მექანიზმი და ფასი.

01პოლინომიალური და ექსპონენციალური

ამ გზამკვლევის ყველა ალგორითმი აქამდე, ორობითი ძებნიდან დეიქსტრამდე და უსქ-მდე, პოლინომიალურ დროში მუშაობს: O(n), O(n log n), O(n²), O(n³). n-ის გაორმაგება შრომას მუდმივზე ამრავლებს (2, 4, 8).

არჩევანების სრული გადარჩევა სხვაა. ყველა ქვესიმრავლის ცდა 2ⁿ ჯდება, ყველა დალაგების n!. აქ ერთი ელემენტის დამატება შრომას აორმაგებს (ან უარესი). ლოგარითმულ სკალაზე პოლინომები თითქმის ბრტყელია, 2ⁿ და n! კი წამში 10⁸ ოპერაციის ხაზს n ≈ 27-სა და n ≈ 12-ზე კვეთს.

სწრაფი კომპიუტერი არ გიშველის: 1000-ჯერ სწრაფი მანქანა 2ⁿ ალგორითმს მხოლოდ დაახლოებით 10 დამატებითი ელემენტის დამუშავების საშუალებას აძლევს. ამიტომ კომპიუტერულ მეცნიერებაში „პოლინომიალური“ ეფექტურის სამუშაო განმარტებაა.

02P და NP: პოვნა და შემოწმება

ვისაუბროთ კი/არა კითხვებზე. P არის კლასი, რომელსაც პოლინომიალურ დროში *ვხსნით*: არსებობს გზა s-დან t-მდე? შეიძლება ამ მასივის k გაცვლით დალაგება?

NP არის კლასი, სადაც პასუხს „კი“ ახლავს სერტიფიკატი, რომლის *შემოწმებაც* პოლინომიალურ დროში შეგვიძლია. ქვესიმრავლის ჯამი: „აქვს ამ რიცხვებს ქვესიმრავლე, რომლის ჯამია 9?“ პოვნას შეიძლება 2ⁿ ცდა დასჭირდეს, მაგრამ თუ ვინმე {4, 5}-ს მოგცემს, ორ რიცხვს შეკრებ და მორჩა. სუდოკუს შევსება ძნელია, შემოწმება კი ტრივიალური.

P-ს ყოველი ამოცანა NP-შიც შედის: თუ ამოხსნა შეგიძლია, შემოწმებაც შეგიძლია. ცნობილი ღია კითხვაა, P = NP თუ არა, ანუ ნიშნავს თუ არა ადვილი შემოწმება ყოველთვის ადვილ პოვნას. ვერავინ დაამტკიცა ვერც ერთი, ვერც მეორე. მკვლევართა უმეტესობას სჯერა, რომ P ≠ NP, დამტკიცებას კი მილიონდოლარიანი პრემია ელის.

03NP-სრული ამოცანები და დაყვანა

დაყვანა A ამოცანის ყოველ ეგზემპლარს B ამოცანის ეგზემპლარად თარგმნის, პოლინომიალურ დროში, ისე რომ პასუხები ემთხვეოდეს. მაშინ B-ს სწრაფი ამომხსნელი A-სთვისაც სწრაფ ამომხსნელს მოგვცემდა. სხვა სიტყვებით, B სულ მცირე ისეთივე რთულია, როგორც A.

ამოცანა NP-სრულია, თუ ის NP-შია და ყოველი NP ამოცანა მასზე დაიყვანება. ესენი NP-ის ყველაზე რთული ამოცანებია და ერთად დგანან ან ერთად ეცემიან: ერთისთვის პოლინომიალური ალგორითმი ყველასთვის მოგვცემდა. ათასობით ასეთია ცნობილი, მაგალითად:

SAT: შეიძლება ეს ლოგიკური პირობები ერთდროულად ჭეშმარიტი იყოს?
კომივოიაჟერის ამოცანა (გადაწყვეტის ვერსია): არსებობს მარშრუტი სიგრძით ≤ L?
ქვესიმრავლის ჯამი და მისი ნათესავი, 0/1 ზურგჩანთა
გრაფის შეღებვა 3 ფერით, ჰამილტონის გზა, კლიკა

იმის საჩვენებლად, რომ შენი ამოცანა რთულია, ცნობილი NP-სრული ამოცანა დაიყვანე შენსაზე და არა პირიქით.

04რთული არ ნიშნავს უიმედოს

NP-სრული აღწერს უარეს შემთხვევას დიდი n-ისთვის. შენი რეალური მონაცემები შეიძლება უფრო კეთილგანწყობილი იყოს. შეამოწმე, დაახლოებით ამ რიგით:

პატარაა n? n ≤ 10: სცადე ყველა გადანაცვლება. n ≤ 20: ქვესიმრავლეები, ბიტმასკური დპ (კომივოიაჟერი O(2ⁿ·n²)-ში), უკუსვლა მოკვეთით. n ≤ 40: შუაში შეხვედრა, ორი ნახევარი 2^(n/2)-ით
პატარაა რიცხვები? ზურგჩანთა და ქვესიმრავლის ჯამი O(n · W)-ში იხსნება დპ ცხრილით. ეს *ფსევდოპოლინომიალურია*: სწრაფია, როცა W პატარაა, და არა როცა W = 10^18
განსაკუთრებულია სტრუქტურა? შეღებვა ადვილია ხეებსა და ორწილა გრაფებზე; ბევრი რთული გრაფული ამოცანა ხეზე დპ ხდება
საკმარისია „საკმაოდ კარგი“? მიახლოებით ალგორითმებს გარანტია აქვთ: ჩვეულებრივი მანძილების მქონე კომივოიაჟერისთვის MST-დან აგებული მარშრუტი ოპტიმუმზე მაქსიმუმ ორჯერ გრძელია. ევრისტიკები (ხარბი, ლოკალური ძებნა, SAT ამომხსნელები) პრაქტიკაში ხშირად შესანიშნავად მუშაობს, უბრალოდ დამტკიცების გარეშე

05რომელი ალგორითმი როდის: მთელი გზამკვლევი ერთ გვერდზე

ოლიმპიადის შემმოწმებელი ან რეალური სისტემის ბიუჯეტი წამში დაახლოებით 10⁸ მარტივ ოპერაციას გაძლევს. ამიტომ ჯერ შეზღუდვები წაიკითხე. ისინი გეუბნება, რა სირთულეს ელის ამოცანა, სირთულე კი ინსტრუმენტზე მიგითითებს.

შემდეგ ამოცანის ფორმა შეადარე:

უმოკლესი გზა უწონო გრაფში → BFS; წონები ≥ 0 → დეიქსტრა; უარყოფითი წიბოები → ბელმან-ფორდი; ყველა წყვილი, პატარა n → ფლოიდი
„მინიმუმი / რაოდენობა / საუკეთესო არჩევანებზე“ გადამფარავი ქვეამოცანებით → დპ; დამტკიცებულად უსაფრთხო ლოკალური არჩევანი → ხარბი
„არის პასუხი ≥ x?“ და პასუხი მონოტონურია → ორობითი ძებნა პასუხზე
ბევრი შუალედის მოთხოვნა → პრეფიქსული ჯამები ან სეგმენტების ხე; ბმულობა გაერთიანებებით → DSU
შაბლონი ტექსტში → KMP / Z / ჰეშირება; უზარმაზარი ხარისხები ან რაოდენობები → სწრაფი ახარისხება mod p

თუ არცერთი პოლინომიალური არ ერგება და n პაწაწინაა, ამოცანა შესაძლოა NP-რთული იყოს, და ახლა უკვე იცი, რა უნდა ქნა.

წაიკითხე შეზღუდვა, აირჩიე სირთულე, შემდეგ ინსტრუმენტი. ზღვრები ითვალისწინებს წამში დაახლოებით 10⁸ მარტივ ოპერაციას.

ფასი ერთი შეხედვით

ქვესიმრავლის ჯამი: სრული გადარჩევაO(2ⁿ·n)

ქვესიმრავლის ჯამი: სერტიფიკატის შემოწმებაO(n)

ქვესიმრავლის ჯამი: შუაში შეხვედრაO(2^(n/2)·n)

ქვესიმრავლის ჯამი: დპ ჯამებზე (ფსევდოპოლ.)O(n·W)

კომივოიაჟერი: ბიტმასკური დპO(2ⁿ·n²)

დაიმახსოვრე

NP ამოცანები სერტიფიკატით ადვილად მოწმდება; NP-სრული მათ შორის ყველაზე რთულია და მათთვის პოლინომიალური ალგორითმი ცნობილი არ არის.
ასეთთან შეხვედრისას გამოიყენე პატარა n (ბიტმასკური დპ, უკუსვლა, შუაში შეხვედრა), პატარა რიცხვები (ფსევდოპოლინომიალური დპ), განსაკუთრებული სტრუქტურა, მიახლოება ან ევრისტიკა.
ყოველთვის ჯერ შეზღუდვები წაიკითხე: ისინი ამჟღავნებს, რა სირთულეს ელის ამოცანა, და ეს სწორ ალგორითმზე მიგითითებს.

ითამაშე

გაიარე ალგორითმი ბიჯ-ბიჯ, მერე სცადე შენს მონაცემებზე.

👀 რას უყურო: შეადარე ორი მთვლელი: ძებნა 2ⁿ-ვე კვადრატს ავსებს, სერტიფიკატის შემოწმება კი რამდენიმე რიცხვს კრებს. შემდეგ უყურე, როგორ ფეთქდება დროის სვეტი n-ის ზრდასთან ერთად.

ინტერაქტიული ვიზუალიზატორიაქ დააწკაპე, მერე space ← →

სიმრავლე, მიზანი = 9

33441252

ყველა 64 ქვესიმრავლე (2^6) · შემოწმებული: 0 / 64

ამონახსნიახლა მოწმდებაშემოწმებულიჯერ არა

ქვესიმრავლის ჯამი: აქვს თუ არა {3, 34, 4, 12, 5, 2}-ს ქვესიმრავლე, რომლის ჯამია 9? n = 6 რიცხვს აქვს 2^6 = 64 ქვესიმრავლე. ქვემოთ ყოველი კვადრატი ერთი ქვესიმრავლეა (ერთი ბიტმასკა).

ფსევდოკოდი

 1 // FIND: is there a subset with sum = target? 2 for mask in 0 .. 2^n - 1:              // 2^n candidates 3   if sum(subset(mask)) == target: found 4 // CHECK: someone hands you a subset (certificate) 5 s = 0; for x in certificate: s += x 6 return s == target                     // O(n) 7 // every extra element doubles the search

1 / 1

შეამოწმე

სამი კითხვა. აირჩიე პასუხი და ნახე ახსნა.

№1

n ≤ 18 მუშა n სამუშაოზე უნდა გადანაწილდეს მინიმალური ჯამური ღირებულებით (ნებისმიერი ღირებულების მატრიცა). რა ერგება საუკეთესოდ?

№2

NP-ის შესახებ რომელი დებულებაა სწორი?

№3

იპოვე პოლინომიალური დაყვანა SAT-იდან (NP-სრული) შენს X ამოცანაზე. რას გეუბნება ეს?

ივარჯიშე

რეალური ამოცანები გასამყარებლად, მარტივიდან რთულისკენ.

CSESApple Division დამწყები↗LeetCodePartition Equal Subset Sum საშუალო↗CSESChessboard and Queens საშუალო↗LeetCodeShortest Path Visiting All Nodes მოწინავე↗CSESMeet in the Middle მოწინავე↗