[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Razlika megju DP & Brute Force ?!  XML
Forum Index » C/C++
Author Message
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Moze li nekoj da mi objasni koja e razlikava megju DP i brute force ?
oti kolku shto gledam i DP gi pominuva site mozni resenija
no i Brute Force toa go pravi
despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

Perez wrote:Moze li nekoj da mi objasni koja e razlikava megju DP i brute force ?
oti kolku shto gledam i DP gi pominuva site mozni resenija
no i Brute Force toa go pravi


Динамичкото програмирање го пресметува решението на даден проблем врз основа на решенијата на помалите подпроблеми на кои може да се разложи тој проблем. Притоа, решенијата на подпроблемите ги чуваме (ова се нарекува мемоизација) така што не мораме да ги пресметуваме повторно. Ова е најголемата добивка која ни ја дава динамичкото програмирање. Но не може секој проблем да се сведе на динамичко програмирање, има проблеми кои не може толку лесно да се разложат на поедноставни подпроблеми така што би се исплатело да одиме со динамичко програмирање.

Исто така, не е точно дека со динамичко програмирање ги поминуваме сите можни решенија. Типичен пример: трговски патник (travelling salesman problem). Брут-форс решение би било да се испробаат сите можни патеки и да се одбере најдобрата, во време O(n!) пропорционално со бројот на градови. Од друга страна, решението со динамичко програмирање (O(n^2 * 2^n)), за секое множество поминати градови, за кои не не интересира по кој редослед биле поминати, и даден тековен град во кој се наоѓаме, го пресметува оптималното решение со кое ќе ги поминеме останатите градови. Со тоа драстично се намалува бројот на потребни решенија кои треба да се проверат.

This message was edited 1 time. Last update was at 13/11/2017 17:58:42

 
Forum Index » C/C++
Go to:   
Powered by JForum 2.1.8 © JForum Team