ბიტმასკური დპ

მიწოდების მარშრუტები, მიკროსქემების ბურღვა, პატარა გუნდების დაგეგმვა: როცა მდგომარეობამ უნდა დაიმახსოვროს, n საქმიდან რომელია უკვე შესრულებული, ეს სიმრავლე მთელი რიცხვის ბიტებად შეინახე. n ≈ 20-მდე ეს n!-იან სრულ გადარჩევას წამიერ გამოთვლად აქცევს.

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

←ეყრდნობა

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

გზას უხსნის→

12P და NP, ალგორითმის არჩევაბიტმასკური დპ კომივოიაჟერს O(2ⁿ·n²)-ში ხსნის: n!-ზე უკეთესია, მაგრამ მაინც ექსპონენციალურია, და ასე გამოიყურება NP-რთული.

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

ისწავლე

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

01ქვესიმრავლე უბრალოდ მთელი რიცხვია

გადავნომროთ ელემენტები 0..n−1. ქვესიმრავლე n-ბიტიანი რიცხვია: j-ური ბიტი 1-ია, როცა j ელემენტი სიმრავლეშია. 4 ქალაქით 1011₂ = 11 ნიშნავს 1, 2 და 4 ქალაქებს (ბიტები 0, 1, 3).

სიმრავლის ყველა ოპერაცია ერთ პროცესორულ ინსტრუქციად იქცევა:

j სიმრავლეშია? mask & (1 << j)
დავამატოთ j: mask | (1 << j); ამოვიღოთ j: mask & ~(1 << j)
სრული სიმრავლე: (1 << n) − 1; ყველა ქვესიმრავლე: for mask in 0 .. 2ⁿ−1

ამიტომ mask-ით ინდექსირებული მასივი dp[mask] თითო ქვესიმრავლეზე ერთ პასუხს ინახავს: სულ 2ⁿ. n = 20-ზე ეს დაახლოებით მილიონია, კომფორტული. n = 30-ზე მილიარდია, ზედმეტად ბევრი. ეს ზღვარი გეუბნება, როდის იფიქრო ბიტმასკურ დპ-ზე: შეზღუდვებში n ≤ 20 ან ასე წერია და ამოცანას „რომელი უკვე გამოყენებულია“ უნდა ახსოვდეს.

შენიშვნა: თუ mask′ mask-ს ელემენტს უმატებს, მაშინ mask′ > mask, ამიტომ ზრდადი რიგი შევსების სწორი რიგია.

02კომივოიაჟერი dp[mask][i]-ით

მოვინახულოთ ყოველი ქალაქი ზუსტად ერთხელ და დავბრუნდეთ საწყის ქალაქში ისე, რომ ჯამური მანძილი მინიმალური იყოს. სრული გადარჩევა (n−1)! რიგს ცდის.

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

dp[mask][i] = უიაფესი გზა, რომელიც 1-ელ ქალაქში იწყება, ზუსტად mask-ის ქალაქებს ინახულებს და i-ში მთავრდება.

ბაზა: dp[{1}][1] = 0;
გადასვლა: (mask, i)-დან გადავდივართ მოუნახულებელ j-ში: dp[mask | j][j] = min(…, dp[mask][i] + D[i][j]);
პასუხი: min(dp[full][i] + D[i][1]) ყველა i-ზე, მარშრუტის დახურვით.

ნახაზის 4 ქალაქისთვის საუკეთესო მარშრუტია 1 → 2 → 4 → 3 → 1 = 10 + 25 + 30 + 15 = 80. მარშრუტის დასაბეჭდად ყოველი მდგომარეობის წინამორბედი შეინახე.

03ექსპონენციალური, მაგრამ ბევრად ნაკლებად, და მზერა NP-ზე

გვაქვს 2ⁿ·n მდგომარეობა და თითოეული n შემდეგ ქალაქს ცდის, ამიტომ დრო O(2ⁿ·n²)-ია, მეხსიერება კი O(2ⁿ·n). n = 20-ზე ეს დაახლოებით 4·10⁸ მარტივი ნაბიჯია, C++-ში ერთი-ორი წამი. სრულ გადარჩევას 20! ≈ 2.4·10¹⁸ დასჭირდებოდა.

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

იგივე ნიმუში ხსნის ბევრ „პატარა სიმრავლის განაწილების / დალაგების“ ამოცანას: ჰამილტონის გზები, n მუშის n სამუშაოზე განაწილება, ნივთების უმცირეს რეისებად დალაგება და სხვა. როცა n ≤ 20-ს ხედავ, სცადე მდგომარეობა dp[mask] ან dp[mask][last] სახით ჩაწერო.

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

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

მეხსიერებაO(2ⁿ·n)

სრული გადარჩევა ყველა მარშრუტზეO(n!)

დაიმახსოვრე

n ≤ ~20 ელემენტის ქვესიმრავლე მთელი რიცხვის ბიტებში ეტევა, ამიტომ dp[mask] თითო ქვესიმრავლეზე ერთ პასუხს ინახავს.
კომივოიაჟერისთვის მომავალს მხოლოდ „რომელი ქალაქებია მონახულებული“ და „სად ვარ ახლა“ სჭირდება, აქედან dp[mask][i].
O(2ⁿ·n²) n!-ს უზარმაზრად სჯობს, მაგრამ მაინც ექსპონენციალურია, როგორც NP-რთული ამოცანისგან არის მოსალოდნელი.

ითამაშე

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

👀 რას უყურო: სტრიქონები mask-ებია (რომელი ქალაქებია მონახულებული), სვეტები ქალაქი, სადაც ვჩერდებით. უყურე, როგორ ივსება უჯრები პატარა mask-ებიდან სრულ 1111 სტრიქონამდე, შემდეგ კი მარშრუტი 1-ელ ქალაქში იხურება.

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

დინამიური პროგრამირება ბიტმასკებით: კომივოიაჟერი (4 ქალაქი, დასაწყისი 1)

mask\\end	1	2	3	4
0001	0	·	·	·
0011	·	·	·	·
0101	·	·	·	·
0111	·	·	·	·
1001	·	·	·	·
1011	·	·	·	·
1101	·	·	·	·
1111	·	·	·	·

კომივოიაჟერის ამოცანა: მოვინახულოთ ყოველი ქალაქი ერთხელ და დავბრუნდეთ, მინიმალური ღირებულებით. მდგომარეობა = (რომელი ქალაქებია მონახულებული ბიტმასკად, მიმდინარე ქალაქი). საბაზისო: მარტო ქალაქ 1-ში, ღირებულება 0.

ფსევდოკოდი

 1 dp[mask][i] = cheapest path from city 1 visiting exactly `mask`, ending at i 2 base: dp[{1}][1] = 0 3 transition: dp[mask|1<<j][j] = min over i in mask of dp[mask][i] + D[i][j] 4 answer = min over i of dp[full][i] + D[i][1]   // close the tour

1 / 1

შეამოწმე

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

№1

5 ელემენტით რომელი mask არის სიმრავლე {0, 2, 4}?

№2

რატომ შეუძლია dp[mask][i]-ს დაივიწყოს, რა რიგით იყო mask-ის ქალაქები მონახულებული?

№3

დაახლოებით რამდენი dp[mask][i] მდგომარეობაა n = 16-ისთვის?

ივარჯიშე

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

LeetCodeSubsets საშუალო↗LeetCodePartition to K Equal Sum Subsets საშუალო↗CSESHamiltonian Flights მოწინავე↗LeetCodeShortest Path Visiting All Nodes მოწინავე↗CSESElevator Rides მოწინავე↗