私は整数のセットを持っています。動的計画法を使用して、そのセットの最長増加サブシーケンスを見つけたいです。
質問する
192684 次
20 に答える
431
わかりました。最初に、O(N^2) である最も単純なソリューションについて説明します。ここで、N はコレクションのサイズです。O(N log N) ソリューションも存在します。これについても説明します。セクション効率的なアルゴリズムでそれを探してください。
配列のインデックスは 0 から N - 1 であると仮定します。したがって、DP[i]を、 index の要素で終了する LIS (最長増加サブシーケンス) の長さと定義しましょうi。計算するDP[i]には、すべてのインデックスを調べて、と(増加させたい)j < iの両方をチェックします。これが真の場合、 の現在の最適値を更新できます。配列のグローバルな最適値を見つけるには、 から最大値を取得できます。DP[j] + 1 > DP[i]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)ソリューションに移りましょう。
S[pos]長さ の増加するシーケンスを終了する最小の整数として を定義しますpos。X入力セットのすべての整数を繰り返し処理し、次の操作を行います。
X> の最後の要素の場合、 の末尾にS追加します。これは基本的に、新しい最大の を見つけたことを意味します。XSLISそれ以外の場合は、
Sで最小の要素を見つけて、 に変更します。は常にソートされるため、要素は でバイナリ検索を使用して見つけることができます。>=XXSlog(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には、親配列を再度使用します。indexを持つ要素の末尾にあるparent[i]index を持つ要素の前身であるとします。iLISi
物事を簡単にするために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]]]],
........................................
重要なことは、親配列をどのように更新するかということです。次の 2 つのオプションがあります。
X> の最後の要素の場合S、parent[indexX] = indexLastElement. これは、最新の要素の親が最後の要素であることを意味します。Xの末尾に追加するだけですS。それ以外の場合は
S、内の最小要素のインデックスを見つけて、それを に変更します。ここに。>=XXparent[indexX] = S[index - 1]
于 2010-04-13T17:39:57.907 に答える
64
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
于 2013-11-09T01:48:46.737 に答える
27
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]
}
于 2016-04-25T09:33:45.440 に答える
4
動的計画法の観点から問題を評価する 3 つの手順を次に示します。
- 繰り返しの定義: 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 の要素を既存のサブシーケンスに追加することにより、2 つの新しいシーケンス {0, 8, 2} および {0, 2} を評価しようとしています - 1 つだけが有効であるため、3 番目に可能なシーケンス {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;
}
于 2013-11-13T00:54:34.463 に答える
1
O(n^2) アルゴリズムの Scala 実装を次に示します。
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)))
}
}
于 2014-12-14T05:21:55.560 に答える
1
ここにJava O（nlogn）の実装があります
import java.util.Scanner;
public class LongestIncreasingSeq {
private static int binarySearch(int table[],int a,int len){
int end = len-1;
int beg = 0;
int mid = 0;
int result = -1;
while(beg <= end){
mid = (end + beg) / 2;
if(table[mid] < a){
beg=mid+1;
result = mid;
}else if(table[mid] == a){
return len-1;
}else{
end = mid-1;
}
}
return result;
}
public static void main(String[] args) {
// int[] t = {1, 2, 5,9,16};
// System.out.println(binarySearch(t , 9, 5));
Scanner in = new Scanner(System.in);
int size = in.nextInt();//4;
int A[] = new int[size];
int table[] = new int[A.length];
int k = 0;
while(k<size){
A[k++] = in.nextInt();
if(k<size-1)
in.nextLine();
}
table[0] = A[0];
int len = 1;
for (int i = 1; i < A.length; i++) {
if(table[0] > A[i]){
table[0] = A[i];
}else if(table[len-1]<A[i]){
table[len++]=A[i];
}else{
table[binarySearch(table, A[i],len)+1] = A[i];
}
}
System.out.println(len);
}
}
//TreeSet を使用できます
于 2015-05-14T18:20:24.773 に答える
0
配列要素を使用した最長増加サブシーケンスについては、Java のコードをチェックアウトしてください
/**
** Java Program to implement Longest Increasing Subsequence Algorithm
**/
import java.util.Scanner;
/** Class LongestIncreasingSubsequence **/
class LongestIncreasingSubsequence
{
/** function lis **/
public int[] lis(int[] X)
{
int n = X.length - 1;
int[] M = new int[n + 1];
int[] P = new int[n + 1];
int L = 0;
for (int i = 1; i < n + 1; i++)
{
int j = 0;
/** Linear search applied here. Binary Search can be applied too.
binary search for the largest positive j <= L such that
X[M[j]] < X[i] (or set j = 0 if no such value exists) **/
for (int pos = L ; pos >= 1; pos--)
{
if (X[M[pos]] < X[i])
{
j = pos;
break;
}
}
P[i] = M[j];
if (j == L || X[i] < X[M[j + 1]])
{
M[j + 1] = i;
L = Math.max(L,j + 1);
}
}
/** backtrack **/
int[] result = new int[L];
int pos = M[L];
for (int i = L - 1; i >= 0; i--)
{
result[i] = X[pos];
pos = P[pos];
}
return result;
}
/** Main Function **/
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Longest Increasing Subsequence Algorithm Test\n");
System.out.println("Enter number of elements");
int n = scan.nextInt();
int[] arr = new int[n + 1];
System.out.println("\nEnter "+ n +" elements");
for (int i = 1; i <= n; i++)
arr[i] = scan.nextInt();
LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence();
int[] result = obj.lis(arr);
/** print result **/
System.out.print("\nLongest Increasing Subsequence : ");
for (int i = 0; i < result.length; i++)
System.out.print(result[i] +" ");
System.out.println();
}
}
于 2015-10-27T11:09:16.903 に答える
0
これは、動的計画法を使用して O(n^2) で解決できます。同じためのPythonコードは次のようになります:-
def LIS(numlist):
LS = [1]
for i in range(1, len(numlist)):
LS.append(1)
for j in range(0, i):
if numlist[i] > numlist[j] and LS[i]<=LS[j]:
LS[i] = 1 + LS[j]
print LS
return max(LS)
numlist = map(int, raw_input().split(' '))
print LIS(numlist)
入力用:5 19 5 81 50 28 29 1 83 23
出力は次のようになります。[1, 2, 1, 3, 3, 3, 4, 1, 5, 3]
5
出力リストの list_index は、入力リストの list_index です。出力リストの指定された list_index の値は、その list_index の最長増加サブシーケンス長を示します。
于 2014-04-13T19:57:01.680 に答える
0
O(n^2) Java 実装:
void LIS(int arr[]){
int maxCount[]=new int[arr.length];
int link[]=new int[arr.length];
int maxI=0;
link[0]=0;
maxCount[0]=0;
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < i; j++) {
if(arr[j]<arr[i] && ((maxCount[j]+1)>maxCount[i])){
maxCount[i]=maxCount[j]+1;
link[i]=j;
if(maxCount[i]>maxCount[maxI]){
maxI=i;
}
}
}
}
for (int i = 0; i < link.length; i++) {
System.out.println(arr[i]+" "+link[i]);
}
print(arr,maxI,link);
}
void print(int arr[],int index,int link[]){
if(link[index]==index){
System.out.println(arr[index]+" ");
return;
}else{
print(arr, link[index], link);
System.out.println(arr[index]+" ");
}
}
于 2017-02-17T20:27:54.047 に答える