각 부분 집합의 숫자 합계의 표준 편차를 최소화하기 위해 숫자 시퀀스를 n 개의 하위 집합으로 나누는 데 사용할 알고리즘

Question

양수 시퀀스를 n 개의 하위 시퀀스로 세그먼트 화하는 알고리즘을 찾고 있습니다. 각 부분 집합의 숫자 합계의 표준 편차가 최소화되도록

는

는 각 서브 시퀀스의 번호 순서는 원래의 시퀀스 예

의 순서와 동일 할 필요가있다 :

가정하자 I는 시퀀스가 ​​{1,1,1,1,1 , 1,10,1}로 나눌 수 있습니다.
최적의 솔루션은 {1,1,1,1,1,1}, {10,1} 일 것입니다.

첫 번째 하위 시퀀스의 합은 6이고 두 번째 하위 시퀀스의 합은 입니다. 두 숫자의 표준 편차는 ~ 3.5이며 이는 가능한 최저입니다.

시퀀스가 ​​{4,1,1,1,1,6}인데 3 개의 서브 시퀀스로 나누고 싶다고 가정 해 보겠습니다.
최적의 솔루션은 {4}, {1,1,1,1}, {6}
입니다. 서브 시퀀스의 합은 4, 4, 6입니다.
3 개의 숫자의 표준 편차 ~ 1.15입니다. 가능한 한 가장 낮습니다.

가장 좋은 알고리즘은 시퀀스의 각 숫자의 누적 합계를 찾고 [totalSum/numSubsequences]의 각 간격으로 시퀀스를 나누는 것입니다.

예를 들어, 시퀀스 {4,1,1,1,1,6}이 주어진 경우, 각 시퀀스 번호의 누적 합계는 {4,5,6,7,8,14}입니다. 시퀀스의 모든 숫자의 합은 14이므로 3 개의 하위 시퀀스가 ​​필요하므로 전체가 14/3 = 4.66 및 2 * 14/3 = 9.333333에 도달하면 시퀀스를 분할해야합니다.

그러나 누적 합계가 4.66 인 실제 위치는 없습니다. 첫 누적 합계는 4이고 다음 누적 합계는 5입니다. 따라서 반올림해야합니까, 반올림해야합니까? 이 경우 4로 반올림하면 최적의 솔루션이 제공되지만 항상 그런 것은 아닙니다. 내가 생각할 수있는 최선의 방법은 올림과 올림의 모든 조합을 시도하는 것이지만 O (2^numSubsequences) 복잡성을 초래합니다.

이것은 기존의 알고리즘을 적용 할 수있는 유형의 것으로 보이지만 내 인터넷 검색은 실패했습니다. 나는 Partition Problem을 알고 있는데 NP 완성형이지만 순서가없는 순서를 다루지 만 정렬되지 않은 집합을 처리합니다.

도움을 주시면 감사하겠습니다.

Answer 1

원래 시퀀스의 길이가 L이고 서브 시퀀스의 수가 N이라고 가정합니다.

당신은 simplify the expression for standard deviationE가 기대/평균 나타내며 X이 확률 변수를 의미 sqrt(E[X^2] - E[X]^2), 얻을 수 있습니다 - 귀하의 경우, 서브 시퀀스의 합을. (유사한 표준 공식이 "표본 표준 편차"에 적용됩니다.) E[X]은 시퀀스 합계를 N으로 나눈 값이므로 항상 시퀀스를 분리하는 방법에 의존하지 않습니다. 따라서 E[X^2] 또는 이와 동등하게 X^2의 합을 최소화하고자합니다 (평균 정의로 N의 요소가 다릅니다).

이 시점에서 동적 프로그래밍을 통해이 문제를 해결할 수 있습니다.N-1M-0에서 i 및 j를 들어, j 서브 시퀀스로 시퀀스의 첫 번째 i 요소의 분할에서 서브 시퀀스의 합계의 제곱의 최소 합, f(i,j)하자. 그러면 f(i,j)은 f(i',j')과 i' <= i 및 j < j'으로 계산 될 수 있습니다. 보다 구체적으로, 시퀀스가 ​​a[k]이 M-1에 0에서 색인 경우 :

f(i,1) = sum(a[k] for 0 <= k < i)^2 
f(i,j) = minimum of f(l,j-1)+sum(a[k] for l < k < i)^2 for l from 0 to i 

이 f(N,L) 최소화하는 데, 당신은 분할을 복구하는 표준 동적 프로그래밍 기술을 사용할 수 있습니다. 특히 f(i,j)을 최소화하는 l을 저장할 수 있습니다. 당신이 f의 O(L N) 다른 값을 계산하기 때문에

이 솔루션의 런타임 O(L^2 N)하고 minimum는 l의 O(L) 개 이상의 서로 다른 값이다.

여기에 Perl로 간단한 구현의 :

#!/usr/bin/perl 

use strict; 
use warnings; 

local $\ = $/; 
print join ", ", map {"@$_"} best(2, qw(1 1 1 1 1 1 10 1)); 
# prints "1 1 1 1 1 1, 10 1" 

print join ", ", map {"@$_"} best(3, qw(4 1 1 1 1 6)); 
# prints "4, 1 1 1 1, 6" 

