უკუსვლა და მოკვეთა: N ლაზიერი

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

★ ლექცია: rekursia_queen · ზაზა გამეზარდაშვილი▶ ვიდეო საშუალო⏱ 14 წთ

←ეყრდნობა

4ქვესიმრავლეებისა და გადანაცვლებების გენერაციაუკუსვლა იგივე გენერაციაა, რომელიც განშტოებას მაშინვე ტოვებს, როგორც კი წესი ირღვევა.3სტეკი (LIFO) და გამოსახულების გამოთვლადაბრუნებისას არჩევანის გაუქმება არის მისი ამოღება უკვე გაკეთებული არჩევანების სტეკიდან.

გზას უხსნის→

6სიღრმეში ძებნა (DFS)DFS სიღრმეში მიდის და უკან ბრუნდება ზუსტად ისე, როგორც უკუსვლით ძებნა.

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

ისწავლე

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

01N ლაზიერის ამოცანა

n × n ჭადრაკის დაფაზე დავსვათ n ლაზიერი ისე, რომ არცერთი ორი ერთმანეთს არ უტევდეს. ლაზიერი უტევს თავის სტრიქონს, სვეტს და ორივე დიაგონალს.

წმინდა უხეში გადარჩევა n² უჯრაზე n ლაზიერის დასმის ყველა ხერხს სცდიდა: n = 8-ისთვის ეს დაახლოებით 4.4 მილიარდი განლაგებაა. პირველი დაკვირვება ამას ამცირებს: ორი ლაზიერი ერთ სტრიქონში ვერ იქნება, ამიტომ ყოველ სტრიქონში ზუსტად ერთი ლაზიერი დავსვათ და მხოლოდ სვეტი ავირჩიოთ. რჩება nⁿ ვარიანტი, n = 8-ისთვის დაახლოებით 16.7 მილიონი.

მაგრამ თითქმის ყველა მათგანი უიმედოა უკვე მეორე ლაზიერიდან. თუ პირველი და მეორე ლაზიერი უკვე უტევენ ერთმანეთს, დაფის დასრულების n^(n−2) ხერხიდან (n = 8-ისთვის 8⁶) ვერცერთი უშველის. ძებნამ ეს უნდა შენიშნოს და გაჩერდეს.

02აირჩიე, გამოიკვლიე, გააუქმე

უკუსვლა ამონახსნს თითო გადაწყვეტილებით აგებს. N ლაზიერისთვის place(r) ლაზიერს r სტრიქონში სვამს:

თუ r == n, ყველა ლაზიერი დასმულია: ეს ამონახსნია;
ყოველი სვეტისთვის c: თუ უჯრა შეტევის ქვეშაა, გამოვტოვებთ; თუ არა, ვირჩევთ (ვსვამთ ლაზიერს (r, c)-ზე), ვიკვლევთ (place(r + 1)), და თუ ვერ გამოვიდა, ვაუქმებთ (ვიღებთ ლაზიერს) და შემდეგ სვეტს ვცდით.

როცა r სტრიქონში არცერთი სვეტი არ გამოდგება, place(r) აბრუნებს false-ს და გამომძახებელი თავის ლაზიერს გადაადგილებს. სწორედ ეს უკან დახევაა „უკუსვლა“.

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

03მოკვეთა: მთელი ქვეხეების ჩამოჭრა

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

ეს არის მოკვეთა და სწორედ აქედან მოდის სისწრაფე. n = 4-ისთვის პირველი ამონახსნი მხოლოდ 26 უჯრის შემოწმებისა და 4 უკუსვლის შემდეგ იძებნება, 4⁴ = 256 სრული განლაგების ნაცვლად. n = 8-ისთვის ყველა 92 ამონახსნის პოვნა დაახლოებით 15 700 უჯრას ამოწმებს 16.7 მილიონი სრული განლაგების ნაცვლად.

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

04O(1) შემოწმება და რეალური სირთულე

