Დინამიური პროგრამირების ძირითადი პრინციპები

აირჩიოთ ოპტიმალური გამოსავალი, როდესაც ასრულებენ პროგრამირების ამოცანები ზოგჯერ საჭირო დასალაგებლად დიდი რაოდენობით მონაცემები კომბინაციები, რომელიც იტვირთება ხსოვნას პერსონალური კომპიუტერი. ასეთი მეთოდები მოიცავს, მაგალითად, პროგრამირების მეთოდი "გათიშე და იბატონე". ამ შემთხვევაში ალგორითმი უზრუნველყოფს გამოყოფის პრობლემა ცალკე პატარა subtasks. ეს მეთოდი გამოიყენება მხოლოდ იმ შემთხვევაში, თუ პატარა subtasks ორმხრივად დამოუკიდებელი. თავიდან აცილების მიზნით, ასრულებენ ზედმეტი მუშაობა, თუ ურთიერთდამოკიდებული sub-ამოცანები, იყენებს დინამიური პროგრამირების მეთოდი შემოთავაზებული ამერიკული R.Bellmanom 50.

მეთოდი

დინამიური პროგრამირების, რათა დადგინდეს, ოპტიმალური გამოსავალი n განზომილებიანი პრობლემა, გაზიარების მისი n ცალკე ეტაპად. თითოეული მათგანი არის sub-ამოცანაა მიმართებაში ერთი ცვლადი.

მთავარი უპირატესობა ამ მიდგომის შეიძლება ჩაითვალოს, რომ დეველოპერები ჩართული ერთ განზომილებიანი ოპტიმიზაციის პრობლემა Subtasks ნაცვლად n განზომილებიანი პრობლემა, და ჩვენი უპირველესი მიზანი აპირებს "bottom-up".

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

დინამიური პროგრამირების ამოცანა წყვეტს პრობლემას ოპტიმიზაცია. ავტორი ამ მეთოდი ჩამოაყალიბა R. Bellman ოპტიმალურობის პრინციპი: რაც არის საწყის მდგომარეობას თითოეული ნაბიჯები და გადაწყვეტა განსაზღვრულია ამ ნაბიჯს, ყველა შემდეგ აირჩიოს ოპტიმალური იმ სახელმწიფოს, რომელიც იღებს სისტემის დასასრულს ნაბიჯი.

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

სამშენებლო ამოცანა ალგორითმი

დინამიური პროგრამირება ალგორითმი მოიცავს სამშენებლო ასეთი ამოცანები, ამოცანა, ასე გაიყო ორ ან მეტი subtasks მისი გადაწყვეტა შედგება ოპტიმალური გამოსავალი ყველა subtasks, იგი მოიცავს. გარდა ამისა, აუცილებელია დაწერა რეციდივის მიზეზი, და გაანგარიშების ოპტიმალური პარამეტრი ღირებულებების ამოცანა, როგორც მთელი.

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

გამოყენების მეთოდი

დინამიური პროგრამირების გამოიყენება მაშინ, როცა არსებობს ორი დამახასიათებელი:

• ოპტიმალური subtasks;
• ყოფნა პრობლემა გადახურვის subproblems.

გადაჭრის ოპტიმიზაციის პრობლემა დინამიური პროგრამირების, თქვენ ჯერ უნდა აღწერს სტრუქტურა გადაწყვეტა. ამოცანა უნდა იყოს ოპტიმალური თუ გამოსავალი შედგება საუკეთესო გადაწყვეტილება მისი subtasks. ამ შემთხვევაში, ეს არის მიზანშეწონილი გამოყენება დინამიური პროგრამირების.

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

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