Ответы пользователя по тегу Алгоритмы
  • Как организовать выборку эффективных вариантов из таблицы?

    @MagicMight
    Задача в нахождении паретооптимального множества решений?
    Допустим, есть вектор характеристик (п1, п3, м) и нужно найти решения, где п1 и п3 максимальны, а М минимально.
    Каждая пара решений(р1, р2) может находиться в трех состояниях:
    1) р1 по всем параметрам лучше р2
    2) р2 по всем параметрам лучше р1
    3) р1 и р2 векторно несравнимы (когда часть параметров одного решения лучше, а часть хуже). Пример (item1, item5).

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

    P.S. в свое время мне помогла книга Подиновский В.В., Ногин В.Д. Парето-оптимальные ре...

    UPD. Полное решение.

    Алгоритм.
    Пусть у нас есть N записей (будем называть их n1, n2, ...), каждой из которых ставится в соответствие вектор характеристик (a,b,c), где a - param1, b - param2, c - money.
    Есть ограничение minmax на a, b и max на c.
    Шаг 1.
    Для каждой отдельно взятой записи определяем количество, больше которого мы не можем взять (назовем его max(n)).
    Пример. Если у нас есть запись (5, 10, 10), minmax(a) = (40, 80), minmax(b) = (50, 70), max(c) = 60, то
    Определям количество.
    max(a): 80 / 5 = максимум 16 записей
    max(b): 70 / 10 = максимум 7 записей
    max(c): 60 / 10 = максимум 6 записей
    То есть из всех верхних ограничений следует, что мы можем взять эту запись не более 6 раз. max(n) = 6
    Строки с max(n)=0 удаляем.

    Шаг 1.1 (опциональный). Позволяет отловить решение, удовлетворяющее всем условиям быстрее, но не обязательно выдаст самое эффективное.
    Для каждой записи сделаем проверку по минимальному условию min(n). В качестве примера возьмем запись из прошлого примера.
    min(a): 40 / 5 = минимум 8 записей
    min(b): 50 / 10 = минимум 5 записей
    По совокупности ограничений понимаем, что мы можем взять минимум 8, а максимум 6 записей для составления решения
    только из нескольких этих записей, что невозможно. Если бы мы получили результат, где min(n) <= max(n), то могли бы построить допустимые решения,
    состоящие из одной записи.

    Шаг 2. Составление комбинаций из записей.
    Представим, что у нас есть чудесное выражение вида k1*n1 + k2*n2 + ... + kN*nN = (ak, bk, ck)
    Диапазон для перебора каждого k_i = (0, max(n_i))
    Помним, что n_i - это вектора. Соответственно, результат выражения - это сумма векторов, каждый из которых домножен на свой коэффициент.
    Все те коэффициенты, при которых (ak, bk, ck) удовлетворяют minmax на ak, bk и max на ck мы сохраняем как допустимые.

    Все :)
    Ответ написан