1. The Divide and Conquer Paradigm:
a) Divide into smaller sub-problems.
b) Conquer via recursive calls.
c) Combine solutions to sub-problems into one for the original problem
2. The definition of inversions counting problem:
Input : Array A containing the numbers 1, 2, 3, ... , n in some arbitrary order.
Output: The number of inversions = the number of pairs(i,j) of array indeices with i < j and A[i]>a[j]
Motivation: Numerical similarity measurement between two ranked lists.
3. Examples: (1, 3, 5, 2, 4, 6)
Inversions: (3, 2) , (5, 2) , (5, 4)
4. Divide and Conquer solution for inversions counting:
inversion (i,j) [wth i <j] :
left ---- if i, j <= n/2
right ---- if i, j > n/2
split ---- if i <= n/2 <j
Count ( arry A, length n)
if n = 1 return 0
else
x = Count(1st half of A, n/2)
y = Count(2nd half of A, n/2)
z = CountSplitInv( A , n )
return x + y + z
5. Key idea of CountSplitInv :
have recursive calls both count inversions and sort
Motivation: Merge sub-routine natually uncovers split inversions:
6. The split inversions involving an element y of the 2nd array C are precisely the numbers left in the 1st array B when y is copied to the output D.
Merge_and_CountSplitInv
-- while merging the two sorted sub-arrays, keep counting total number of split inversions.
-- When element of 2nd array C gets copied to output D, increment the total nunmber of conversions by the number of lements remaining in the 1st array B.
7. Naive Divide and Conquer solution for matrix multiplication:
( a b ) ( e f ) = ( ae + bg af + bh)
( c d ) ( g h ) = ( ce + dg cf + dh)
T(n) = 8T(n/2) + n^2 = O(n^3)
8. Strassen’s Algorithm
P1 = A(F-H), P2 = (A+B)H , P3 = (C+D)E, P4 = D(G-E), P5 = (A+D)(E+H), P6 = (B-D)(G+H), P7= (A-C)(E+F)
( a b ) ( e f ) = ( P5+P4-P2+P6 P1+P2)
( c d ) ( g h ) = ( P3+P4 P1+P5-P3-P7)
Totally 7 sub-problems.
9. The definition of Closest Pair problem:
Input: a Set P = { p1, p2, ..., pn} of n points in the Plane.
Output: a pair p*, q* of P and such that p*, q* are distinct and d(p*,q*) is minimum over any pair p,q of P ( d(p,q) is Euclidean distance of p and q)
10. Solution to 1-D version of Closest Pair:
a) sort the points ( O(n log n)
b) return closest pair of adjacent points (O(n))
11. Divide and Conquer solution to ClosestPair(P) :
a) Let Q = left half of P , R = right half of P
b) (p1, q1) = ClosestPair(Q)
c) (p2, q2) = ClosestPair(R)
d) s = min { d(p1, q1) , d(p2, q2) }
d) (p3, q3) = ClosestSplitPair(P , s)
e) return closest of (p1, q1) , (p2, q2) , (p3, q3)
12. Solution to ClosestSplitPair(P, s)
a) Let x0 = biggest x-coordinate in left of P.
b) Let Sy = points of P with x-coordinate in [x0-s , x0 + s], sorted by y-coordinate
c) Initialize best = m , bestPair = NULL
for i = 1 to |Sy|-1
for j = 1 to min {7, |Sy|-i}
Let p, q the ith and jth points of Sy
if d(p,q) < best
bestPair = (p, q) , best = d(p,q)
Idea: if p,q is a split pair with d(p,q) < s , then p and q are in Sy and at most 7 points apart
13. For any p=(x1, y1) and q=(x2, y2) with d(p,q) < s , draw s/2 X s/2 boxes with center x0 and bottom min{y1, y2}.
All points in Sy with y-coordinate between p and q , lie in one of the 8 boxes. Because |y2-y1|<s , so max{y1, y2} < s , so one point is at the bottom line and the other point is within bottom line plus s that is in one of the 8 boxes.
At most one point of Sy in each box. Because each box are either in left (Q) or in right (R) and the maxium distance of each box is s/2 * 2^1/2 < s , so if there are more than one points in the same box then the min{ d(ClosesetPair(P)) , d(ClosestPair(Q)) } should not be s.
相关推荐
斯坦福algorithm part1 Divide and Conquer, Sorting and Searching, and Randomized Algorithms python 版答案
分治法(Divide and Conquer)是计算机科学中一种重要的算法思想,它的核心理念在于将一个复杂的问题分解成若干个规模较小、相互独立、与原问题形式相同的子问题,然后分别解决这些子问题,最后将子问题的解组合起来...
### 分治算法详解 #### 一、概述 **分治算法**是一种强大的算法设计思想,在计算机科学领域占有举足轻重的地位。它基于一个简单但非常有效的策略:将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到...
divideAndConquer
### 分治法递归关系式的通用解法 #### 引言与背景 在计算机科学领域,算法分析是一项至关重要的工作,它不仅对于理论研究有着深远的意义,同时也为实际应用提供了强大的支持。根据研究方法的不同,算法分析可以...
在本例中,我们关注的是通过分治(Divide and Conquer)策略来解决LCS问题。 **分治策略** 分治是一种解决问题的有效方法,它将大问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题,然后递归地解决...
根据提供的文件标题、描述、标签以及部分内容,我们可以深入探讨基于Divide and Conquer策略的Sutherland-Hodgman算法在多边形裁剪中的应用。 ### 基于Divide and Conquer策略的Sutherland-Hodgman算法 #### 算法...
算法设计技巧与分析课件(英文版):ch6 Divide and Conquer.ppt
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两...
快速排序 快速排序(Quicksort)是一种常见的、高效的排序算法,它基于分治(Divide and Conquer)的思想
在演算法领域中,Divide and Conquer(分治算法)是一种非常重要的思想与策略,其核心在于将一个难以直接解决的大问题分割成多个易于处理的小问题,对这些小问题分别解决后再将结果组合起来,以达到最终解决问题的...
分而治之的算法分而治之的算法分而治之的算法分而治之的算法
二分查找,也称为折半查找,是一种在有序数组中查找特定元素的搜索算法,具有高效的时间复杂度。本文将深入探讨二分查找的基本概念、实现方式及其在不同场景下的应用,结合提供的代码文件,我们将分析`chessBoard....
该项目开发了新的新技术和算法,可以使用“树状图”的“分而治之”方法在各种任意形状和空间内快速划分和可视化非常大的层次结构。 相关出版物:...
归并排序(Merge Sort)是一种基于分治策略的高效排序算法,由计算机科学家John W. Backus于1945年提出。它的工作原理可以分为三个主要步骤:分解、解决和合并。 1. 分解:将原始数据序列分成两个相等(或接近相等...
在计算机科学中,分治(Divide and Conquer)是一种重要的算法设计策略,它将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这种策略在...
非常好的数据结构课程代码 包含全书实例代码 程序的输入输出 另外网上可以找到邓俊辉数据结构公开课的视频下载 菜鸟都能很容易理解的数据结构教程 让你明白很多思想 比如绪论介绍的:分而治之(divide and conquer)...
分治(Divide and Conquer)是一种重要的算法设计策略,它将一个复杂的问题分解成两个或更多的相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这种方法在处理大量数据和复杂...