Лучший способ поиска / фильтрации (возможно, несколько миллиардов) комбинаций элементов из нескольких списков или массивов - PullRequest
Новая
       19

Лучший способ поиска / фильтрации (возможно, несколько миллиардов) комбинаций элементов из нескольких списков или массивов

3 голосов
/ 19 сентября 2019

Я пытаюсь написать программу для оптимизации конфигурации оборудования для игры.Проблема заключается в следующем:

  1. Для размещения предмета у персонажа есть шесть различных слотов для снаряжения.Это представлено 6 списками отдельных предметов для каждого слота в коде, содержащем все оборудование, принадлежащее игроку в целом.

  2. Программа рассчитает общую статистику персонажа для каждоговозможная комбинация снаряжения (по 1 из каждого списка).Эти рассчитанные характеристики могут быть отфильтрованы по определенным минимальным / максимальным значениям характеристик, а затем также отсортированы по определенным показателям для определения определенного целевого набора характеристик для их персонажа.

  3. Программа должна быть в состояниивыполнять эти запросы, не исчерпывая памяти или занимая часы, и, конечно же, основная проблема заключается в просеивании нескольких миллиардов возможных комбинаций.

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

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

Weapons List
|
-----Armor List
     |
     ------Helm List... etc

Каждый слой дерева будет содержать словарь каждого дочернего пути, который он может взять, содержащий идентификаторы 1 элемента из каждого списка и постепенно вычисляя статистику, данную персонажу (простое добавление статистикиот оружия + брони + руля, когда он пересекает дерево и так далее ...)

Когда любой стат с примененным фильтром мин / макс достигает его границы для этого стата (а именно, если он проходит черезмаксимум, прежде чем он достигнет нижнего слоя дерева, он исключает этот «путь» из словаря, тем самым удаляя весь отрезок возможных результатов от прохождения).

Основная цель здесь - сократить возможные пути деревабыть пройденным алгоритмом поиска и удалить как можно больше недействительных результатов, прежде чем дерево должно будет рассчитать их, чтобы сделать поиск максимально быстрым и избежать ненужных циклов.Это кажется довольно простым при удалении элементов, основанных на «максимальном» фильтре, поскольку при постепенном добавлении статистики каждого элемента мы можем быстро определить, когда статистика пересекла ожидаемый максимум - однако, когда речь идет об остановке путей на основе минимального общего показателя, яЯ не могу обернуть голову, как предсказать и удалить эти пути, которые не окажутся выше минимума шестым пунктом.

Чтобы упростить идею, подумайте о ней так:

У меня есть 3 массива чисел 

[X][0][1][2]
[0] 5  3  2
[1] 1  0  8 
[2] 3  2  7
[3] 2  1  0

Я хочу найти все комбинации из 3 массивов (сумм)) минимум 9 и максимум 11 всего.Каждый массив должен выбирать не менее 1 элемента, а сумма этих выбранных значений - это то, что ищется.Это должно было бы быть в состоянии масштабировать до поиска более 6 массивов по 40+ значений каждый по существу.Является ли приведенный выше подход правильным путем или как лучше всего это сделать (в основном с использованием c #)

1 Ответ

0 голосов
/ 20 сентября 2019

Вы должны иметь возможность отфильтровывать множество предметов, используя нижнюю и верхнюю границу для каждого слота: 

var minimum = slots.Sum(slot => slot.Minimum);
var maximum = slots.Sum(slot => slot.Maximum);

foreach (var slot in slots)
{
    var maxAvailable = maximum - slot.Maximum;
    var minAvailable = minimum - slot.Minimum;
    var filtered = slot.Items
         // If we choose the strongest item in all the other slots and it's still below the minimum
        .Where(item => item.Value + maxAvailable >= request.MinimumValue)
        // If we choose the weakest item in all the other slots and its still above the maximum
        .Where(item => item.Value + minAvailable <= request.MaximumValue);
}

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

...