უჯრის ყველა წინა ლაზიერთან შემოწმება O(n) ღირს. სამი ბულის მასივით შეგიძლია ის O(1) გახადო:

col[c]: სვეტი c დაკავებულია;
d1[r − c + n − 1]: ↘ დიაგონალი დაკავებულია (მის ყველა უჯრას ერთი და იგივე r − c აქვს);
d2[r + c]: ↙ დიაგონალი დაკავებულია (მის ყველა უჯრას ერთი და იგივე r + c აქვს).

ლაზიერის დასმა სამ ალამს ჩართავს, აღება კი გამორთავს. ესაა მთელი „გაუქმების“ ნაბიჯი.

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

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

უარესი შემთხვევაO(n!)

შემოწმება (მასივებით)O(1)

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

დაიმახსოვრე

უკუსვლა ამონახსნს ნაბიჯ-ნაბიჯ აგებს: აირჩიე, რეკურსიულად გამოიკვლიე, შემდეგ გააუქმე და მდგომარეობა აღადგინე.
შეზღუდვების შემოწმება უფრო ღრმად ჩასვლამდე მთელ ქვეხეებს კვეთს, და სწორედ აქედან მოდის აჩქარება.
N ლაზიერისთვის სვეტით, r − c-ითა და r + c-ით ინდექსირებული მასივები ყოველ შემოწმებას O(1)-ად აქცევს.

უყურე

ლექცია ვიდეოს სახით.

▶

ლექცია, ანიმაციით

ვიდეო ლექციას სლაიდ-სლაიდ მიჰყვება: იგივე მაგალითი, იგივე აღნიშვნები. უყურე ვიზუალიზატორთან თამაშამდე ან მის შემდეგ.

▶ ვიდეოს გვერდი ▣ პრეზენტაციად გახსნა

ლექციებიდან ასევე▶ მხედრის ამოცანა

ითამაშე

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

👀 რას უყურო: დააკვირდი, როგორ იზრდება ხე მარჯვნივ: წითელი X-ები მოკვეთილი უჯრებია, ნაცრისფერი წრეები ჩიხებია, საიდანაც უკან დაიხიე. სცადე n = 5 (უკუსვლის გარეშე) და n = 6.

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

4 ლაზიერი: დაფა და ძებნის ხე

ძებნის ხე (წვერო = ლაზიერის სვეტი)

ლაზიერიშეტევის ქვეშმოკვეთილიჩიხი (უკუსვლა)

დავსვათ 4 ლაზიერი 4×4 დაფაზე ისე, რომ არცერთი ორი ერთმანეთს არ უტევდეს. თითო სტრიქონში თითო ლაზიერი; სვეტებს მარცხნიდან მარჯვნივ ვცდით და უიმედო არჩევანს ვაუქმებთ.

ფსევდოკოდი

 1 bool place(int r):           // put a queen in row r 2   if r == n: return true      // all n queens placed 3   for c in 0..n-1: 4     if attacked(r, c): continue    // prune this branch 5     queen[r] = c 6     if place(r+1): return true 7     remove queen[r]            // backtrack, try next c 8   return false                 // dead end

1 / 1

შეამოწმე

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

№1

ლაზიერი დგას სტრიქონ 1-ში, სვეტ 2-ში (0-დან). სტრიქონ 3-ის რომელ უჯრას უტევს ის დიაგონალზე?

№2

place(r)-მა r სტრიქონის ყველა სვეტი სცადა და ყველა შეტევის ქვეშ იყო. რა ხდება შემდეგ?

№3

რატომ ჯობია ყოველი ლაზიერის დასმისთანავე შემოწმება მხოლოდ სრული დაფების შემოწმებას?

ივარჯიშე

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

CSESChessboard and Queens საშუალო↗LeetCodeWord Search საშუალო↗LeetCodeN-Queens მოწინავე↗LeetCodeSudoku Solver მოწინავე↗CSESGrid Path Description მოწინავე↗