Wenn ich ein Problem mit der optimalen Substruktur habe und keine Subproblem-Subsubprobleme, dann kann ich einen Divide and Conquer-Algorithmus verwenden, um es zu lösen?
Aber wenn das Subproblem subsubproblems (überlappende Subprobleme) teilt, kann ich dynamische Programmierung verwenden, um das Problem zu lösen?
Stimmt das?
Und wie ähneln gierige Algorithmen der dynamischen Programmierung?
Wenn ich ein Problem mit optimal habe Substruktur und keine Subproblem-Anteile subsubproblems dann kann ich eine divide verwenden und erobern Algorithmus, um es zu lösen?
Ja, solange Sie für jedes Subproblem einen optimalen Algorithmus finden können.
Aber wenn das Teilproblem sich teilt subsubproblems (überlappend Subprobleme) dann kann ich dynamisch verwenden Programmierung, um das Problem zu lösen?
Stimmt das?
Ja. Dynamische Programmierung ist im Grunde ein Spezialfall der Familie von Divide & amp; Conquer-Algorithmen, bei denen alle Teilprobleme gleich sind.
Und wie sind gierige Algorithmen ähnlich? zur dynamischen Programmierung?
Sie sind anders.
Dynamische Programmierung bietet Ihnen die optimale Lösung.
Ein Greedy-Algorithmus liefert normalerweise eine gute / faire Lösung in kurzer Zeit, aber er garantiert nicht, das Optimum zu erreichen.
Es ist , sagen wir , ähnlich, weil es normalerweise die Lösungskonstruktion in mehrere Stufen unterteilt, in denen es lokal optimale Entscheidungen trifft. Aber wenn Stufen keine optimalen Substrukturen des ursprünglichen Problems sind, führt das normalerweise nicht zur besten Lösung.
BEARBEITEN:
Wie von @rrenaud aufgezeigt, gibt es einige gierige Algorithmen, die sich als optimal erwiesen haben (z. B. Dijkstra, Kruskal, Prim usw.).
Um richtiger zu sein, der Hauptunterschied zwischen gieriger und dynamischer Programmierung besteht darin, dass der erstere nicht erschöpfend auf den Raum der Lösungen eingeht, während letzterer ist
In der Tat sind gierige Algorithmen auf diesem Raum kurzsichtig, und jede Wahl, die während des Lösungsbaus getroffen wird, wird nie überdacht.
Dynamisches Programm verwendet einen Bottom-up-Ansatz, speichert die vorherige Lösung und verweist darauf, so dass wir eine optimale Lösung unter allen verfügbaren Lösungen finden können, während der gierige Ansatz den Top-Down-Ansatz verwendet, so dass es eine optimale Lösung von lokal verfügbare Lösung, wird nicht die vorherige Ebene Lösungen nehmen, die zu der weniger optimierten Lösung führt. Dynamisch = von unten nach oben, optimale Lösung Gierig = von oben nach unten, weniger optimal, weniger zeitaufwendig
gieriger Ansatz funktioniert in Top-Down-Mode, aber dynamisch arbeitet in Bottom-up-Mode. Der gierige Ansatz kann eine Lösung liefern, die nicht optimal ist, sie kann suboptimal sein (fast optimal) Wenn wir einen dynamischen Ansatz verwenden, müssen wir auch alle vorherigen Lösungen beibehalten aber in gierig nehmen wir die beste Wahl in jedem Moment ohne Rücksicht auf vorheriges hier ist der Unterschied ... Deshalb können wir eine Lösung finden, die nicht optimal ist.
Siehe den Link Ссылка
Tags und Links algorithm
