• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            隨筆 - 42  文章 - 3  trackbacks - 0
            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            常用鏈接

            留言簿(2)

            隨筆檔案

            文章檔案

            網(wǎng)頁收藏

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜


            Dynamic programming is similar to divide-and-conquer, it divide the original problem into small part, but they have different directions, Dynamic programming is bottom-up, while divide-and-conquer is a top-down approach. In this approach, we solve the small instance and store the result in a table, when we need the result, we just search in the table, and thus save large amount of time to re-calculation.

            The steps in the development of a dynamic programming algorithm are as follows:
            1. Establish a recursive property that gives the solution to an instance of the problem.

            2. Solve an instance of the problem in a bottom-up fashion by solving smaller instances first.

            A famous applications of dynamic programming is Floyd's Algorithm for Shortest Paths.

            Using dynamic programming, we create a cubic-time algorithm for the Shortest Paths problem. First we develop an algorithm that determines only the lengths of the shortest paths. After that we modify it to produce shortest paths as well. We represent a weighted graph containing n vertices by an array W where

            Image from book

            The array D in Figure 3.3 contains the lengths of the shortest paths in the graph. For example, D[3][5] is 7 because 7 is the length of a shortest path from v3 to v5. If we can develop a way to calculate the values in D from those in W, we will have an algorithm for the Shortest Paths problem. We accomplish this by creating a sequence of n + 1 arrays D(k), where 0 k n and where

            Image from book
            Figure 3.3: W represents the graph in Figure 3.2 and D contains the lengths of the shortest paths. Our algorithm for the Shortest Paths problem computes the values in D from those in W.
            • D(k)[i][j] = length of a shortest path from vi to vj using only vertices in the set {v1, v2, , vk} as intermediate vertices.

            Therefore, to determine D from W we need only find a way to obtain D(n) from D(0). The steps for using dynamic programming to accomplish this are as follows:

            1. Establish a recursive property (process) with which we can compute D(k) from D(k-1).

            2. Solve an instance of the problem in a bottom-up fashion by repeating the process (established in Step 1) for k = 1 to n. This creates the sequence

            Dynamic programming algorithm provides a solution for an optimization problem, and the steps in the development of such an algorithm are as follows:

            1. Establish a recursive property that gives the optimal solution to an instance of the problem.

            2. Compute the value of an optimal solution in a bottom-up fashion.

            3. Construct an optimal solution in a bottom-up fashion.

            Steps 2 and 3 are ordinarily accomplished at about the same point in the algorithm.

            The principle of optimality is said to apply in a problem if an optimal solution to an instance of a problem always contains optimal solutions to all substances.

            posted on 2012-03-27 18:48 鷹擊長空 閱讀(184) 評論(0)  編輯 收藏 引用

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


            欧美日韩精品久久久免费观看 | 久久人人爽人人人人爽AV| segui久久国产精品| 亚洲国产成人久久精品99| 一本色道久久HEZYO无码| 国产精品一久久香蕉国产线看| 久久777国产线看观看精品| 久久久中文字幕日本| 国产精品免费看久久久| 久久93精品国产91久久综合| 久久人人爽人人爽人人AV东京热| 亚洲成人精品久久| 漂亮人妻被黑人久久精品| 亚洲嫩草影院久久精品| 性高湖久久久久久久久| 色婷婷综合久久久久中文字幕| 久久精品aⅴ无码中文字字幕不卡| 欧美国产精品久久高清| 欧美一区二区精品久久| 久久人人爽人人爽人人片AV不| 久久久这里有精品中文字幕| 久久久精品午夜免费不卡| 亚洲av成人无码久久精品| 91麻豆国产精品91久久久| 久久综合成人网| 久久精品国产一区二区| 色综合久久88色综合天天 | 久久久国产打桩机| 久久一本综合| 久久成人国产精品一区二区| 国产精品欧美亚洲韩国日本久久| 丰满少妇人妻久久久久久| 久久精品国产99久久无毒不卡| 一本久久a久久精品vr综合| 久久久久se色偷偷亚洲精品av| 色99久久久久高潮综合影院| 亚洲AV伊人久久青青草原| 亚洲欧美日韩精品久久亚洲区 | 久久免费视频网站| 91精品国产高清久久久久久国产嫩草| 亚洲日韩中文无码久久|