Предложения для алгоритма предложения фрагментов

Question

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

У меня есть серия «весов», * w_i *, которая может суммироваться до общего веса. В результате измеренный общий вес имеет связанную с этим ошибку, поэтому она неточна.

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

Теперь это звучит подозрительно, как ограниченно-целочисленной задачи множественного рюкзаке, однако

• можно идти над вес, и
• Я также хочу все занимает решения с точки зрения погрешности

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

Количество весов обычно невелико (4 -> 10 веса) и отношение общего веса среднего веса обычно составляет около 2 или 3

Кто-нибудь знает имена алгоритма, который может быть подходит здесь?

Answer 1

Ваша проблема действительно напоминает проблему с рюкзаком, которая является NP-полной проблемой.

Для действительно ограниченного количества весов вы можете использовать все комбинации с повторением, а затем сортировку, которая дает вам довольно большое количество манипуляций; в лучшем случае: (n + k - 1)!/((n - 1)! · k!) для комбинации и n·log(n) для сортировочной части.

Решить эту проблему в разумные сроки лучше всего сделать с помощью эволюционных алгоритмов в настоящее время.

Если взять следующий пример из ОЭАПА, эволюционная структура алгоритма в Python: ga_knapsack.py, вы понимаете, что путь изменения строки 58-59, который автоматически сбрасывает избыточный вес решения что-то более гладкого (линейную зависимость, например), это даст вам решения, близкие к оптимальным, за более короткое время, чем грубая сила. Решения уже отсортированы для вас в конце, как вы просили.

Answer 2

В первой попытке я бы пойти на ограничения программирования (но тогда я почти всегда делаю, поэтому принять предложение с щепоткой соли):

1. Учитывая W = w_1, ..., w_i для весов и E = e_1, .., e_i для ошибки (вы также можете сделать ее асимметричной), а T.
2. Найти все множества S (если веса являются уникальными или список) st sum w_1 + e_1, ..., w_k + e_k (где w_1, .., w_k \ elem и e_1, ..., e_k \ elem E) \ approx T в некоторой дельте, которую вы получаете из k. Или просто установите его на какое-то достаточно большое значение и уменьшите его, когда вы решаете ограничения.

Я просто понимаю, что вы хотите параметризовать выражение w_n оп E_m над оп \ элем +, - (любая комбинация весов и сроков ошибок) и от верхней части моей головы, я не знаю, какие ограничения решатель позволит вам это сделать. В любом случае вы всегда можете вернуться к прологу. Он может не летать, особенно если у вас много веса, но он быстро даст вам решения.