Geek_Ling

摘要： 動(dòng)態(tài)規(guī)劃博大精深，想完全掌握是很難的，不過我們可以從一些簡單的例子之中去體會(huì)她的奧妙。不說廢話、先來一個(gè)簡單的例子吧：longest path in DAGProblem: Given a weighted directed acyclic graph G=(V, E), an vertex v, where each edge is assigned an integer weight, find a longest path in graph G問題描述：給一個(gè)帶權(quán)有向無環(huán)圖G=（V，E），找出這個(gè)圖里的最長路徑。說實(shí)話初學(xué)者直接給出這個(gè)圖會(huì)看蒙的、再看看問題，不知道從何下手。好了，對(duì)上圖 閱讀全文

摘要： 之前也在看算法相關(guān)的書、在被稱為黑書的《算法導(dǎo)論》里看過關(guān)于動(dòng)態(tài)規(guī)劃的講解只是當(dāng)時(shí)研究不深、最近突來興趣對(duì)動(dòng)態(tài)規(guī)劃做了個(gè)小的總結(jié)、所以就分享下不足之處多多指正、先對(duì)動(dòng)態(tài)規(guī)劃做一個(gè)簡單的介紹吧：動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。動(dòng)態(tài)規(guī)劃是信息學(xué)競賽中選手 閱讀全文