算法设计

divide and conquer

In section 2.3.1 we can saw how merge sort serves as an example of the divide-and conquer paradigm. Recalling that in divide-and-conquer, we solve a problem recursively, applying three step at each level of the recursion:

  • Divide the problem into a number of subproblems that are smaller instances of the same problem
  • Conquer the subproblems by solving them recurisvely. If the problem sizes are small enough, however,just solve the subproblems in a straightforward manner.
  • Combine the solutions to the subpoblems into the solution for the original problem

(1)对于一个规模为N 的问题,若该问题可以容易地解决,则直接解决,否则执行下面的步骤。
(2)将该问题分解成若干个规模较小的子问题,这些子问题互相独立,并且原问题形式相同。
(3)递归recursively地解子问题。
(4)然后,将各子问题的解合并得到原问题的解


example: merge sort

  1. 对于一个长数组的排序问题,其排序可以分为左半边、右半边的排序手段
  2. 这样独立分配的子任务最终排序为可以分为最小的两个元素
  3. 排序之后再合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from math import floor


def merge_sort(A, p, r):
if p < r:
q = floor((p + r) / 2)
merge_sort(A, p, q)
merge_sort(A, q + 1, r)
merge(A, p, q, r)
return A


def merge(A, p, q, r):
n1 = q - p + 1
n2 = r - q
L = []
R = []
ceiling = 10000
for i in range(0, n1):
L.append(A[p + i - 1])
for j in range(0, n2):
R.append(A[q + j])
L.append(ceiling)
R.append(ceiling)
i = 0
j = 0
for k in range(p - 1, r):
if L[i] <= R[j]:
A[k] = L[i]
i = i + 1
else:
A[k] = R[j]
j = j + 1
return A


print(merge_sort([1, 3, 4, 2, 3, 1], 1, 6))

Dymanic programming

dynamic programming, like the divide-and-conquer method ,solves problems by combineing the solutions to subproblems.(“programming in this context refers to a tabular method,not ato wirting computer code”). As we saw in cahpter 2 and 4, divide -and -conquer algorithm partition the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the orignal problem. In contrast, ddynamic programming applies when the subproblems overlap—that is, when subproblems share subsubproblems. In this context, a divide-and-conquer algotirhm does more work than necessary , reaped solving the common subsubproblems.

A dynamic-programming algorithm solves each subsubproblems juest once and then saves its answei in the table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with optimal value.

  • characterizethe structure of an optimal solution
  • Recursively defin ethe value of an opitmal solution
  • Compute the value of an optimal solution, typically in a bottom-up fashion.
  • Construst an optimal solution from computed information
  1. 确定dynamic programming的数组以及具体的下标定义
  2. 确定递推公式
  3. dynamic programming数组的初始化
  4. 具体举例来使得计算进行下去

Example: 三角形最小和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
triangle=[[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
DP=[]
DP.append(triangle[0])
if len(triangle)>=1:
for story in range(1, len(triangle)):
temp=[]
for i in range(0, len(triangle[story])):
if i==0:
temp.append(DP[story-1][0] + triangle[story][0])
elif i==(len(triangle[story]) - 1):
temp.append(DP[story-1][i-1] + triangle[story][i])
else:
temp.append(min(triangle[story][i] + DP[story - 1][i - 1], triangle[story][i] + DP[story - 1][i]))
DP.append(temp)
min(DP[-1])

Greedy programming

–remain to studying–

back tracking

–remain to studying–

branch and bound

–remain to studying–


算法设计
https://blog.tjdata.site/posts/95085cd8.html
作者
chenxia
发布于
2021年8月8日
许可协议