• <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
            <2012年3月>
            26272829123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            常用鏈接

            留言簿(2)

            隨筆檔案

            文章檔案

            網頁收藏

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜


            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)  編輯 收藏 引用
            欧美噜噜久久久XXX| 精品无码人妻久久久久久| 久久久久久久亚洲Av无码| 久久久久亚洲AV无码网站| 午夜不卡888久久| 一本一道久久综合狠狠老| 狠狠综合久久综合中文88| 无码久久精品国产亚洲Av影片 | 91精品国产高清91久久久久久 | 久久人妻无码中文字幕| 亚洲国产精品一区二区久久| 色青青草原桃花久久综合| 国产精品免费久久| av午夜福利一片免费看久久| 国产成人精品久久| 亚洲欧美久久久久9999| 久久久精品久久久久久| 青青草原1769久久免费播放| 国产成人无码精品久久久性色 | 91精品国产91久久| 久久久久久国产精品免费无码 | 青青青青久久精品国产| 久久精品人人做人人爽电影蜜月| 亚洲精品乱码久久久久久不卡| 99久久国产亚洲高清观看2024 | 精品国产99久久久久久麻豆| 久久久久无码国产精品不卡| 久久久中文字幕| 一级做a爰片久久毛片人呢| 999久久久免费精品国产| 久久国产热精品波多野结衣AV| 99久久精品免费看国产一区二区三区 | 国产成人久久777777| 97超级碰碰碰碰久久久久| 青青青青久久精品国产h| 99久久精品国产毛片| 国产福利电影一区二区三区久久老子无码午夜伦不 | 亚洲国产日韩综合久久精品| 亚洲欧美日韩精品久久亚洲区 | 91精品国产91久久久久久青草| 国产精品美女久久久免费|