특정 평가에 따라 개체 집합을 여러 하위 집합으로 분할

Question

개체 집합이 있다고 가정하면 S입니다. S 집합이 특정 데이터 구조 D을 빌드하면 이라는 알고리즘 f이 있습니다. S이 크고 매우 다른 객체를 포함하면 D이 커져서 사용할 수 없게됩니다 (할당 된 메모리에 적합하지 않음). 이 문제를 극복하기 위해 S을 여러 교차하지 않는 하위 집합 (S = S1 + S2 + ... + Sn)으로 분할하고 각 하위 집합에 대해 Di을 작성했습니다. n 구조를 사용하는 것은 하나를 사용하는 것보다 덜 효율적이지만 최소한 메모리 제약 조건에 맞출 수는 있습니다. f(S) 크기가 S보다 빠르게 증가하므로 Di의 결합 크기는 D 크기보다 훨씬 작습니다.

그러나, 여전히 서브 세트의 수인 n을 감소시키는 것이 바람직하다. 또는 결합 된 크기를 Di으로 줄이십시오. 이를 위해 S을 각각의 Si에 "유사한"개체가 포함되도록 분할해야합니다. 왜냐하면 f은 입력 개체가 서로 "충분히 유사"한 경우 더 작은 출력 구조를 생성하기 때문입니다.

문제는 S 및 f(S)의 크기는 물체의 "유사성"상관 관계 않지만,이 단지 f(S)을 평가보다 후자의 기타를 계산하는 방법은 없으며, f 매우 빠른되지 않는 것입니다. 이 범

for x in S: 
    i = such i that 
      size(f(Si + {x})) - size(f(Si)) 
      is min 
    Si = Si + {x} 

:

알고리즘 I 현재이 (이 단계에서) 가능한 최소 초래하도록 반복적으로 결합 Di 크기, Si 중 하나 S에서 증가를 각각 다음의 오브젝트를 추가하는 가지고 실용적으로 유용한 결과를 보여 주지만, 최적의 것에서는 꽤 멀다. 또한 은입니다. 다소 속도를 높이기 위해 i에 대해서만 size(f(Si + {x})) - size(f(Si))을 계산합니다. x은 이미 Si에있는 객체에 "충분히 유사"합니다.

이러한 종류의 문제에 대한 표준 접근법이 있습니까?

나는 branch and bounds 알고리즘 패밀리를 알고 있지만, 너무 느려서 여기서는 적용 할 수 없다. 내 생각에 합당한 시간에 S의 최적 분포를 Si으로 계산하는 것은 불가능합니다. 그러나 반복적으로 알고리즘을 개선하는 몇 가지 공통점이 있습니까?

편집 : 코멘트 언급

, 나는이 "유사성"정의되지 않았다. 사실, 내가 원하는 것은 Di = f(Si)의 결합 된 크기가 최소한이거나 적어도 충분히 작은 서브 세트 Si으로 분할하는 것입니다. "유사성"은 이것으로 정의되며 유감스럽게도 쉽게 계산할 수 없습니다. 나는 간단한 근사값을 가지고 있지만 근사치 일뿐입니다. 내가 좋은 결과를 제공하는 것은 매우 어렵다 사례를 버려야 만 사용 근사치 -

그래서, 내가 필요한 것은 sum f(Si) 후자를 계산 할 간단한 방법 이 없다는 것을 주어진 최소화하는 (가능성이 heuristical) 알고리즘이다.

Answer 1

느린 점에 대해서도 유사한 문제에서 고정 된 수의 무작위 후보를 선택하는 것만으로도 충분한 결과를 얻을 수 있다는 것을 알았습니다.

결과가 최상의 (내가 구현 한 "욕심 많은"솔루션보다 좋지 않은) 결과가 아닐 수도 있지만 내 경험 에선 그렇게 나쁘지 않고 속도를 결정할 수 있습니다. 실제로 구현할 수도 있습니다. 지정된 시간 (즉, 할당 된 시간이 만료 될 때까지 검색을 계속합니다).

내가 사용하는 또 다른 옵션은 잠시 동안 개선되지 않을 때까지 계속 검색하는 것입니다.

욕심이 많은 로직을 지나치려면 N "x"엘리먼트의 큐를 유지하고 "k"(k < N)의 그룹으로 동시에 패킹하려고 할 수 있습니다. 이 경우 대기열에있는 요소의 "수명"을 유지하고 결과에 대한 "상금"으로 사용하여 다른 요소가 항상 일치하기 때문에 대기열에 영원히 "나쁜"요소를 보관하지 않는 것이 중요하다는 것을 알았습니다 (이것은 큐 검색을 쓸모 없게 만들 것이고 그 결과는 기본적으로 욕심 많은 접근법과 동일 할 것이다).