부분 집합 근방 검색과의 합 -

Question

근린 알고리즘을 사용하여 부분 집합 합계 문제를 구현하려고합니다. 의사 코드는 다음과 같습니다. 1. Generate a random solution for the problem and call it S 2. Compute the neighborhood of S and choose S' as the best solution in the neighborhood 3. If S' is better than S then go to step 4, else go to step 6 4. S = S' 5. Go to step 2 6. Return S as the best solution encountered X가 10 개 (+ ve 및 -ve) 인 집합이 주어지면 합계가 가능한 한 0에 가깝도록 X의 하위 집합을 찾아야합니다.

는 의사 코드에 따라, 나는 임의의 솔루션 S를 생성했지만, 나는 S.

가 어떻게 S의 근처를 계산 않는 이웃을 구축에 어려움을 만난? S의 이웃은 무엇입니까?

예.

근방 무엇 X = X0, X1, X2, X3, X4, X5, X6, X7, X8, X9]

S = X1, X7, X2, X3]

에스?

Answer 1

이웃에 대한 고유 한 정의가 없으며 문제에 따라 다릅니다. 귀하의 경우에 좋은 정의는 all the tuples that have (at most) n different elements from the current solution 일 수 있습니다. 여기서 n은 1, 2 , size - 1 일 수 있습니다 (n = size을 취하면 전체 솔루션 공간을 고려하고 이웃에 대해 더 이상 의미가 없음).

D = [X0, X7, X2, X3, [X4, X7 : 현재 일로부터 한 단계의 차이가 모든 솔루션을 고려하여 예에서

는 용액의 다음 세트에 미 단부 x2, x3], [x6, x7, x2, x3], [x8, x7, x2, x3], [x9, x7, x2, 의 우리가 그것을에서 다른 하나를 생성 할 수있는 방법을 보자,

S가 하나 개의 솔루션이다 :, X2, X3], [X1, X4, X2, X3, ...]

Answer 2

은 이제 예제를 사용하자

을

• 우리는 [X2, X3, X7을]은 예를 들어 [X1, X2, X3, X7, X8]
• 을 만들거나 예를 들어 우리가 만드는 그것에서 x_i로부터 제거 할 수 있습니다 또 다른 x_i로부터 추가 할 수 있습니다

위의 작업 중 하나를 사용하여 S에서 얻은 모든 솔루션은 S의 이웃입니다. 이러한 솔루션 모두가 이웃을 형성합니다.

이 [X1, X3, X2] 및 [X1, X2, X3]가 중요하지 않은 요소의 순서와 동일한 용액 있다는 사실을 숙지.

---

정식으로 모든 용액은 대응 x_i로부터 용액을 포함하는 경우 0과 1 등 V [I] == 1 이루어진 길이 10의 바이너리 벡터 (V)이다.

같을 것이다 예에서 S에 대응하는 벡터 : S의 = [0, 1, 1, 1, 0, 0, 0, 1, 0, 0]

모든 그러한 벡터 인 솔루션 그래프의 정점. 두 정점 사이의 모서리는 위에서 설명한 것과 같은 일종의 간단한 연산을 사용하여 다른 정점으로 변환 할 수있는 경우에 존재합니다.

이 정보가 도움이되기를 바랍니다.