Сумма подмножества с поиском по окрестностям — Java

Я пытаюсь реализовать проблему суммы подмножества, используя алгоритм соседства. Вот псевдокод: 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), я должен найти такое подмножество X, чтобы сумма была как можно ближе к 0.

Следуя псевдокоду, я сгенерировал случайное решение S, но столкнулся с трудностями при построении окрестности S.

Как вычислить окрестности S? Что такое окрестности S?

E.g.

X = [x0, x1, x2, x3, x4, x5, x6, x7, x8, x9]

S = [x1, x7, x2, x3]

Что такое окрестности S?


java algorithm neighbours subset-sum
person NoName    schedule 20.06.2016    source источник
comment
Есть новости по этому поводу?   -  person Razvan    schedule 12.06.2018

Ответы (2)


arrow_upward
0
arrow_downward

Не существует однозначного определения окрестности, это зависит от проблемы. В вашем случае хорошим определением может быть 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], [x5, x7, x2, x3], [x6, x7, x2, x3], [x8, x7, x2, x3], [x9, x7, x2, x3], [x1, x0, x2, x3], [x1, x4, x2, x3], ... ]

person SimoV8    schedule 20.06.2016

arrow_upward
0
arrow_downward

Давайте использовать пример:

S — это одно решение, давайте посмотрим, как мы можем сгенерировать из него другое:

  • Мы можем добавить к нему еще один x_i, создав, например, [x1, x2, x3, x7, x8]
  • или мы можем удалить из него x_i, создав, например, [x2, x3, x7]

Каждое такое решение, полученное из S с помощью одной из вышеперечисленных операций, является соседом S. Все такие решения образуют окрестность.

Имейте в виду, что [x1, x3, x2] и [x1, x2, x3] — это одно и то же решение, поскольку порядок элементов не имеет значения.

Формально каждое решение представляет собой двоичный вектор v длины 10, состоящий из 0 и 1, например v[i] == 1, если соответствующее решение содержит x_i.

Вектор, соответствующий S из примера, будет выглядеть так: S = [0, 1, 1, 1, 0, 0, 0, 1, 0, 0]

Каждый такой вектор является вершиной графа решений. Ребро между двумя такими вершинами существует, если одну можно преобразовать в другую с помощью какой-либо простой операции, подобной описанной выше.

Надеюсь, это поможет.

person kvlr    schedule 20.06.2016