[algorithm] 동적 프로그래밍을 사용하여 가장 긴 하위 시퀀스를 결정하는 방법은 무엇입니까?
정수 세트가 있습니다. 동적 프로그래밍을 사용하여 해당 세트 의 가장 긴 하위 시퀀스 를 찾고 싶습니다 .
답변
먼저 가장 간단한 솔루션 인 O (N ^ 2)를 설명하겠습니다. 여기서 N은 컬렉션의 크기입니다. O (N log N) 솔루션도 있는데, 이것도 설명하겠습니다. 봐 여기 섹션 효율적인 알고리즘에 그것을합니다.
배열의 인덱스가 0에서 N-1 사이라고 가정하겠습니다. 따라서 DP[i]index가있는 요소에서 끝나는 LIS (길이가 가장 긴 하위 시퀀스)의 길이로 정의하겠습니다 i. 계산하기 위해 DP[i]우리는 모든 지수를 살펴보고 j < iif DP[j] + 1 > DP[i]와 if array[j] < array[i](증가하기를 원함)를 모두 확인합니다 . 이것이 사실이라면에 대한 현재 최적을 업데이트 할 수 있습니다 DP[i]. 배열에 대한 전역 최적을 찾으려면에서 최대 값을 사용할 수 있습니다 DP[0...N - 1].
int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;
for (int i = 1; i < N; i++)
{
DP[i] = 1;
prev[i] = -1;
for (int j = i - 1; j >= 0; j--)
if (DP[j] + 1 > DP[i] && array[j] < array[i])
{
DP[i] = DP[j] + 1;
prev[i] = j;
}
if (DP[i] > maxLength)
{
bestEnd = i;
maxLength = DP[i];
}
}
배열 prev을 사용하여 길이뿐만 아니라 실제 시퀀스를 나중에 찾을 수 있습니다. 를 bestEnd사용하여 루프에서 재귀 적으로 돌아가십시오 prev[bestEnd]. -1값은 정지 표시이다.
이제 더 효율적인 O(N log N)솔루션 으로 넘어가십시오.
LET S[pos]길이의 증가 순서를 종료 최소 정수로 정의된다 pos. 이제 X입력 세트의 모든 정수 를 반복 하고 다음을 수행하십시오.
-
X>에서 마지막 요소 인 경우 의 끝에S추가하십시오 . 이것은 본질적으로 우리가 새로운 가장 큰 것을 발견했다는 것을 의미 합니다.XSLIS -
그렇지 않으면에서 가장 작은 요소 발견
S하고,>=보다를X, 그리고로 변경X.S언제든 정렬 되므로 에서 이진 검색을 사용하여 요소를 찾을 수 있습니다log(N).
총 런타임- N정수 및 각각에 대한 이진 검색-N * log (N) = O (N log N)
이제 실제 예제를 보자 :
정수 수집 :
2 6 3 4 1 2 9 5 8
단계 :
0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS
따라서 LIS의 길이는 5(S의 크기)입니다.
실제를 재구성하기 위해 LIS다시 부모 배열을 사용합니다. 하자 parent[i]인덱스 요소의 전신이 될 i에서 LIS인덱스 요소에서 결말 i.
일을 더 간단하게하기 위해 S실제 정수가 아니라 세트의 인덱스 (위치)에 배열을 유지할 수 있습니다 . 우리는 유지하지 않고 유지 {1, 2, 4, 5, 8}합니다 {4, 5, 3, 7, 8}.
즉 input [4] = 1 , input [5] = 2 , input [3] = 4 , input [7] = 5 , input [8] = 8 입니다.
부모 배열을 올바르게 업데이트하면 실제 LIS는 다음과 같습니다.
input[S[lastElementOfS]],
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................
이제 중요한 것은 부모 배열을 어떻게 업데이트합니까? 두 가지 옵션이 있습니다.
-
만약
X>의 마지막 요소S다음parent[indexX] = indexLastElement. 이것은 최신 요소의 부모가 마지막 요소임을 의미합니다. 우리는 단지X끝에 끝S. -
그렇지 않으면에서 가장 작은 요소의 인덱스 찾을 수
S있습니다,>=보다를X, 그리고로 변경X. 이곳까지parent[indexX] = S[index - 1].
답변
Petar Minchev의 설명은 나를 위해 명확하게 도움이되었지만 모든 것이 무엇인지 파싱하기가 어려웠으므로 지나치게 설명이 쉬운 변수 이름과 많은 주석으로 Python을 구현했습니다. 순진한 재귀 솔루션, O (n ^ 2) 솔루션 및 O (n log n) 솔루션을 수행했습니다.
알고리즘을 정리하는 데 도움이되기를 바랍니다.
재귀 솔루션
def recursive_solution(remaining_sequence, bigger_than=None):
"""Finds the longest increasing subsequence of remaining_sequence that is
bigger than bigger_than and returns it. This solution is O(2^n)."""
# Base case: nothing is remaining.
if len(remaining_sequence) == 0:
return remaining_sequence
# Recursive case 1: exclude the current element and process the remaining.
best_sequence = recursive_solution(remaining_sequence[1:], bigger_than)
# Recursive case 2: include the current element if it's big enough.
first = remaining_sequence[0]
if (first > bigger_than) or (bigger_than is None):
sequence_with = [first] + recursive_solution(remaining_sequence[1:], first)
# Choose whichever of case 1 and case 2 were longer.
if len(sequence_with) >= len(best_sequence):
best_sequence = sequence_with
return best_sequence
O (n ^ 2) 동적 프로그래밍 솔루션
def dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming. This solution is O(n^2)."""
longest_subsequence_ending_with = []
backreference_for_subsequence_ending_with = []
current_best_end = 0
for curr_elem in range(len(sequence)):
# It's always possible to have a subsequence of length 1.
longest_subsequence_ending_with.append(1)
# If a subsequence is length 1, it doesn't have a backreference.
backreference_for_subsequence_ending_with.append(None)
for prev_elem in range(curr_elem):
subsequence_length_through_prev = (longest_subsequence_ending_with[prev_elem] + 1)
# If the prev_elem is smaller than the current elem (so it's increasing)
# And if the longest subsequence from prev_elem would yield a better
# subsequence for curr_elem.
if ((sequence[prev_elem] < sequence[curr_elem]) and
(subsequence_length_through_prev >
longest_subsequence_ending_with[curr_elem])):
# Set the candidate best subsequence at curr_elem to go through prev.
longest_subsequence_ending_with[curr_elem] = (subsequence_length_through_prev)
backreference_for_subsequence_ending_with[curr_elem] = prev_elem
# If the new end is the best, update the best.
if (longest_subsequence_ending_with[curr_elem] >
longest_subsequence_ending_with[current_best_end]):
current_best_end = curr_elem
# Output the overall best by following the backreferences.
best_subsequence = []
current_backreference = current_best_end
while current_backreference is not None:
best_subsequence.append(sequence[current_backreference])
current_backreference = (backreference_for_subsequence_ending_with[current_backreference])
best_subsequence.reverse()
return best_subsequence
O (n log n) 동적 프로그래밍 솔루션
def find_smallest_elem_as_big_as(sequence, subsequence, elem):
"""Returns the index of the smallest element in subsequence as big as
sequence[elem]. sequence[elem] must not be larger than every element in
subsequence. The elements in subsequence are indices in sequence. Uses
binary search."""
low = 0
high = len(subsequence) - 1
while high > low:
mid = (high + low) / 2
# If the current element is not as big as elem, throw out the low half of
# sequence.
if sequence[subsequence[mid]] < sequence[elem]:
low = mid + 1
# If the current element is as big as elem, throw out everything bigger, but
# keep the current element.
else:
high = mid
return high
def optimized_dynamic_programming_solution(sequence):
"""Finds the longest increasing subsequence in sequence using dynamic
programming and binary search (per
http://en.wikipedia.org/wiki/Longest_increasing_subsequence). This solution
is O(n log n)."""
# Both of these lists hold the indices of elements in sequence and not the
# elements themselves.
# This list will always be sorted.
smallest_end_to_subsequence_of_length = []
# This array goes along with sequence (not
# smallest_end_to_subsequence_of_length). Following the corresponding element
# in this array repeatedly will generate the desired subsequence.
parent = [None for _ in sequence]
for elem in range(len(sequence)):
# We're iterating through sequence in order, so if elem is bigger than the
# end of longest current subsequence, we have a new longest increasing
# subsequence.
if (len(smallest_end_to_subsequence_of_length) == 0 or
sequence[elem] > sequence[smallest_end_to_subsequence_of_length[-1]]):
# If we are adding the first element, it has no parent. Otherwise, we
# need to update the parent to be the previous biggest element.
if len(smallest_end_to_subsequence_of_length) > 0:
parent[elem] = smallest_end_to_subsequence_of_length[-1]
smallest_end_to_subsequence_of_length.append(elem)
else:
# If we can't make a longer subsequence, we might be able to make a
# subsequence of equal size to one of our earlier subsequences with a
# smaller ending number (which makes it easier to find a later number that
# is increasing).
# Thus, we look for the smallest element in
# smallest_end_to_subsequence_of_length that is at least as big as elem
# and replace it with elem.
# This preserves correctness because if there is a subsequence of length n
# that ends with a number smaller than elem, we could add elem on to the
# end of that subsequence to get a subsequence of length n+1.
location_to_replace = find_smallest_elem_as_big_as(sequence, smallest_end_to_subsequence_of_length, elem)
smallest_end_to_subsequence_of_length[location_to_replace] = elem
# If we're replacing the first element, we don't need to update its parent
# because a subsequence of length 1 has no parent. Otherwise, its parent
# is the subsequence one shorter, which we just added onto.
if location_to_replace != 0:
parent[elem] = (smallest_end_to_subsequence_of_length[location_to_replace - 1])
# Generate the longest increasing subsequence by backtracking through parent.
curr_parent = smallest_end_to_subsequence_of_length[-1]
longest_increasing_subsequence = []
while curr_parent is not None:
longest_increasing_subsequence.append(sequence[curr_parent])
curr_parent = parent[curr_parent]
longest_increasing_subsequence.reverse()
return longest_increasing_subsequence
답변
DP 솔루션에 대해 말하면서, LIS가 LCS 로 축소 될 수 있다는 사실을 언급 한 사람이 아무도 없다는 것이 놀랍습니다 . 원본 시퀀스의 사본을 정렬하고 모든 복제본을 제거하고 LCS를 수행하기 만하면됩니다. 의사 코드에서는 다음과 같습니다.
def LIS(S):
T = sort(S)
T = removeDuplicates(T)
return LCS(S, T)
그리고 Go로 작성된 전체 구현. 솔루션을 재구성 할 필요가없는 경우 n ^ 2 DP 매트릭스 전체를 유지할 필요가 없습니다.
func lcs(arr1 []int) int {
arr2 := make([]int, len(arr1))
for i, v := range arr1 {
arr2[i] = v
}
sort.Ints(arr1)
arr3 := []int{}
prev := arr1[0] - 1
for _, v := range arr1 {
if v != prev {
prev = v
arr3 = append(arr3, v)
}
}
n1, n2 := len(arr1), len(arr3)
M := make([][]int, n2 + 1)
e := make([]int, (n1 + 1) * (n2 + 1))
for i := range M {
M[i] = e[i * (n1 + 1):(i + 1) * (n1 + 1)]
}
for i := 1; i <= n2; i++ {
for j := 1; j <= n1; j++ {
if arr2[j - 1] == arr3[i - 1] {
M[i][j] = M[i - 1][j - 1] + 1
} else if M[i - 1][j] > M[i][j - 1] {
M[i][j] = M[i - 1][j]
} else {
M[i][j] = M[i][j - 1]
}
}
}
return M[n2][n1]
}
답변
다음 C ++ 구현에는 이라는 배열을 사용하여 실제로 가장 오래 증가하는 하위 시퀀스 를 작성하는 코드도 포함되어 있습니다 prev.
std::vector<int> longest_increasing_subsequence (const std::vector<int>& s)
{
int best_end = 0;
int sz = s.size();
if (!sz)
return std::vector<int>();
std::vector<int> prev(sz,-1);
std::vector<int> memo(sz, 0);
int max_length = std::numeric_limits<int>::min();
memo[0] = 1;
for ( auto i = 1; i < sz; ++i)
{
for ( auto j = 0; j < i; ++j)
{
if ( s[j] < s[i] && memo[i] < memo[j] + 1 )
{
memo[i] = memo[j] + 1;
prev[i] = j;
}
}
if ( memo[i] > max_length )
{
best_end = i;
max_length = memo[i];
}
}
// Code that builds the longest increasing subsequence using "prev"
std::vector<int> results;
results.reserve(sz);
std::stack<int> stk;
int current = best_end;
while (current != -1)
{
stk.push(s[current]);
current = prev[current];
}
while (!stk.empty())
{
results.push_back(stk.top());
stk.pop();
}
return results;
}
스택이없는 구현은 벡터를 거꾸로합니다.
#include <iostream>
#include <vector>
#include <limits>
std::vector<int> LIS( const std::vector<int> &v ) {
auto sz = v.size();
if(!sz)
return v;
std::vector<int> memo(sz, 0);
std::vector<int> prev(sz, -1);
memo[0] = 1;
int best_end = 0;
int max_length = std::numeric_limits<int>::min();
for (auto i = 1; i < sz; ++i) {
for ( auto j = 0; j < i ; ++j) {
if (s[j] < s[i] && memo[i] < memo[j] + 1) {
memo[i] = memo[j] + 1;
prev[i] = j;
}
}
if(memo[i] > max_length) {
best_end = i;
max_length = memo[i];
}
}
// create results
std::vector<int> results;
results.reserve(v.size());
auto current = best_end;
while (current != -1) {
results.push_back(s[current]);
current = prev[current];
}
std::reverse(results.begin(), results.end());
return results;
}
답변
다음은 동적 프로그래밍 관점에서 문제를 평가하는 세 단계입니다.
- 반복 정의 : maxLength (i) == 1 + maxLength (j) 여기서 0 <j <i 및 array [i]> array [j]
- 반복 매개 변수 경계 : 매개 변수로 전달 된 0-i-1 개의 서브 시퀀스가있을 수 있습니다.
- 평가 순서 : 하위 시퀀스가 증가함에 따라 0에서 n까지 평가되어야합니다.
인덱스에서 시퀀스 {0, 8, 2, 3, 7, 9}를 예로 들면 다음과 같습니다.
- [0] 기본 시퀀스로 하위 시퀀스 {0}을 얻습니다.
- [1] 1 개의 새로운 하위 시퀀스 {0, 8}이 있습니다.
- [2] 인덱스 2의 요소를 기존 하위 시퀀스에 추가하여 두 개의 새로운 시퀀스 {0, 8, 2} 및 {0, 2}를 평가하려고합니다. 하나만 유효하므로 세 번째 가능한 시퀀스 {0, 2} 만 추가 파라미터 목록으로 …
작동하는 C ++ 11 코드는 다음과 같습니다.
#include <iostream>
#include <vector>
int getLongestIncSub(const std::vector<int> &sequence, size_t index, std::vector<std::vector<int>> &sub) {
if(index == 0) {
sub.push_back(std::vector<int>{sequence[0]});
return 1;
}
size_t longestSubSeq = getLongestIncSub(sequence, index - 1, sub);
std::vector<std::vector<int>> tmpSubSeq;
for(std::vector<int> &subSeq : sub) {
if(subSeq[subSeq.size() - 1] < sequence[index]) {
std::vector<int> newSeq(subSeq);
newSeq.push_back(sequence[index]);
longestSubSeq = std::max(longestSubSeq, newSeq.size());
tmpSubSeq.push_back(newSeq);
}
}
std::copy(tmpSubSeq.begin(), tmpSubSeq.end(),
std::back_insert_iterator<std::vector<std::vector<int>>>(sub));
return longestSubSeq;
}
int getLongestIncSub(const std::vector<int> &sequence) {
std::vector<std::vector<int>> sub;
return getLongestIncSub(sequence, sequence.size() - 1, sub);
}
int main()
{
std::vector<int> seq{0, 8, 2, 3, 7, 9};
std::cout << getLongestIncSub(seq);
return 0;
}
답변
다음은 O (n ^ 2) 알고리즘의 스칼라 구현입니다.
object Solve {
def longestIncrSubseq[T](xs: List[T])(implicit ord: Ordering[T]) = {
xs.foldLeft(List[(Int, List[T])]()) {
(sofar, x) =>
if (sofar.isEmpty) List((1, List(x)))
else {
val resIfEndsAtCurr = (sofar, xs).zipped map {
(tp, y) =>
val len = tp._1
val seq = tp._2
if (ord.lteq(y, x)) {
(len + 1, x :: seq) // reversely recorded to avoid O(n)
} else {
(1, List(x))
}
}
sofar :+ resIfEndsAtCurr.maxBy(_._1)
}
}.maxBy(_._1)._2.reverse
}
def main(args: Array[String]) = {
println(longestIncrSubseq(List(
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15)))
}
}
답변
다음은 또 다른 O (n ^ 2) JAVA 구현입니다. 실제 하위 시퀀스를 생성하기위한 재귀 / 메모리가 없습니다. 모든 단계에서 실제 LIS를 저장하는 문자열 배열과 각 요소의 LIS 길이를 저장하는 배열입니다. 꽤 쉬운 일입니다. 보세요 :
import java.io.BufferedReader;
import java.io.InputStreamReader;
/**
* Created by Shreyans on 4/16/2015
*/
class LNG_INC_SUB//Longest Increasing Subsequence
{
public static void main(String[] args) throws Exception
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter Numbers Separated by Spaces to find their LIS\n");
String[] s1=br.readLine().split(" ");
int n=s1.length;
int[] a=new int[n];//Array actual of Numbers
String []ls=new String[n];// Array of Strings to maintain LIS for every element
for(int i=0;i<n;i++)
{
a[i]=Integer.parseInt(s1[i]);
}
int[]dp=new int[n];//Storing length of max subseq.
int max=dp[0]=1;//Defaults
String seq=ls[0]=s1[0];//Defaults
for(int i=1;i<n;i++)
{
dp[i]=1;
String x="";
for(int j=i-1;j>=0;j--)
{
//First check if number at index j is less than num at i.
// Second the length of that DP should be greater than dp[i]
// -1 since dp of previous could also be one. So we compare the dp[i] as empty initially
if(a[j]<a[i]&&dp[j]>dp[i]-1)
{
dp[i]=dp[j]+1;//Assigning temp length of LIS. There may come along a bigger LIS of a future a[j]
x=ls[j];//Assigning temp LIS of a[j]. Will append a[i] later on
}
}
x+=(" "+a[i]);
ls[i]=x;
if(dp[i]>max)
{
max=dp[i];
seq=ls[i];
}
}
System.out.println("Length of LIS is: " + max + "\nThe Sequence is: " + seq);
}
}
작동 코드 : http://ideone.com/sBiOQx
