• <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年6月>
            272829303112
            3456789
            10111213141516
            17181920212223
            24252627282930
            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)  編輯 收藏 引用
            亚洲一本综合久久| 亚洲综合伊人久久大杳蕉| 2021久久精品国产99国产精品| 久久久久久久97| 色婷婷狠狠久久综合五月| 欧美日韩久久中文字幕| 国产成人精品久久二区二区 | 久久久久久久91精品免费观看 | 办公室久久精品| 久久久久亚洲AV无码专区首JN| 精品国产VA久久久久久久冰| 国产视频久久| 久久发布国产伦子伦精品| 久久婷婷色综合一区二区| 久久美女人爽女人爽| 久久久久女教师免费一区| 久久成人国产精品| 精品国产乱码久久久久久呢| 国内精品久久久久久中文字幕| 国色天香久久久久久久小说| 久久久这里有精品中文字幕| 久久久青草青青亚洲国产免观| 久久夜色精品国产网站| 国产欧美久久久精品影院| 精品久久久无码中文字幕| 久久精品国产免费一区| 国产V综合V亚洲欧美久久| 国产成年无码久久久免费| 香蕉99久久国产综合精品宅男自 | 26uuu久久五月天| 久久精品9988| 中文字幕一区二区三区久久网站| 久久w5ww成w人免费| 久久不见久久见免费视频7| 久久久久亚洲AV无码网站| 欧美噜噜久久久XXX| 久久婷婷成人综合色综合| 久久亚洲精品人成综合网| 久久精品国产亚洲AV电影| 国产精品青草久久久久婷婷 | 狠狠色婷婷综合天天久久丁香|