sub best { 
    my($N, @a) = @_; 

    my(@f, @g, $i, $j, $k, $sum); 

    # DP base case 
    $sum = 0; 
    $f[0][1] = $g[0][1] = 0; 
    for $i (1 .. @a) { 
     $sum += $a[$i-1]; 
     $f[$i][1] = $sum * $sum; 
     $g[$i][1] = 0; 
    } 

    # DP recurrence 
    for $j (2 .. $N) { 
     $f[0][$j] = $g[0][$j] = 0; 
     for $i (1 .. @a) { 
      $sum = 0; 
      $f[$i][$j] = $f[$i][$j-1]; 
      $g[$i][$j] = $i; 
      for $k (reverse 0 .. $i-1) { 
       $sum += $a[$k]; 
       if($f[$i][$j] > $f[$k][$j-1] + $sum * $sum) { 
        $f[$i][$j] = $f[$k][$j-1] + $sum * $sum; 
        $g[$i][$j] = $k; 
       } 
      } 
     } 
    } 

    # Extract best expansion 
    my(@result); 
    $i = @a; $j = $N; 

    while($j) { 
     $k = $g[$i][$j]; 
     unshift @result, [@a[$k .. $i-1]]; 
     $i = $k; 
     $j--; 
    } 

    return @result; 
} 

Answer 2

내 생각에 오는 한 가지 아이디어는 A * 검색 알고리즘을 사용하는 것입니다.그것에 대해

더 :

이

• 초기 상태 : 다음을 분할하면 A *에 사용할 수

  Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig 
  

  몇 가지 : 그것에 대해 읽을 수

  http://en.wikipedia.org/wiki/A*_search_algorithm 
  

  좋은 책 시퀀스를 n 개의 동일한 (가능한 한 많이) 서브 시퀀스로 변환

• 다음 S tate : 각 부분 집합에 대해 왼쪽 또는 오른쪽 번호 (i! = 0이면)의 하위 집합 i-1의 마지막 번호 또는 하위 집합 i + 1의 첫 번째 번호 (i! = n 인 경우)
• 지능형 : 최적 값은 모든 값의 평균입니다. 허용되기 때문에 A *와 함께 사용할 수 있습니다.

이 문제를 다시 해결하지는 못했지만 실제로 문제를 해결하는 데 도움이되지는 모르겠지만 꽤 잘할 것이라고 생각합니다. 또한이 특정 문제에 대해 가장 정교한 솔루션이 아닐 수도 있지만 "모든 조합을 시도하십시오"접근 방식보다 낫습니다. 그것은 또한 견고하고 완전합니다 (허용 가능한 휴리스틱 때문에).

이 질문에 대해 더 궁금한 점이 있으면 최선을 다해 도와 드리겠습니다.

Answer 3

나는 연속적인 덩어리로 나눌 것을 의미한다. 또는 다른 말로하면 시퀀스를 조각으로 자르는 n-1 장소를 찾는다. 인터리브 (interleave)하는 서브 시퀀스가 ​​주 시퀀스를 생성하도록 허용하려는 경우 시퀀스를 정렬하고 청크 문제를 해결 한 다음 인터리브 된 서브 시퀀스를 제공하기 위해 개별 번호의 출처를 추적 할 수 있습니다.

동적 프로그래밍을 사용하여 시퀀스 길이의 n 배에 비례하여이 문제를 해결할 수 있다고 생각합니다. bestCost [i] [j]와 lastCut [i] [j]의 배열을 채우기 위해 왼쪽에서 오른쪽으로 작업합니다. 여기서 시퀀스를 따라 실행되고 j는 0에서 n-1까지 실행됩니다. bestCost [i] [j]는 0부터 i까지의 시퀀스를 j 청크로 잘리는 가장 좋은 방법의 비용입니다. lastCut [i] [j]는 bestCost [i] [j]를 생성하는 절단에 대한 가장 최근 절단 위치입니다. bestCost [i + 1] [j] = min_k 표준 편차 (i + 1 내지 k) + bestCost [k-1] [j-1]. lastCut [i + 1] [j] = k이다. 마지막에 같은 방법으로 n 개의 컷에 대한 최상의 답을 얻은 다음 lastCut [] []을 사용하여 길을 추적하여 다른 컷을 찾습니다.

Answer 4

내가 동적 프로그래밍이 가장 좋은 방법이 될 수 있음에 동의합니다 - 하나 개의 기술 제가 배제 할 비선형 최적화입니다. 제곱근을 최소화하든 차분 제곱 합을 최소화하든 상관없이 비선형 목적 함수가 있습니다. 또한 제약 조건 집합의 일부로 정수 변수가 있습니다. 집합에 구성원을 할당하려면 형식에 관계없이 일부 정수 변수가 필요합니다. 정수 변수를 이용한 비선형 최적화는 일반적으로 최적으로 풀 수 없다면 대단히 어렵습니다. 대략적인 해법 만 필요하다면 유전자 알고리즘은 유전 적 문자열이 구성원에 대한 집합의 표현 인 좋은 접근법 일 수 있습니다.

1 초 이내에 모든 작업을 수행 할 수 있습니다. 행운을 비네!