动态规划加速原理之四边形不等式


http://blog.csdn.net/find_my_dream/article/details/4931222
http://blog.csdn.net/shiwei408/article/details/8791011
在动态规划的转移方程中,常见这样一种转移方程:
四边形不等式优化动态规划原理:
1.当决策代价函数w[i][j]满足w[i][j]+w[i’][j’]<=w[I;][j]+w[i][j’](i<=i’<=j<=j’),w满足四边形不等式.当函数w[i][j]满足w[i’][j]<=w[i][j’] i<=i’<=j<=j’),w关于区间包含关系单调.
2.如果状态转移方程m且决策代价w满足四边形不等式的单调函数(可以推导出m亦为满足四边形不等式的单调函数),则可利用四边形不等式推出最优决策s的单调函数性,从而减少每个状态的状态数,将算法的时间复杂度由原来的O(n^3)降低为O(n^2).方法是通过记录子区间的最优决策来减少当前的决策量.:
s[i][j]=max{k | ma[i][j] = m[i][k-1] + m[k][j] + w[i][j]}
由于决策s具有单调性,因此状态转移方程可修改为:
 
证明过程: (转载)
m[i,j]表示动态规划的状态量。
m[i,j]有类似如下的状态转移方程:
m[i,j]=opt{m[i,k]+m[k,j]}(ikj)
如果对于任意的abcd,有m[a,c]+m[b,d]m[a,d]+m[b,c],那么m[i,j]满足四边形不等式。
以上是适用这种优化方法的必要条件
对于一道具体的题目,我们首先要证明它满足这个条件,一般来说用数学归纳法证明,根据题目的不同而不同。
通常的动态规划的复杂度是O(n3),我们可以优化到O(n2)
s[i,j]m[i,j]的决策量,即m[i,j]=m[i,s[i,j]]+m[s[i,j]+j]
我们可以证明,s[i,j-1]s[i,j]s[i+1,j]  (证明过程见下)
那么改变状态转移方程为:
m[i,j]=opt{m[i,k]+m[k,j]}      (s[i,j-1]ks[i+1,j])
复杂度分析:不难看出,复杂度决定于s的值,以求m[i,i+L]为例,
(s[2,L+1]-s[1,L])+(s[3,L+2]-s[2,L+1])…+(s[n-L+1,n]-s[n-L,n-1])=s[n-L+1,n]-s[1,L]n
所以总复杂度是O(n2)
s[i,j-1]s[i,j]s[i+1,j]的证明:
mk[i,j]=m[i,k]+m[k,j]s[i,j]=d
对于任意k<d,有mk[i,j]md[i,j](这里以m[i,j]=min{m[i,k]+m[k,j]}为例,max的类似),接下来只要证明mk[i+1,j]md[i+1,j],那么只有当s[i+1,j]s[i,j]时才有可能有ms[i+1,j][i+1,j]md[i+1,j]
(mk[i+1,j]-md[i+1,j]) - (mk[i,j]-md[i,j])
=(mk[i+1,j]+md[i,j]) - (md[i+1,j]+mk[i,j])
=(m[i+1,k]+m[k,j]+m[i,d]+m[d,j]) - (m[i+1,d]+m[d,j]+m[i,k]+m[k,j])
=(m[i+1,k]+m[i,d]) - (m[i+1,d]+m[i,k])
m满足四边形不等式,∴对于i<i+1k<dm[i+1,k]+m[i,d]m[i+1,d]+m[i,k]
(mk[i+1,j]-md[i+1,j])(mk[i,j]-md[i,j])0
s[i,j]s[i+1,j],同理可证s[i,j-1]s[i,j]
证毕
http://blog.csdn.net/regina8023/article/details/44241817

四边形不等式优化的大致流程是:
如果w[i][j]满足四边形不等式即w[i][j]+w[i'][j']<=w[i][j']+w[i'][j]  (i<=i'<=j<=j'),

那么f[i][j]也满足四边形不等式,

设f[i][j]=f[i-1][k]+w[k+1][j],f[i][j]在k的时候取到最优值,记s[i][j]=k,则s[i][j]满足单调性:
s[i-1][j]<=s[i][j]<=s[i][j+1]

于是k就不需要从1开始枚举了,从s[i-1][j]到s[i][j+1]枚举即可。

这里有详细证明。

一般证明dp方程满足四边形不等式比较复杂,因此我们只要把s[i][j]暴力求出,看是否满足s[i-1][j]<=s[i][j]<=s[i][j+1]即可。


http://wenku.baidu.com/link?url=2DZtWmnoqlj73G2HxRUSXw840lyK5Z-GT1JgP07f_7OAuIxMFqUxT05d_9OaFBtAMkqC3RdXnZb9hI4Fb0TMQOmmTbUWNxx7F1j5G38keFW

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts