უმარტივესი ირაციონალურობის ონლაინ ინტეგრირება. ინტეგრალები ფესვებიდან. ტიპიური მეთოდები და გადაწყვეტილებები. ინტეგრანტის ტრანსფორმაცია
რა არის ეს?
ზოგჯერ მიღებული NP-სრული პრობლემა უნდა მოგვარდეს. ამ შემთხვევაში, პირველ რიგში, ზოგჯერ შესაძლებელია შემცირება სრული ძებნაისე, რომ ალგორითმი, უარეს შემთხვევაში ექსპონენციალური რჩება, იმუშავებს მისაღები დრორეალურ მონაცემებზე. მეორეც, არა ზუსტი გამოსავალი, მაგრამ გარკვეული მიახლოება შეიძლება დამაკმაყოფილებელი აღმოჩნდეს. ალგორითმებს, რომლებიც იძლევა ასეთ გადაწყვეტილებებს, ეწოდება სავარაუდო.
"უხეში ძალის" პრობლემების გადაჭრის მეთოდები შეიძლება დაიყოს რამდენიმე საერთო მეთოდებიუხეში ძალის გაუმჯობესება.
რთული პრობლემების გადაჭრის მეთოდები
- ტოტი და შეკრული მეთოდიმოიცავს აშკარად არაოპტიმალური გადაწყვეტილებების გაუქმებას მთელი კლასების მიხედვით გარკვეული შეფასების შესაბამისად
- მოიცავს უფრო ოპტიმალური გადაწყვეტის ძიებას ზოგიერთი მიმდინარე გადაწყვეტის სიახლოვეს
- მიახლოებითი და ევრისტიკული მეთოდებიმოიცავს ევრისტიკის გამოყენებას გადაწყვეტილების ელემენტების შესარჩევად
- ფსევდოპოლინომიური ალგორითმებიწარმოადგენს ქვეკლასს დინამიური პროგრამირება
- მეთოდი შემთხვევითი ძებნა შედგება არჩევანის, როგორც შემთხვევითი არჩევანის თანმიმდევრობის წარმოჩენისგან
სავარაუდო ალგორითმების ხარისხის შეფასება
მოდით გადავჭრათ ოპტიმიზაციის პრობლემა, ანუ ვეძებთ ობიექტს ყველაზე მაღალი ან დაბალი ღირებულებით იმ ობიექტების სიმრავლეს შორის, რომელზედაც მითითებულია ხარჯების ფუნქცია. აღვნიშნოთ ოპტიმალური გადაწყვეტაროგორც C*. და გამოსავალი, რომელსაც ალგორითმი გვაძლევს არის C.
ჩვენ ვიტყვით, რომ ალგორითმი პრობლემას ხსნის შეცდომით არაუმეტეს ρ(n)-ჯერ თუ
მაქს(C ⁄ C *, C * ⁄ C) ≤ ρ (n)
გაითვალისწინეთ, რომ რადგან ორი ურთიერთშებრუნებული რაოდენობის მაქსიმუმი არ არის 1-ზე ნაკლები, მაშინ
ზოგჯერ უფრო მოსახერხებელია შედარებითი შეცდომის გამოყენება, რომელიც განისაზღვრება როგორც | C − C *| ⁄ C *
ჩვენ ვიტყვით, რომ ალგორითმს აქვს შეცდომა არაუმეტეს ε(n) თუ
| C − C *| ⁄ C * ≤ ε (n)
ადვილია იმის შემოწმება, რომ ε (n) შეიძლება შემოიფარგლოს ზემოდან ρ (n) ფუნქციის მეშვეობით, კერძოდ ε (n) ≤ ρ (n) − 1. მართლაც, მინიმალური ამოცანების შემთხვევაში ეს უტოლობა იქცევა ტოლობაში. მაქსიმალური ამოცანებისთვის ε (n) = (ρ (n) − 1) ⁄ ρ (n) (შემდეგ უნდა გვახსოვდეს, რომ ρ (n) ≥ 1.
მიახლოებითი ალგორითმები ცნობილია მრავალი პრობლემისთვის, პრობლემის გადაჭრაშეცდომით არაუმეტეს გარკვეული ფიქსირებული რაოდენობის ჯერ (მიუხედავად შეყვანის სიგრძისა). სხვა შემთხვევებში, ასეთი ალგორითმები უცნობია და უნდა დაკმაყოფილდეთ ალგორითმებით, რომლებშიც შეცდომის შეფასება იზრდება n-ით.
ზოგიერთი პრობლემის შემთხვევაში შესაძლებელია დაახლოების ხარისხის გაუმჯობესება (ფარდობითი შეცდომის შემცირება) ოპერაციული დროის გაზრდის ხარჯზე. ამისათვის მიახლოების სქემა ოპტიმიზაციის პრობლემაარის ალგორითმი, რომელიც, გარდა პრობლემის პირობებისა, იღებს დადებით რიცხვს ε და იძლევა ამონახსნის ფარდობითი ცდომით არაუმეტეს ε.
მიახლოების სქემას ეწოდება მრავალწევრი, თუ ნებისმიერი ფიქსირებული ε > 0-ისთვის, მისი მუშაობის დრო არ აღემატება ზოგიერთ მრავალწევრს n-ში. მიახლოების სქემას ეწოდება სრულად მრავალწევრი, თუ მისი მოქმედების დრო შემოიფარგლება რამდენიმე მრავალწევრით n-ში და 1 ⁄ ε.
მოგზაური გამყიდველის პრობლემა არის ოპტიმიზაციის მეთოდების ტესტირების საფუძველი.
მოგზაური გამყიდველის პრობლემის ფორმულირება (1934):
მოგზაურმა გამყიდველმა უნდა დატოვოს პირველი ქალაქი, ეწვიოს ქალაქებს 2, 3, ..., n ერთხელ უცნობი თანმიმდევრობით და დაბრუნდეს პირველ ქალაქში. ქალაქებს შორის მანძილი ცნობილია. რა თანმიმდევრობით უნდა შემოუარო ქალაქებს, რომ მოგზაური გამყიდველის დახურული გზა (ტური) იყოს ყველაზე მოკლე?
გრაფიკის თეორიის თვალსაზრისით, პრობლემა შეიძლება ჩამოყალიბდეს შემდეგნაირად: არსებობს სრული მიმართული გრაფიკი G = (V, E), რომლის თითოეული რკალი (u, v) ასოცირდება წონასთან c (u, v). ჩვენ უნდა ვიპოვოთ ყველაზე იაფი ჰამილტონის კონტური ამ გრაფიკში.
მოდით ყურადღება მივაქციოთ დეტალებს, რომლებიც ძალიან მნიშვნელოვანი იქნება პრობლემის გადაჭრის ალგორითმებისთვის:
- ორივე ფორმულირება ვარაუდობს c(u, v) ≥ 0; c (u, u) = ∞ ყველა u, v ∈ V.
- გულუბრყვილო ფორმულირება ვარაუდობს c(u, v) = c(v, u) ყველა u, v ∈ V, ანუ გრაფიკი შეიძლება ჩაითვალოს არამიმართულად. ამ პრობლემას ეწოდება სიმეტრიული მოგზაური გამყიდველის პრობლემა. თუმცა, in ზოგადი შემთხვევა, არ არის სავალდებულო.
- გულუბრყვილო ფორმულირებით, ჩვენ ვვარაუდობთ, რომ ყველა u, v, w ∈ V c (u, v) ≤ c (u, w) + c (w, v) (სამკუთხედის უტოლობა), რომელიც ხშირად მოქმედებს პრაქტიკული პრობლემები. თუმცა, ზოგადად რომ ვთქვათ, ეს სიმართლეს არ შეესაბამება.
თეორემა
ვთქვათ P ≠ NP, ρ ≥ 1. მაშინ არ არსებობს პოლინომიური მიახლოების ალგორითმი, რომელიც ხსნის ზოგად (უფრო მეტიც, სიმეტრიულ) მოგზაური გამყიდველის პრობლემას არა უმეტეს ρ-ჯერ შეცდომით.
მტკიცებულება.დასამტკიცებლად, გაითვალისწინეთ, რომ თვითნებური გრაფიკის აღება G = (V, E) და მასთან დაკავშირება სრული გრაფიკის G ′ ღირებულება c (u, v) = 1, თუ (u, v) ∈ E და ρ | V | + 1 წინააღმდეგ შემთხვევაში. დავრწმუნდეთ, რომ ჩვენი პოლინომიური ალგორითმი განსაზღვრავს, შეიცავს თუ არა გრაფიკი G ჰამილტონის ციკლს, რაც შეუძლებელია.
ფილიალისა და შეკრული მეთოდი („უკან დაბრუნება“)
ეს მეთოდი ერთ-ერთი პირველი ეფექტური იმპლიციტური (გაუმჯობესებული) ჩამოთვლის სქემაა, რომლის იდეაც მდგომარეობს იმაში, რომ ექსტრემალური პრობლემის გადაჭრისას, სრული ჩამოთვლის თავიდან აცილება შესაძლებელია აშკარად არაოპტიმალური გადაწყვეტილებების გაუქმებით.
მეთოდის იდეა ასეთია: დისკრეტული ექსტრემალური პრობლემის გადაჭრისას ჩვენ ვყოფთ ყველა სიმრავლეს შესაძლო ვარიანტებიკლასებად და შეადგინეთ შეფასებები მათთვის. შედეგად, შესაძლებელი ხდება გადაწყვეტილებების მთელი კლასის გაუქმება, თუ მათი ქულა უარესია გარკვეულ ჩანაწერზე.
განვიხილოთ დისკრეტული ექსტრემალური (განსაზღვრულობისთვის, მინიმალური) პრობლემა ზოგადი ფორმით:
მიეცით A დისკრეტული სიმრავლე და მასზე განისაზღვროს ფუნქცია f. F ფუნქციის მინიმუმი X-ზე ავღნიშნოთ, როგორც F (X).
თქვენ უნდა იპოვოთ x 0 ∈ A: f (x 0) = F (A)
შენიშვნა 1
მოდით A = A 0 ∪ A 1 ∪ … ∪ A k , A i ∩ A j = Ø, i ≠ j . უფრო მეტიც, F (A)< F (A 0), т. е. на A 0 минимум не достигается.
მაშინ სწორია შემდეგი: F (A) = min (F (A i) | i ∈ 1: k )
შენიშვნა 2
ვთქვათ Φ არის A სიმრავლის ქვესიმრავლეების კრებულზე განსაზღვრული ფუნქცია, რომ Φ (X) ≤ F (X) ∀ X ⊂ A
მოდით x * იყოს A-ს თვითნებური ელემენტი და მოდით, f * = f (x *).
მაშინ სწორია შემდეგი: F (A) = min ( f *, min ( F (A i) | i ∈ 1: k, Φ (A i) ≤ f *) )
ეს ორი მოსაზრება საშუალებას გვაძლევს შემოგთავაზოთ შემდეგი ტექნოლოგია მინიმალურის საპოვნელად. მოდით გავყოთ A სიმრავლე რამდენიმე A i ქვეჯგუფად და თითოეულ მათგანზე ვიპოვოთ Φ-ს ქვედა ზღვარი. A სიმრავლის ელემენტებისთვის ჩვენ გამოვთვლით f ფუნქციის მნიშვნელობებს და დავიმახსოვრებთ უმცირესს, როგორც ჩანაწერის მნიშვნელობას. ჩვენ გავაერთიანებთ ყველა ქვესიმრავლეს, რომელთა ქულა აღემატება ფუნქციის ჩანაწერის მნიშვნელობას (f *) ქვეჯგუფში A 0, რათა არ განვიხილოთ იგი შემდგომში.
ახლა ავირჩიოთ რომელიმე კომპლექტი A i, i > 0. მოდით დავყოთ ეს ნაკრები რამდენიმე პატარა ქვეჯგუფად. ამავდროულად, ჩვენ გავაგრძელებთ რეკორდული f* მნიშვნელობის გაუმჯობესებას. ეს პროცესი გრძელდება მანამ, სანამ ყველა კომპლექტი A i, i > 0 არ განიხილება.
განშტოებისა და შეკრული მეთოდი (უკან უკანა დაბრუნება) შეიძლება უფრო ნათლად აიხსნას შესაძლებლობების ხის გამოყენებით. ასეთი ხის კვანძები შეიძლება ჩაითვალოს კონფიგურაციების კოლექციად (A i ქვესიმრავლეები) და გარკვეული კვანძის თითოეული შთამომავალი წარმოადგენს ამ კოლექციის ქვეჯგუფს. და ბოლოს, თითოეული ფურცელი წარმოადგენს განსხვავებულ კონფიგურაციას.
მაგალითი 1. მოგზაური გამყიდველის პრობლემა (ლიტლის ალგორითმი)
მოდით შევხედოთ ამ ალგორითმის მოქმედებას კონკრეტული მაგალითის გამოყენებით.
მოდით იყოს გრაფიკი, რომელიც განისაზღვრება მიმდებარე მატრიცით:
| — | 6 | 4 | 8 | 7 | 14 |
| 6 | — | 7 | 11 | 7 | 10 |
| 4 | 7 | — | 4 | 3 | 10 |
| 8 | 11 | 4 | — | 5 | 11 |
| 7 | 7 | 3 | 5 | — | 7 |
| 14 | 10 | 10 | 11 | 7 | — |
მართალია შემდეგი: გამოვაკლოთ ნებისმიერი მუდმივი C მატრიცის ნებისმიერი მწკრივის ან სვეტის ყველა ელემენტს, მინიმალურ ტურს ვტოვებთ როგორც მინიმუმს. ამასთან დაკავშირებით, თითოეული მწკრივიდან მისი მინიმალური ელემენტის გამოკლების პროცესი (ხაზ-სტრიქონი ჩამოსხმა) გავლენას არ ახდენს მინიმალურ ტურზე. ანალოგიურად, შემოღებულია სვეტის შემცირების კონცეფცია, რომელსაც აქვს იგივე თვისება.
წარმოვადგინოთ ორიგინალური მატრიცის მწკრივი
Ორიგინალური
| — | 6 | 4 | 8 | 7 | 14 |
| 6 | — | 7 | 11 | 7 | 10 |
| 4 | 7 | — | 4 | 3 | 10 |
| 8 | 11 | 4 | — | 5 | 11 |
| 7 | 7 | 3 | 5 | — | 7 |
| 14 | 10 | 10 | 11 | 7 | — |
ჩამოთვლილია სტრიქონი-სტრიქონი
| — | 2 | 0 | 4 | 3 | 10 | |4 |
| 0 | — | 1 | 5 | 1 | 4 | |6 |
| 1 | 4 | — | 1 | 0 | 7 | |3 |
| 4 | 7 | 0 | — | 1 | 7 | |4 |
| 4 | 4 | 0 | 2 | — | 4 | |3 |
| 7 | 3 | 3 | 4 | 0 | — | |7 |
შერჩეული თამამადორიგინალური მატრიცის რიცხვები არის ლექსიკოგრაფიული ძიების შედეგად მიღებული იდეალური ტური.
(გაითვალისწინეთ, რომ შემცირების მუდმივთა ჯამი არის 4 + 6 + 3 + 4 + 3 + 7 = 27)
და შემდეგ სვეტის მიხედვით:
| — | 0 | 0 | 3 | 3 | 6 |
| 0 | — | 1 | 4 | 1 | 0 |
| 1 | 2 | — | 0 | 0 | 3 |
| 4 | 5 | 0 | — | 1 | 3 |
| 4 | 2 | 0 | 1 | — | 0 |
| 7 | 1 | 3 | 3 | 0 | — |
| — | — | — | — | — | — |
| 0 | 2 | 0 | 1 | 0 | 4 |
(გაითვალისწინეთ, რომ შემცირების მუდმივთა ჯამი აქ არის 0 + 2 + 0 + 1 + 0 + 4 = 7, და ყველა მუდმივის: 27 + 7 = 34)
ახლა, ტური, რომელიც გაივლის მხოლოდ ნულოვანი ღირებულების კიდეებს, აშკარად მინიმალური იქნება. მისი ღირებულების დასადგენად, ჩვენ ვამატებთ ნულს ახლად გამოთვლილ მუდმივ 34-ს:
ამრიგად, ჩვენ მივიღეთ ყველა შესაძლო ტურის კლასის ღირებულების დაბალი შეფასება. ანუ ამ პრობლემაში მინიმალური რაუნდი 34-ზე ნაკლები არ შეიძლება დაჯდეს.
დავურეკოთ შეფასებანული მატრიცაში პოზიციაზე (i, j) არის მინიმალური ელემენტების ჯამი i-ე სტრიქონში და j-th სვეტში (თვითონ ეს ნული არ ჩაითვალოს). ახლა შევაფასოთ თითოეული ნული მოცემულ მატრიცაში:
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | — | 0 1 | 0 | 3 | 3 | 6 |
| 2 | 0 1 | — | 1 | 4 | 1 | 0 |
| 3 | 1 | 2 | — | 0 1 | 0 | 3 |
| 4 | 4 | 5 | 0 1 | — | 1 | 3 |
| 5 | 4 | 2 | 0 | 1 | — | 0 |
| 6 | 7 | 1 | 3 | 3 | 0 1 | — |
კლასები, ნულის ტოლი, მითითებული არ არის. ქულა k ნული, პოზიციაში (i, j) სიტყვასიტყვით ნიშნავს შემდეგს: თუ ტური არ მოიცავს გზას i-დან j-მდე (ღირებულება 0), მაშინ მოგიწევთ მინიმუმ k-ის გადახდა. აქედან გამომდინარე, ჩვენ შეგვიძლია გავყოთ ყველა შესაძლო ტურის კლასი ორად: ტურები, რომლებიც შეიცავს ზღვარს (i, j) და ტურებს, რომლებიც არ შეიცავს მას. ამ უკანასკნელისთვის მინიმალური ქულა გაიზრდება კ.
განვიხილოთ ნულის შესაბამისი ზღვარი მაქსიმალური ქულით. IN ამ შემთხვევაშიეს არის ზღვარი (1, 2). ამრიგად, როგორც უკვე აღვნიშნეთ, ყველა ტურის კლასი იყოფა ორად: ის, რომელიც შეიცავს ზღვარს (1, 2) და ის, რომელიც არ შეიცავს მას. მეორე კლასის ტურების ღირებულების ქვედა შეფასება იზრდება 35-მდე. პირველი კლასის ტურების შეფასების დასადგენად, ამოიღეთ მატრიციდან 1 მწკრივი და სვეტი 2 (მოდით ავღნიშნოთ როგორც C [(1,2)]) :
მას შემდეგ, რაც მატრიცას შეეძლო 1-მდე შემცირება (1 სვეტში), ტურების კლასის შეფასება ზღვარზე (1, 2) იზრდება 1-ით და ხდება 35-ის ტოლი.
კლასებად დაყოფა და თავად შეფასებები შეიძლება წარმოდგენილი იყოს როგორც ხე:
ამრიგად, კლასი (ALL) დაიყო ორად და გამოითვალა შესაბამისი ქულები.
ახლა ავირჩიოთ ყველაზე დაბალი ქულის მქონე კლასი და გავიმეოროთ ეს პროცესი მისთვის. შემდეგ მიღებული ორი კლასიდან ვირჩევთ მინიმალური ქულით და ვყოფთ. ამას ვიმეორებთ სანამ ხის ფოთოლს არ მივაღწევთ. ანუ, სანამ არ მივიღებთ 0×0 მატრიცას:
C [(1, 2); [−](a 1, b 1); [−](a 2, b 2); … [−](a k, b k)]
სადაც (თითოეული) −(x, y) ნიშნავს, რომ მატრიცა შეესაბამება კლასს, რომელიც არ შეიცავს −(x, y) კიდეს მატრიცის აღნიშვნიდან, მივიღებთ შემდეგს :
(c 0, d 0); (c 1, d 1); … (c n, d n)
ხის წვერო (5, 4) შეესაბამება კლასს, რომელიც შეიცავს კიდეებს: (1, 2); (3, 1); (6, 5); (2, 6); (4, 3); (5, 4). ეს კლასი აშკარად შედგება ერთი სრული ტურისგან (1, 2, 6, 5, 4, 3, 1) ღირებულება = 36 (სრული ტურისთვის მისი მინიმალური ქულა უდრის ზუსტ ღირებულებას)
გავიხსენოთ ეს შედეგი, როგორც რეკორდული და გადავიდეთ ხეზე მაღლა, „გადაკვეთეთ“ ყველა წვერო (ანუ შემდგომი განხილვისგან ყველა კლასის გამოკლებით), რომელთა ქულები მეტია ან ტოლია ახლახან ნაპოვნის. გარდა ამისა, ჩვენ გადავხაზავთ წვეროს იმ შემთხვევაშიც კი, თუ მისი ორივე შთამომავალი გადახაზულია, მიუხედავად მისი შეფასებისა. ჩვენ ვიღებთ შემდეგს:
მეორე სვეტში მოცემული ტურების კლასის შესაბამისი მატრიცა, რომელიც არ შეიცავს ზღვარს (1, 2), ასე გამოიყურება:
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | — | — | 0 3 | 3 | 3 | 6 |
| 2 | 0 1 | — | 1 | 4 | 1 | 0 |
| 3 | 1 | 1 | — | 0 1 | 0 | 3 |
| 4 | 4 | 4 | 0 1 | — | 1 | 3 |
| 5 | 4 | 1 | 0 | 1 | — | 0 |
| 6 | 7 | 0 1 | 3 | 3 | 0 | — |
იგი მიღებული იყო მატრიციდან, რომელიც შეესაბამება ყველა ტურის კლასს, ელემენტის (1, 2) ნაცვლად ტირე (უსასრულო ფრენის ღირებულების აღმნიშვნელი) ჩასმით. იმათ. 1,2 = ∞-ით. ავღნიშნოთ როგორც C [−(1,2)]
ვინაიდან ნულის მაქსიმალური ქულა არის 3 (ელემენტი 1,3), მივიღებთ, რომ −(1,3) ტოტის ქულა უდრის 38-ს.
პირველი რიგისა და პირველი სვეტის გადაკვეთით, ვიღებთ მატრიცას, რომელიც მცირდება 1-მდე მეოთხე რიგში. ანუ განშტოების ქულა −(1,2)(1,3) უდრის 36-ს. ჩვენ გავაგრძელებთ შემდგომ განშტოებას ნაპოვნი ჩანაწერის მნიშვნელობის (36) გათვალისწინებით:
ამრიგად, წვეროები აღარ დარჩა, ძებნა დასრულებულია. და მის დროს და შესაბამისი რაუნდის დროს ნაპოვნი ჩანაწერი არის პრობლემის გადაწყვეტა.
არ არსებობს დამაკმაყოფილებელი თეორიული შეფასებები პატარას და სხვა მსგავსი ალგორითმის შესახებ, მაგრამ პრაქტიკა გვიჩვენებს, რომ თანამედროვე მანქანებზე ისინი საშუალებას გაძლევთ გადაჭრას მოგზაური გამყიდველის პრობლემა წვეროების რაოდენობით ≈ 100. გარდა ამისა, განშტოება და შეკრული ალგორითმები ეფექტური ევრისტიკული პროცედურებია. . თუ მათი დასრულება შეუძლებელია.
მაგალითი 2. მიკროსქემის გახსნის პრობლემა
იგივე მიდგომა შეიძლება გამოყენებულ იქნას სქემების გახსნის პრობლემასთან დაკავშირებით. პრობლემის ფორმულირება:
მოყვანილი იყოს გრაფიკი G = (V, E), რომლის თითოეული რკალი (u, v) ასოცირდება დადებით რიცხვთან c (u, v) - ამ რკალის წონასთან.
საჭიროა მოიძებნოს E 0 ⊂ E ისე, რომ გრაფიკს (V , E 0) არ ჰქონდეს კონტურები და რკალების წონების ჯამი (E 0-დან) მაქსიმალური იყოს.
მოდით განვიხილოთ დამხმარე ამოცანა (ჩვენ აღვნიშნავთ მას (E , E *)) ახლახან ჩამოყალიბებულის მსგავსი, მაგრამ დამატებითი პარამეტრი— ნაკრები E * ⊂ E, საიდანაც არ შეიძლება რკალების ამოღება (ამ შემთხვევაში მოვითხოვთ, რომ გრაფიკი (V , E *) არ შეიცავდეს კონტურებს).
თუ არის პრობლემა (E, E *), მაშინ შესაძლებელია მისი ამონახსნების მთელი ნაკრები დაიყოს ორ კლასად შემდეგნაირად.
განვიხილოთ რკალი (u, v) ∈ E\E* ისე, რომ გრაფიკს (V, E* ∪ (u, v)) არ ჰქონდეს კონტურები.
შემდეგ პრობლემის გადაწყვეტილებების ნაკრები შეიძლება დაიყოს ორად:
- პრობლემის გადაწყვეტილებების ნაკრები (E \ (u, v), E *)
- პრობლემის გადაწყვეტილებების ნაკრები (E, E* ∪ (u, v))
სქემების გახსნის თავდაპირველი პრობლემა აშკარად პრობლემაა (E, Ø).
ახლა წარმოვიდგინოთ ფუნქცია est(E, E 0) შემდეგნაირად:
- თუ გრაფიკი (V, E) არ შეიცავს ციკლებს, მაშინ est(E, E 0) = 0
- წინააღმდეგ შემთხვევაში, მოდით, E cyc იყოს ციკლი, მაშინ: est(E, E 0) = est(E \ E cyc, E 0) + c cyc, სადაც c cyc = min( c (u, v) | (u, v ) ∈ E cyc \ E 0 ) (ანუ მინიმალური წონა, რომელიც შეიძლება გამოყენებულ იქნას ამ ციკლის გასახსნელად)
ამის ჩვენება ადვილია
V (E, E 0) ≥ est(E, E 0),
სადაც v (E, E 0) არის რკალების წონების მინიმალური ჯამი, რომელთა ამოღება E \ E 0-დან ხსნის გრაფის ყველა კონტურს.
ადგილობრივი გაუმჯობესების მეთოდი ("ლოკალური ძებნა")
ამ მეთოდის იდეა მდგომარეობს იმაში, რომ x ∈ X ექსტრემალური ამოცანის თითოეული ამოხსნისთვის განისაზღვრება A (x) ახლო ამონახსნების მეზობლობა და გამოთვლითი პროცესის ყოველი გამეორებისას მოცემული მიმდინარე ამონახსნებისთვის x ხდება მცდელობა იპოვოთ. მის სამეზობლოში გამოსავალი რომ ექნებოდა საუკეთესო ფასი ობიექტური ფუნქცია. თუ ასეთი გამოსავალი მოიძებნება, ის თავად ხდება ამჟამინდელი გამოსავალი, თუ არა, ძიება მთავრდება.
უფრო კონკრეტულად სტრატეგია ადგილობრივი ძებნაეს არის:
- დაიწყეთ შემთხვევითი გადაწყვეტით
- მიმდინარე გადაწყვეტის გასაუმჯობესებლად, მიმართეთ მას ნებისმიერი ტრანსფორმაცია გარდაქმნების მოცემული ნაკრებიდან. ეს გაუმჯობესებული გამოსავალი ხდება მიმდინარე გადაწყვეტა
- გაიმეორეთ ეს პროცედურა მანამ, სანამ მოცემულ კომპლექტში არცერთი ტრანსფორმაცია არ გააუმჯობესებს მიმდინარე ამოხსნას
თუ გარდაქმნების მოცემული ნაკრები მოიცავს ყველა შესაძლო ტრანსფორმაციას (რომელიც ნებისმიერი ამონახსნისგან შეიძლება მივიღოთ ნებისმიერი სხვა), მაშინ მივიღებთ ზუსტ (გლობალურად ოპტიმალურ) გადაწყვეტას, მაგრამ ასეთი ალგორითმის სირთულე არ იქნება უკეთესი, ვიდრე ყველა ამონახსნის ჩამოთვლა. .
პრაქტიკაში, პრობლემების გადაჭრისას, რომელთა ზუსტი გადაწყვეტილებები მოითხოვს ექსპონენციალურ დროს, გარდაქმნების ნაკრები შეზღუდულია. მათი დახმარებით არაერთი თვითნებური გადაწყვეტილებებიდან მიიღება ლოკალურად ოპტიმალური გადაწყვეტილებები და შეირჩევა საუკეთესო.
მოდით განვიხილოთ ზუსტი ალგორითმი გრაფაში მინიმალური გაშლილი ხის მოსაძებნად ლოკალური ძიების მეთოდის გამოყენებით. ლოკალური გარდაქმნები იქნება შემდეგი: ჩვენ ვიღებთ ამა თუ იმ ზღვარს, რომელიც არ არის დაკავშირებული მიმდინარე გაშლილ ხესთან და ვამატებთ ხეს (ციკლის მიღება), შემდეგ კი ამ ციკლიდან ერთ კიდეს ვხსნით (ყველაზე მაღალი ღირებულებით). ეს გრძელდება მანამ, სანამ ხის გარეთ ყველა კიდე არ იქნება უმაღლესი ღირებულებამარყუჟის ყველა კიდეს შორის, რომელიც წარმოიქმნება ხეზე დამატებისას (ამ შემოწმებას სჭირდება O(|V||E|) დრო). ეს ალგორითმი უფრო ნელია ვიდრე Prim და Kruskal-ის ალგორითმები და არის მაგალითი. ირაციონალური გამოყენებაარა-NP-სრული პრობლემების ლოკალური ძიება.
მაგალითი 2. მოგზაური გამყიდველის პრობლემა (ორმაგი არჩევანი)
უმარტივესი ტრანსფორმაცია, რომელიც შეიძლება გამოვიყენოთ სიმეტრიული მოგზაური გამყიდველის პრობლემაში, არის ეგრეთ წოდებული „ორმაგი არჩევანი“. ის მდგომარეობს იმაში, რომ ჩვენ ვირჩევთ ნებისმიერ ორ ზღვარს (მაგალითად (a, b) და (c, d)), ვშლით მათ და „ხელახლა ვცვლით“ მათ მიერ დაკავშირებულ წერტილებს ისე, რომ ჩამოყალიბდეს ახალი მარშრუტი. თუ ორი ახალი კიდეების ხარჯების ჯამი ორ ძველზე ნაკლებია, მაშინ ჩვენ ვიპოვეთ გაუმჯობესებული მარშრუტი.
განვიხილოთ იგივე გრაფიკი, რომლისთვისაც ჩვენ ავაშენეთ გაშლილი ხე. ავირჩიოთ (a, b, c, d, e) საწყის მარშრუტად და მივმართოთ მას „ორმაგი არჩევანი“. ადვილია იმის დადასტურება, რომ ფიგურაში "c" შეუძლებელია ერთი წყვილი კიდეების ამოღება სხვა უპირატესად ჩანაცვლებით.
ორმაგი არჩევანი შეიძლება განზოგადდეს k-არჩევანზე. ამ შემთხვევაში, ჩვენ ვხსნით k-მდე კიდეებს და "გადავრთავთ" დარჩენილ ელემენტებს ნებისმიერი თანმიმდევრობით, ვცდილობთ მივიღოთ მარშრუტი. ზოგადად, ჩვენ არ ვითხოვთ, რომ მოსახსნელი კიდეები არ იყოს მიმდებარე.
რაოდენობის დადასტურება ადვილია სხვადასხვა ტრანსფორმაციები, რომელიც გასათვალისწინებელია k -შერჩევისთვის არის O(|V|k). თუმცა, დროა საჭირო ნებისმიერის მისაღებად ოპტიმალური მარშრუტი, შეიძლება ბევრად მეტი აღმოჩნდეს.
პრაქტიკაში „ცვლადი სიღრმის შერჩევა“ ძალიან ეფექტურია. დიდი ალბათობით უზრუნველყოს ოპტიმალური მარშრუტი | V | = 40 − 100.
მაგალითი 3: ბლოკის განლაგების პრობლემა
ერთგანზომილებიანი ბლოკის განლაგების პრობლემის ფორმულირება: საჭიროა უმართავი გრაფის წვეროების დალაგება c (u, v) კიდეებზე წონებით, მათი ნუმერაცია 1 ... n რიცხვებით. ∑ i, j = 1 ... n | i − j | c (v i, v j); n = | V|.
გრაფიკის წვეროებს ჩვეულებრივ უწოდებენ "ბლოკებს", ხოლო წონები ინტერპრეტირებულია, როგორც "მავთულის" რაოდენობა ბლოკებს შორის. მაშინ ირკვევა პრობლემის არსი: აუცილებელია ელემენტების დალაგება სწორ ხაზზე ისე, რომ მათ დასაკავშირებლად საჭირო სადენების სიგრძე მინიმალური იყოს.
ეს, ისევე როგორც მსგავსი ორგანზომილებიანი პრობლემა, პოულობს გამოყენებას ლოგიკური დაფების დასაკავშირებლად და ინტეგრირებული სქემების შესაქმნელად.
ბლოკის განთავსების პრობლემის ლოკალური ოპტიმალური გადაწყვეტილებების მოსაძებნად, შეგიძლიათ გამოიყენოთ შემდეგი ადგილობრივი გარდაქმნები:
- განახორციელეთ მეზობელი ბლოკების v i და v i +1 ურთიერთგადაწყობა, თუ მიღებულ შეკვეთას უფრო დაბალი ღირებულება აქვს. დაე
L (j) = ∑ k =1… j −1 c (v k , v j);
R (j) = ∑ k = j +1… n c (v k, v j).გაუმჯობესება შესაძლებელია, თუ
L (i) − R (i) + R (i +1) − L (i +1) + 2 c (v i, v i +1)< 0
- აიღეთ v i ბლოკი და ჩადეთ ის რამდენიმე ბლოკს შორის v i და v i +1 i და j მნიშვნელობებისთვის.
- შეასრულეთ ორი ბლოკის vi და v j ურთიერთ გადაწყობა.
როგორც მოგზაური გამყიდველის პრობლემაში, ჩვენ არ შეგვიძლია ზუსტად გამოვთვალოთ დრო, რომელიც საჭიროა ადგილობრივი ოპტიმუმის მოსაძებნად. შეიძლება აჩვენოს, რომ თუ ჩვენ შემოვიფარგლებით ტრანსფორმაციით ( 1 ), O(|V|) დრო საკმარისი იქნება იმისათვის, რომ შეამოწმოთ არის თუ არა შესრულებული ტრანსფორმაცია გაუმჯობესებული და გამოვთვალოთ L(i) და R(i). ტრანსფორმაციისთვის ( 2 ) და ( 3 ) ეს დრო იზრდება O(|V|2-მდე). მაგრამ ეს არ არის ლოკალური ოპტიმუმის პოვნის დროის შეფასება, რადგან ყოველმა გაუმჯობესებამ შეიძლება შექმნას ახალი გაუმჯობესების შესაძლებლობები.
მიახლოებითი და ევრისტიკული მეთოდები
ამ განყოფილებაში განვიხილავთ ალგორითმებს, რომლებიც მუშაობენ ჩვენთვის ცნობილ პოლინომიურ დროში და გადაჭრიან „უხეში ძალის“ ამოცანებს ჩვენთვის ცნობილი შეცდომით. მიახლოებით და ევრისტიკულ მეთოდებს შორის ზღვარი ბუნდოვანია. ზოგიერთი მიახლოებით ალგორითმებად განასხვავებს მათ, რომლებშიც შესაძლებელია შეცდომის კორექტირება, ანუ მიახლოების სქემები.
ევრისტიკულ მეთოდებში, გარკვეული ერთი შეხედვით ბუნებრივი რეკომენდაციები გამოიყენება გადაწყვეტილების ელემენტების შესარჩევად. შერჩევის წესები, ევრისტიკა. ხშირად ასეთი წესები შერწყმულია არჩევანის სიხარბის პირობასთან: გაკეთებული არჩევანი შემდგომში არ გადაიხედება. მეტი ძლიერი ჯიშიეს მიდგომა არის შემცირებული ძიება, რომელშიც ჩვენთვის ნაცნობი ოფციონების ხე, რომელიც ჩვენთვის არის ნაცნობი ტოტიდან და შეკრული მეთოდით, ხელოვნურად მცირდება გარკვეული წესების საფუძველზე, რომლებიც დამაჯერებელია, მაგრამ არა ფორმალურად გამართლებული.
მაგალითი 1. მოგზაური გამყიდველის პრობლემა (ხის ალგორითმი)
განვიხილოთ სამი ევრისტიკული ალგორითმი, რომლებიც ხსნის სიმეტრიული პრობლემამოგზაური გამყიდველი სამკუთხედის უტოლობით ცდომით არაუმეტეს ორჯერ (ρ = 2).
პირველი მათგანი, ეგრეთ წოდებული ხის ალგორითმი, ასეთია: მოდით ავაშენოთ მინიმალური გაშლილი ხე ჩვენი გრაფისთვის Prim-ის ალგორითმის გამოყენებით და შემდეგ გადავკვეთოთ ხე თანმიმდევრობით. ფესვი-მარცხნივ-მარჯვნივ, დუბლიკატი წვეროების წაშლა.
ამ ალგორითმის მუშაობის დროა Θ(E) = Θ(V 2).
მაგალითი 1. მოგზაური გამყიდველის პრობლემა (ხარბი და კარგ-ტომპსონის ალგორითმები)
ყველაზე აშკარა ალგორითმი მოგზაური გამყიდველის პრობლემის გადასაჭრელად არის ხარბი: ამჟამინდელი ქალაქიდან გადადით უახლოეს ქალაქში, რომელიც ჯერ არ გინახიათ. თუ სამკუთხედის უტოლობა ძალაშია, ძნელი არ არის იმის დამტკიცება, რომ ეს ალგორითმი მაქსიმუმ ორჯერ მცდარია. ამ ალგორითმის სირთულეა O(V 2).
Karg-Thompson ალგორითმი (უახლოესი წერტილის ევრისტიკა) ოდნავ ნაკლებად აშკარაა: ჯერ ვიღებთ ორ უახლოეს წვეროს (გადაგვარებული ტური), შემდეგ ციკლში უკვე აგებული ტურის ყველა კიდეზე, თითოეული კიდეზე (u, v) თავისუფალი წვეროებიდან აირჩიეთ w ისეთი, რომ c ( u , w) + c (w , v) − c (u , v) იყოს მინიმალური და w ჩავრთოთ ტურში u და v შორის. ამ მეთოდისთვის ასევე ρ = 2, მაგრამ მისი სირთულე უკვე არის O (V 3).
მაგალითი 2. წვეროს საფარის პრობლემა
შეგახსენებთ, რომ უმართავი გრაფის წვეროს საფარი G =(V , E) არის მისი V წვეროების გარკვეული ოჯახი შემდეგი თვისებით: G გრაფის ყოველი კიდეზე (u , v) მისი ერთი ბოლო მაინც u ან. v შეიცავს V ′-ში. წვეროს საფარის ზომა არის მასში შემავალი წვეროების რაოდენობა.
წვეროს საფარის პრობლემა შედგება მინიმალური ზომის წვეროს საფარის პოვნაში. ეს პრობლემა NP-მყარია, მაგრამ ქვემოთ მოცემული მარტივი ალგორითმი აგვარებს მას არაუმეტეს ორჯერადი შეცდომით.
დავუშვათ, C იყოს წვეროს საფარის უკვე აგებული ნაწილი, ხოლო E ′ შეიცავდეს გრაფიკის დაუფარავ კიდეებს. ყოველ საფეხურზე ჩვენ ვიღებთ ზღვარს E-დან და ვამატებთ მის ბოლოებს u და v-ს C-ს, ხოლო E-დან ვხსნით ყველა კიდეს მათი ბოლო წერტილებით u ან v. და ასე შემდეგ მანამ, სანამ E კომპლექტი ცარიელი არ გახდება. ამ ალგორითმის მუშაობის დრო არის O(E).
იმის დასამტკიცებლად, რომ ეს ალგორითმი არ არის ორჯერ ცუდი ვიდრე ზუსტი, საკმარისია აღინიშნოს, რომ ალგორითმის მიერ შერჩეულ ორ კიდეს არ აქვს საერთო წვეროები, რაც ნიშნავს, რომ წვეროების რაოდენობა C-ში ორჯერ აღემატება ამ კიდეების რაოდენობას. . ოპტიმალური საფარი შეიცავს თითოეული მათგანის მინიმუმ ერთ წვეროს და ყველა ეს წვერო განსხვავებულია.
მოცემულია X სასრული სიმრავლე და მისი F ქვესიმრავლეების ოჯახი. სადაც:
X =∪ S ∈ F S
ჩვენ ვეძებთ F-ის ქვეჯგუფების მინიმალურ რაოდენობას, რომლებიც ერთად ფარავს X სიმრავლეს, ანუ უმცირესი კარდინალობის C ოჯახს, რომლისთვისაც:
X =∪ S ∈ C S
ასეთ C ოჯახს დავარქმევთ X სიმრავლის საფარს. მაგალითად, ფიგურაში შავი წრეები X სიმრავლის ელემენტებია, კონტურები არის F-ის ქვესიმრავლეები. სამი მსუბუქი მყარი კონტური შეადგენს მინიმალურ დაფარვას.
ჩვენ მოვაგვარებთ პრობლემას ხარბი მიახლოების ალგორითმის გამოყენებით. მოდით, U სიმრავლე შეიცავდეს ელემენტებს, რომლებიც ჯერ არ არის დაფარული, ხოლო C ოჯახი შეიცავდეს ქვეჯგუფებს, რომლებიც უკვე შედის გაშუქებაში. ყოველ ნაბიჯზე კეთდება გაუმაძღარი არჩევანი: ნაკრები, რომელიც მოიცავს ყველაზე მეტ ელემენტს, რომელიც ჯერ არ არის დაფარული, აღებულია როგორც S.
ეს ხდება მანამ, სანამ U ცარიელია. ალგორითმის სირთულე არის O (| X |·| F |·min(| X |,| F |)).
ამ ალგორითმის მიერ მოცემული დაფარვის ზომა აღემატება შესაძლებელ მინიმუმს არაუმეტეს H (max(| S |: S ∈ F )) ჯერ (სადაც H (d) არის პირველი d პუნქტების ჯამი. ჰარმონიული სერია) ან, რაც იგივეა, (ln| X | + 1)-ჯერ.
ფსევდოპოლინომიური ალგორითმები
ასეთი ალგორითმები ხშირად მიიღება დინამიური პროგრამირების გამოყენებით NP-სრული პრობლემები. ასეთ ალგორითმებს აქვთ ოპერაციული დროის (და კომპიუტერის მეხსიერების) ექსპონენციალური დამოკიდებულება შეყვანის სიგრძეზე, მაგრამ პრობლემის შეყვანისას არის პოლინომიური დამოკიდებულება გარკვეულ რიცხვზე (რიცხვებზე). ასეთი ალგორითმები ძალიან სასარგებლოა, რადგან ისინი საშუალებას გაძლევთ გადაჭრათ პრობლემები მცირე რიცხვებით ზუსტად და დაახლოებით დიდი რაოდენობით, როგორღაც პატარებად გარდაიქმნა.
მაგალითი 1. ქვესიმრავლეების ჯამის ამოცანა ("ტაბულური" ალგორითმი)
მიეცით წყვილი (S, t), სადაც S = ( x 1 , x 2 , …, x n ) არის დადებითი მთელი რიცხვების სიმრავლე, ხოლო t არის დადებითი რიცხვი. საჭიროა S სიმრავლის ქვესიმრავლეთა შორის, რომელთა ჯამი არ აღემატება t-ს, ის, ვისი ჯამიც ყველაზე ახლოს არის t-თან.
მოდით | S | = n. ავღნიშნოთ (k, w) - პრობლემა, რომელშიც არის პირველი k რიცხვები S-დან და უნდა აკრიფოთ w ჯამი. ამრიგად, თავდაპირველი პრობლემა არის პრობლემა (n, t).
ამოცანის ამოსახსნელად ავაშენებთ ცხრილს T [n, t + 1], რომლის T [i, j] უჯრაში დავწერთ ამოცანის ოპტიმალურ ამოხსნას (i, j).
პირველი სვეტი შეივსება ნულებით. პირველი სტრიქონი ჯერ ნულებით შევავსოთ და უჯრედიდან (1, x 1) დავიწყოთ x 1 რიცხვებით. უჯრას T [i, j] (i, j > 1) შევავსებთ წესის მიხედვით:
- თუ j − x i > 0, მაშინ y:= T [i − 1, j − x i ], წინააღმდეგ შემთხვევაში y:= 0;
- T [i, j] := max(T [i − 1, j], y + x i)
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 3 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| 5 | 0 | 0 | 0 | 3 | 3 | 5 | 5 | 5 | 8 | 8 | 8 | 8 | 8 | 8 |
| 7 | 0 | 0 | 0 | 3 | 3 | 5 | 5 | 7 | 8 | 8 | 10 | 10 | 12 | 12 |
| 9 | 0 | 0 | 0 | 3 | 3 | 5 | 5 | 7 | 8 | 9 | 10 | 10 | 12 | 12 |
| 11 | 0 | 0 | 0 | 3 | 3 | 5 | 5 | 7 | 8 | 9 | 10 | 11 | 12 | 12 |
S = (3, 5, 7, 9, 11) t = 13;
ცხრილი ასე გამოიყურება. პასუხი: არ არსებობს 13 წონით ქვეჯგუფი, ქვემოდან ყველაზე ახლოს არის 12.
პირობა (2) ამბობს, რომ ოპტიმალური ჯამის მიღწევა შესაძლებელია x i გამოყენების გარეშე (T [i − 1, j ]), ან თუ x i შედის ჯამში (y + x i). ამ შემთხვევაში ის უნდა დაემატოს ამოცანის ამოხსნას (i − 1, j − x i), რომელიც ინახება y ცვლადში (1) მდგომარეობაში. მიღებული ცხრილიდან შეგიძლიათ გაიგოთ ოპტიმალური თანხის შემადგენლობა.
ამ ალგორითმის სირთულე არის O(n t) ოპერაციები. ამრიგად, თუ t დიდია, შესაძლებელი იქნება ყველა რიცხვის გაყოფა, მაგალითად, 10-ზე, მრგვალად და მიახლოებითი ალგორითმის მიღება.
მაგალითი 2. ქვესიმრავლეების ჯამის პრობლემა („სიის“ ალგორითმი)
მოდით L იყოს რიცხვების სიმრავლე, ხოლო x არის გარკვეული რიცხვი, შემდეგ L + x-ით აღვნიშნავთ რიცხვთა სიმრავლეს, რომელიც მიიღება, თუ x დაემატება L-ის ყველა ელემენტს. ეს ალგორითმი ასევე იყენებს იმ ფაქტს, რომ x i შეიძლება იყოს ან არ იყოს ჯამში, ანუ:
L i = L i −1 ∪ (L i −1 + x i)
სიიდან t-ზე დიდი ელემენტების ამოღებით, ჩვენ ვიღებთ L n - დალაგებულ სიას S ქვეჯგუფების ყველა შესაძლო ჯამისა, რომელიც გვაკმაყოფილებს. რჩება მაქსიმალური (ბოლო) ელემენტის აღება პრობლემის გადაწყვეტის მისაღებად. სია L n შეიძლება შეიცავდეს 2 n ელემენტამდე (ანუ ალგორითმი ექსპონენციალურია), თუმცა, ვინაიდან ყველა ელემენტი განსხვავებულია, არ შეიძლება იყოს თ-ზე მეტი. არსებობს ფსევდოპოლინომიულობა.
სიახლოვის სქემები
სავარაუდო ალგორითმებთან დაკავშირებით ჩნდება კითხვა: შესაძლებელია თუ არა მიახლოებითი ალგორითმის თანდათანობით გართულება და უფრო ზუსტი ამოხსნის მიღება? არსებობს ასეთი ალგორითმები და, როგორც უკვე ვთქვით, მათ დაახლოების სქემები ეწოდება. უნდა აღინიშნოს, რომ ეს ძალიან იშვიათია: ჩვეულებრივ, რთული პრობლემისთვის არის ცნობილი მარტივი ალგორითმი ცუდი სიზუსტით, უხეში ძალით მეორე ბოლოში და არაფერი შუაში.
განვიხილავთ ორ მიახლოების სქემას ქვესიმრავლის ჯამის ამოცანისთვის. ერთი მათგანი მოდის „სიის“ ალგორითმიდან, მეორეს კი ჯონსონის ალგორითმი ჰქვია.
მაგალითი 1. ქვესიმრავლეების ჯამის ამოცანა (სრულიად პოლინომიური მიახლოების სქემა)
ასეთი სქემა მიიღება „სიის“ ალგორითმიდან, თუ სია L ინახება შემცირებულ ფორმაში. სიას L′ ეწოდება L სიის δ-შემცირება, თუ L′ არის L და-ს ნაწილი
∀ y ∈ L ∃ ∈ z ∈ L ′: z ≤ y , (y − z) ⁄ y ≤ δ
მაგალითად δ = 0.1 და L =<10, 11, 12, 15, 20, 21, 22, 23, 24, 29>სია L ′ =<10, 12, 15, 20, 23, 29>არის δ -შეკუმშვა. m ელემენტების მოწესრიგებული სიის შემცირება მოითხოვს Θ(m) ოპერაციებს. ამრიგად, შეიძლება დადასტურდეს, რომ „სიის“ ალგორითმი, რომელიც სრული სიის ნაცვლად ინახავს შემოკლებულ სიას, არის სრულად პოლინომიური მიახლოების სქემა.
მაგალითი 2. ქვესიმრავლეების ჯამის ამოცანა (ჯონსონის ალგორითმი)
ალგორითმი, გარდა S სიმრავლისა და t რიცხვისა, შესაყვანად იღებს მთელი რიცხვის პარამეტრს m > 2. მოდით, i-ე რიცხვს ვუწოდოთ დიდი, თუ x i > t ⁄(m +1). ალგორითმის აღწერა:
- ჩამოთვალეთ დიდი რიცხვების ყველა ქვესიმრავლე და იპოვეთ დიდი რიცხვების სიმრავლე ჯამით t ′: t′< t , Δ = t − t ′ min
- თუ Δ = 0, ალგორითმი დასრულებულია.
- დაალაგეთ ყველა მცირე რიცხვი კლებადობით. თუ შემდეგი x i ≤ Δ, მაშინ t ′:= t ′ + x i, Δ := Δ − x i;
- როდესაც დასრულებულია მცირე რიცხვების ძიება, დააბრუნეთ t ′ როგორც პასუხი.
ვთქვათ k არის დიდი რიცხვების რაოდენობა. მაშინ შეგვიძლია დავამტკიცოთ, რომ ჩვენთვის შესაფერისი ქვესიმრავლეების რაოდენობა დიდი რიცხვებიდან არის O (k m) ≤ O (n m). ამრიგად, ძიებას აქვს პოლინომიური სირთულე, რომელიც იზრდება m-ით. უფრო მეტიც, შეიძლება აჩვენოს, რომ:
T ′⁄ t ≥ 1 − 1 ⁄ (m + 1) 1 − 1 ⁄ (m + 1) ≤ t ′⁄ t* ≤ 1
ანუ ფარდობითი შეცდომა ε = 1⁄ (m +1). ამრიგად, ეს მიახლოების სქემა არის მრავალწევრი, მაგრამ არა მთლიანად მრავალწევრი.
შემთხვევითი ძიების მეთოდი
როგორც წესი, გადაწყვეტის არჩევანი შეიძლება წარმოდგენილი იყოს როგორც არჩევანის თანმიმდევრობა. თუ ამ არჩევანს აკეთებთ რაიმე შემთხვევითი მექანიზმის გამოყენებით, მაშინ გამოსავალი ძალიან სწრაფად მოიძებნება, ასე რომ თქვენ შეგიძლიათ ბევრჯერ იპოვოთ გამოსავალი და დაიმახსოვროთ „ჩანაწერი“, ანუ საუკეთესო გამოსავალი, რომელიც შეგხვდათ. ეს გულუბრყვილო მიდგომა მნიშვნელოვნად გაუმჯობესებულია, როდესაც შესაძლებელია შემთხვევითი მექანიზმის გარკვეული არჩევანის პერსპექტივის გათვალისწინება, ანუ შემთხვევითი ძიების გაერთიანება ევრისტიკულ მეთოდთან და ლოკალური ძიების მეთოდთან. ასეთი მეთოდები გამოიყენება, მაგალითად, აეროფლოტის განრიგის შექმნისას.
ძალიან მინდა მეტი ინფორმაციაშემთხვევითი ძიების მეთოდის შესახებ და იხილეთ კონკრეტული მაგალითინებისმიერი პრობლემის გადაჭრა ამ მეთოდით..........
გთხოვთ. შეკითხვისთვის "შემთხვევითი ძიების მეთოდი" Google საძიებო სისტემააცხადებს 300000-ზე მეტ ბმულს. ეს ინფორმაცია საკმარისი უნდა იყოს.........
გმადლობთ სტატიისთვის, მე გავარკვიე პატარას ალგორითმი. საიტის დამახსოვრება მინდოდა და გამიკვირდა ჩემი მშობლიური უნივერსიტეტის დომენი :)
ზემოთ სწორად იყო აღნიშნული გადასვლების აკრძალვის შესახებ - აქ მინდა ვნახო ახსნა.
გმადლობთ ლიტლის ალგორითმის ნათელი ახსნისთვის. მაგრამ არ არის გათვალისწინებული მნიშვნელოვანი დეტალი: შემდეგი კიდის არჩევისას უნდა გაითვალისწინოთ, რომ კიდეების სიმრავლიდან ბილიკი თანმიმდევრულად მოიცავს ყველა წერტილს. მას შემდეგ, რაც ჩვენ ვამატებთ კიდეებს შემთხვევითი თანმიმდევრობით, ჩვენ უნდა დავაკვირდეთ მიკროციკლების არსებობას (მაგალითად, თუ თქვენ აირჩიეთ ზღვარი 1,0 - ეს ნიშნავს, რომ 0, 1 აღარ შეიძლება იყოს არჩეული, ან თუ აირჩიეთ 0,1 და 1, 2 - მაშინ თქვენ არ შეგიძლიათ აირჩიოთ 2,0 და 2,1 და ა.შ.), რომლის თვალყურის დევნება არც ისე ადვილია. მე განვახორციელე ალგორითმი C#-ში და ვადევნე თვალი ციკლებს გამოყენებით სპეციალური კლასი, რომელიც შეიცავდა მიკროციკლების კომპლექტს და წაშლილია აკრძალული კიდეები, როდესაც მას ახალი დაემატა და აღადგინა კიდეები, როდესაც კიდეები ამოიღეს.
ალგორითმის განხორციელება პრაქტიკაში ძალიან რთული აღმოჩნდა და მისი გამართვა უბრალოდ ჯოჯოხეთი იყო. კოდი აიღო 512 სტრიქონი. ამუშავებს 20 ქულას 0.1 - 10 წამში - ხანგრძლივობა დიდად არის დამოკიდებული შეყვანის კომპლექტზე. დიდი რაოდენობითიგი არ წყვეტს მას ადეკვატურ დროში. ყველაზე მარტივი საძიებო სისტემა, რაც მე მაქვს, პოულობს გამოსავალს 13 წვეროზე 1 წამში.
თუ გჭირდებათ ალგორითმის დანერგვა C#-ში, მოგვწერეთ ელექტრონული ფოსტით [ელფოსტა დაცულია].
მოგზაური გამყიდველის პრობლემის გადაჭრა განშტოებისა და შეკრული მეთოდის გამოყენებით (ლიტლის ალგორითმი)
http://igorvn.ucoz.ru/load/kursovye/kommivojazher/2-1-0-15
ლიტლის მეთოდი მუშაობს მხოლოდ მცირე რაოდენობაზე, ასე რომ, ყველა მაგალითში არ არის 10-ზე მეტი მათგანი, დაწყებული 15 ქულით, ის იძლევა მიახლოებით შედეგს მინიმუმზე 1-2% -ით და ეს თანდაყოლილია. ყოველი სვლის (შემცირების) განსაზღვრის თანმიმდევრობა, გაუგებარია, რის საფუძველზე ხდება ეს, ბოლოს და ბოლოს, ფორმალურად ვიღებთ სხვა მატრიცას.
გამოგიგზავნით "რუსულ მეთოდს" ჩემი კომენტარის დასადასტურებლად.
Გმადლობთ. ჩვენ ეჭვი არ გვეპარება თქვენს მთლიანობაში და კომპეტენციაში. მაგრამ ჩვენ არ ვატარებთ *.doc ფაილებს. თუ თქვენ განათავსებთ მის შიგთავსს საჯარო ადგილას მუდმივი შენახვის სტატუსით და ჩაამატებთ ბმულს თქვენი ახალი კომენტარის ტექსტში, ჩვენ გამოვაქვეყნებთ მას ყველასთვის სანახავად.
ვისაც სურს გაიგოს ლიტლის მეთოდის ყველა თეორიული შეცდომის შესახებ, გთხოვთ, ჯერ თავად აუხსნათ, რა არის შემცირება და რა მათემატიკური საფუძველზე ხორციელდება. გარდა ამისა, შემიძლია სრულიად უფასოდ გამოგიგზავნოთ ჩემს მიერ შემუშავებული რუსული მეთოდი. Ჩემი ელ - ფოსტა: [ელფოსტა დაცულია]
გამარჯობა, ჰაბრ! ხვდება სხვადასხვა ალგორითმებიჰამილტონის ციკლის ყველაზე მცირე ღირებულების მოსაძებნად, მე წავაწყდი პუბლიკაციას, რომელიც გთავაზობთ საკუთარ ვერსიას. ცდის შემდეგ მივიღე არასწორი პასუხი:
ინტერნეტში შემდგომმა ძიებამ არ მოიტანა მოსალოდნელი შედეგი: არც თეორიული აღწერა, რომელიც რთული იყო არამათემატიკოსებისთვის, ან გასაგები, მაგრამ შეცდომებით.
ჭრილის ქვემოთ ნახავთ შესწორებულ ალგორითმს და ონლაინ კალკულატორს.
თავად მეთოდი, რომელიც გამოქვეყნდა Little, Murthy, Sweeney, Carell-ის მიერ 1963 წელს, გამოიყენება მრავალი NP-სრული პრობლემისთვის და არის ძალიან თეორიული მასალა, რომელიც კარგი ცოდნის გარეშეა. ინგლისურადდა მათემატიკა არ შეიძლება დაუყოვნებლივ იქნას გამოყენებული ჩვენი მოგზაური გამყიდველის პრობლემაზე.
მოკლედ მეთოდის შესახებ - ეს არის ყველა შესაძლო ვარიანტის სრული ძიება აშკარად არაოპტიმალური გადაწყვეტილებების აღმოფხვრით.
შესწორებული ალგორითმი ჭეშმარიტად მინიმალური მარშრუტის მოსაძებნად
ალგორითმი შედგება ორი ეტაპისგან:
პირველი ეტაპი
ხარჯების მატრიცის შემცირება და მარშრუტის ღირებულების ქვედა შეფასების გამოთვლა r.
1. გამოთვალეთ უმცირესი ელემენტი თითოეულ მწკრივში (ჩასმული მუდმივი მწკრივისთვის)2. გადავიდეთ ახალი მატრიცახარჯები თითოეული მწკრივიდან მისი შემცირების მუდმივის გამოკლებით
3. გამოთვალეთ უმცირესი ელემენტი თითოეულ სვეტში (იძულების მუდმივი სვეტისთვის)
4. ჩვენ გადავდივართ ხარჯების ახალ მატრიცაზე, გამოვაკლებთ მის შემცირების მუდმივას თითოეულ სვეტს.
შედეგად, ჩვენ გვაქვს ხარჯების მატრიცა, რომელშიც თითოეულ სტრიქონს და თითოეულ სვეტს აქვს მინიმუმ ერთი ნულოვანი ელემენტი.
5. გამოთვალეთ საზღვარი ამ სცენაზეროგორც სვეტებისა და მწკრივების შემცირების მუდმივების ჯამი (ეს ზღვარი იქნება ღირებულება, რომლის ქვემოთ შეუძლებელია საჭირო მარშრუტის აგება)
მეორე (მთავარი) ეტაპი
1. გამოუყენებლობის ჯარიმის გამოთვლა მოცემული ღირებულების მატრიცის ყოველ ნულოვან ელემენტზე.მატრიცაში (h,k) ინდექსის მქონე ელემენტის გამოუყენებლობის ჯარიმა ნიშნავს, რომ ეს ზღვარი არ შედის ჩვენს მარშრუტში, რაც ნიშნავს, რომ მინიმალური ღირებულება ამ ზღვრის „გამოუყენებლობის“ უდრის მინიმალური ელემენტების ჯამს. რიგი h და სვეტი k.
ა) ჩვენ ვეძებთ ყველა ნულოვანი ელემენტს მოცემულ მატრიცაში
ბ) თითოეულ მათგანს გამოვთვალოთ მისი ჯარიმა გამოუყენებლობისთვის.
გ) აირჩიეთ ელემენტი, რომელიც შეესაბამება მაქსიმალურ ჯარიმას (ნებისმიერი, თუ რამდენიმე მათგანია)
2. ახლა ჩვენ ვყოფთ ჩვენს კომპლექტს S ნაკრებებად - ისეთებს, რომლებიც შეიცავს ზღვარს მაქსიმალური ჯარიმის (S w) და ისინი, რომლებიც არ შეიცავს ამ ზღვარს (S w/o).
3. თითოეულ ამ კომპლექტში შემავალი მარშრუტების ხარჯთაღრიცხვის გაანგარიშება.
ა) S w/o სიმრავლისთვის ყველაფერი მარტივია: ვინაიდან ჩვენ არ ვიღებთ შესაბამის ზღვარს მაქსიმალური ჯარიმით (h,k), მაშინ მისი ხარჯთაღრიცხვა უდრის კომპლექტის S + ჯარიმის ხარჯთაღრიცხვას. კიდეების გამოუყენებლობისთვის (h,k)
ბ) S w სიმრავლისთვის დანახარჯების გაანგარიშებისას მხედველობაში მივიღებთ, რომ რაკი ზღვარი (h,k) შედის მარშრუტში, ეს ნიშნავს, რომ ზღვარი (k,h) ვერ შედის მარშრუტში, შესაბამისად დანახარჯების მატრიცას ვწერთ c(k,h) =უსასრულობა და რადგან h წერტილიდან „უკვე დავრჩით“ და k წერტილიდან „უკვე ჩამოვედით“, მაშინ არც ერთი კიდე არ ტოვებს h და არც ერთი კიდე არ მოდის. k-ზე აღარ შეიძლება გამოყენებულ იქნას, ამიტომ ჩვენ ვკვეთთ ხარჯების მატრიცას, მწკრივს h და სვეტს k. ამის შემდეგ, ჩვენ ვამცირებთ მატრიცას, შემდეგ კი S w-ის ხარჯთაღრიცხვა უდრის S და r(h,k) ხარჯთაღრიცხვის ჯამს, სადაც r(h,k) არის შემცირების მუდმივების ჯამი შეცვლილი ხარჯების მატრიცა.
4. მდებარეობა ყველასგაუნაწილებელი ნაკრებიდან შეირჩევა ყველაზე დაბალი ქულის მქონე.
ჩვენ ვაგრძელებთ ამ გზას, სანამ ხარჯების მატრიცაში დარჩება ერთი გადაკვეთილი მწკრივი და ერთი გადაკვეთილი სვეტი.
მცირე ოპტიმიზაცია - ევრისტიკის დამატება
დიახ, მართლა, რატომ არ შემოვიღოთ ევრისტიკა? მართლაც, ტოტისა და შეკრული ალგორითმში ფაქტობრივად ვაშენებთ ხეს, რომლის კვანძებზეც გადავწყვიტეთ ავიღოთ კიდე (h,k) და ჩამოვკიდოთ ორი შვილი - Sw(h,k) და Sw/o( თ, კ). მაგრამ საუკეთესო ვარიანტიშემდეგი გამეორებისთვის ჩვენ ვირჩევთ მხოლოდ შეფასებით. ამიტომ ავირჩიოთ საუკეთესო არა მხოლოდ რეიტინგის, არამედ ხეში სიღრმის მიხედვით, რადგან... რაც უფრო ღრმაა შერჩეული ელემენტი, მით უფრო ახლოს არის ის დათვლის დასასრულთან. ამ გზით ჩვენ საბოლოოდ შეგვიძლია დაველოდოთ პასუხს.
ახლა, რეალურად, ამ პუბლიკაციაში შეცდომებზე
იყო მხოლოდ ერთი შეცდომა - თქვენ უნდა აირჩიოთ ნაკრების დაყოფა ყველა მინიმალური საზღვრით შესაძლო გზები, და არა ბოლო გაყოფის შედეგად მიღებული ორი შვილისგან.მტკიცებულება
დავუბრუნდეთ პოსტის დასაწყისში სურათს:
და აქ არის გამოსავალი შესწორებული ალგორითმით:
პასუხი: ბილიკი:3=>4=>2=>1=>5=>3 სიგრძე: 41
როგორც ხედავთ, ხსნარში 5:2 ზღვრის ჩართვა შეცდომა იქნება. ქ.ე.დ
გრაფიკი, რომელიც ადარებს განშტოებასა და შეკრულ მეთოდს და დახარჯულ დროს შემთხვევითი ცხრილისთვის 5x5-დან 10x10-მდე: 
მატრიცებისთვის დახარჯული მაქსიმალური და მინიმალური დროის გრაფიკი 5x5-დან 66x66-მდე. 
სცადეთ ერთად დეტალური გადაწყვეტაშეუძლია
განშტოებისა და შეკრული მეთოდი პირველად იქნა შემოთავაზებული 1960 წელს Land and Doig-ის ნაშრომში მთელი რიცხვების პრობლემასთან დაკავშირებით. ხაზოვანი პროგრამირება. თუმცა, ამ სამუშაოს მნიშვნელოვანი პირდაპირი გავლენა არ ჰქონია დისკრეტული პროგრამირების განვითარებაზე. ფაქტობრივად, ტოტისა და შეკრული მეთოდის „ხელახალი დაბადება“ დაკავშირებულია ლიტლის, მერთის, სუინისა და კარელის მუშაობასთან მოგზაური გამყიდველის პრობლემაზე; იმავე ნაშრომში პირველად იქნა შემოთავაზებული მეთოდის ახლა საყოველთაოდ მიღებული სახელწოდება „ტოტი და შეკრული მეთოდი“. ამ მომენტიდან ძალიან ჩანს დიდი რიცხვისამუშაოები, რომლებიც ეძღვნება ტოტისა და შეკვრის მეთოდს და მის სხვადასხვა მოდიფიკაციას. ასეთი დიდი წარმატება (და თუნდაც „კლასიკურად რთული“ მოგზაური გამყიდველის პრობლემასთან დაკავშირებით) აიხსნება იმით, რომ ლიტლი, მერთი, სვინი და კარელი პირველებმა მიიპყრეს ყურადღება ფილიალისა და შეკრული მეთოდის შესაძლებლობების სიგანზე. აღნიშნეს პრობლემის სპეციფიკის გამოყენების მნიშვნელობა და თავადაც წარმატებით ისარგებლეს ამ სპეციფიკით.
ამ თავის 1 ნაწილი ადგენს ზოგადი იდეაგანშტოების და შეკრული მეთოდი; § 2 -ში - Land and Doig ალგორითმი მთელი რიცხვითი წრფივი პროგრამირების ამოცანისთვის, § 3 - ლიტლის და სხვა ავტორების მეთოდი მოგზაური გამყიდველის პრობლემისთვის.
§ 1. ტოტისა და შეკრული მეთოდის იდეა
1.1. განვიხილოთ დისკრეტული პროგრამირების პრობლემა შემდეგი ზოგადი ფორმით.
მინიმიზაცია
იმის გათვალისწინებით, რომ
აქ G არის გარკვეული სასრული ნაკრები.
1.2. განშტოებისა და შეკრული მეთოდი ეფუძნება შემდეგ კონსტრუქციებს, რომლებიც ზოგიერთ შემთხვევაში შესაძლებელს ხდის ძიების ზომის საგრძნობლად შემცირებას.
I. ქვედა ზღვრის გამოთვლა (შეფასება).
ხშირად შესაძლებელია მისი პოვნა ქვედა ზღვარიობიექტური ფუნქციის (შეფასება) გეგმების სიმრავლეზე (ან მის რომელიმე ქვეჯგუფზე, ანუ ისეთ რიცხვზე, რომ
(შესაბამისად, ქვეჯგუფებად დაყოფა (განშტოება) ხდება. მეთოდის განხორციელება დაკავშირებულია გეგმების სიმრავლის თანდათანობით დაყოფასთან ქვესიმრავლეების ხედ (განშტოება). განშტოება ხდება შემდეგი მრავალსაფეხურიანი სქემის მიხედვით.
0 ნაბიჯი. არსებობს კომპლექტი, რომელიც გარკვეულწილად იყოფა სასრული რაოდენობის ქვეჯგუფებად. გარკვეული წესის მიხედვით (ქვემოთ მითითებული), მათ შორის ირჩევა სიმრავლე და იყოფა ქვეჯგუფების სასრულ რაოდენობად:
კომპლექტები, რომლებიც ჯერ არ იყო გაყოფილი
ხელახლა დანიშნა
ამ თანმიმდევრული დაყოფის პროცესის რამდენიმე ეტაპი სქემატურად არის გამოსახული ნახ. 10.1.1.
III. ქულების ხელახალი გაანგარიშება. თუ არის კომპლექტი, მაშინ ცხადია
მაშასადამე, ამოხსნის პროცესში გარკვეული ნაკრების ქვეჯგუფებად დაყოფა
კონკრეტულ სიტუაციებში ხშირად შესაძლებელია შეფასების გაუმჯობესება, ანუ გარკვეული მკაცრი უთანასწორობის მიღება მაინც
IV. გეგმების გაანგარიშება. ამისთვის კონკრეტული ამოცანებიშეიძლება დაზუსტდეს სხვადასხვა გზებიგეგმების პოვნა თანმიმდევრულად განშტოებულ ქვეჯგუფებში. ნებისმიერი ასეთი მეთოდი მნიშვნელოვნად არის დამოკიდებული პრობლემის სპეციფიკაზე.
V. ოპტიმალურობის ნიშანი. დაე
და გეგმა X ეკუთვნის ზოგიერთ ქვეჯგუფს, თუ გარდა ამისა,
შემდეგ X - ოპტიმალური გეგმაპრობლემები (1.1) - (1.2).
მტკიცებულება პირდაპირ გამომდინარეობს შეფასების განმარტებიდან.
როგორც წესი, ეს ფუნქცია გამოიყენება განშტოების ზოგიერთ ეტაპზე (ანუ, ფორმალურად რომ ვთქვათ, ზე; იხილეთ პუნქტი II).
VI. სავარაუდო ამოხსნის სიზუსტის შეფასება. დაე
თუ X არის თავდაპირველი პრობლემის გარკვეული გეგმა (ე.ი.), მაშინ
აქ დასტური დაუყოვნებლივ გამომდინარეობს შეფასების განმარტებიდან.
ცხადია, თუ განსხვავება მცირეა (ანუ არ აღემატება მოცემული ამოცანისთვის არჩეულ გარკვეულ რიცხვს), მაშინ X შეიძლება მივიღოთ მიახლოებითი ამონახსნით, როგორც მიახლოების სიზუსტის შეფასება.
1.3. მოდით გამოვყოთ განშტოების და შეკრული მეთოდის ფორმალური სქემა.
0 ნაბიჯი. ჩვენ ვიანგარიშებთ ქულას. თუ შესაძლებელია ისეთი გეგმის მოძებნა X რომ
მაშინ X არის ოპტიმალური გეგმა.
თუ ოპტიმალური გეგმა ვერ მოიძებნა, მაშინ რომელიმე მეთოდის გამოყენებით ჩვენ ვყოფთ კომპლექტს სასრული რაოდენობის ქვეჯგუფებად.
და გადადით საფეხურზე.
1 ნაბიჯი. გამოთვალეთ შეფასებები თუ შესაძლებელია X გეგმის პოვნა ისეთი, რომ ზოგიერთისთვის და
მაშინ X არის ოპტიმალური გეგმა.
თუ ოპტიმალური გეგმა ვერ მოიძებნა, მაშინ ჩვენ ვირჩევთ "ყველაზე პერსპექტიულ" კომპლექტს შემდგომი დანაყოფისთვის შემდეგი წესის მიხედვით:
ჩვენ ვყოფთ კომპლექტს რამდენიმე (ჩვეულებრივ განცალკევებულ) ქვეჯგუფად.