Сокращение временной сложности этого алгоритма

Ответ 1

Начните с memoizing в решении грубой силы, т.е. выполните сортировку source_weapons, сделайте ее хешируемой (например, конвертируйте в строку путем соединения с запятыми) и посмотрите он отображается на карте пар ввода/вывода. Если его нет, выполните вычисления как обычно и добавьте результат в карту. Это часто приводит к большим выигрышам за небольшие усилия.

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

Если линейное программирование является опцией, тогда существуют систематические способы обрезания деревьев поиска. В частности, пусть облегчит проблему (i), позволяя бесконечную поставку "катализаторов" (может быть, не нужна здесь?) (ii) допускает "дробную" ковку, например, если X + Y = > Z, то 0,5 X + 0,5 Y = > 0,5 Z. Затем имеется формула LP следующим образом. Для всех i + j => k (i и j forge k) переменная x_{ijk} - это количество раз, когда выполняется эта кузница.

minimize sum_{i, j => k} x_{ijk} (to prevent wasteful cycles)
for all i:   sum_{j, k: j + k => i} x_{jki}
           - sum_{j, k: j + i => k} x_{jik}
           - sum_{j, k: i + j => k} x_{ijk} >= q_i,
for all i + j => k: x_{ijk} >= 0,

где q_i - 1, если i - элемент цели, иначе минус количество i, изначально доступное. Для этой простой версии есть эффективные решатели. Так как реакции всегда 2 = > 1, вы всегда можете восстановить допустимый график ковки для целочисленного решения. Соответственно, я бы рекомендовал целочисленное программирование для этой проблемы. Этот пункт может по-прежнему представлять интерес.

Я знаю, что судоходство с решателем LP может быть неудобным, поэтому здесь прозрение, которое позволит вам обойтись без него. Этот LP возможен тогда и только тогда, когда его двойственный ограничен. Интуитивно двойственная проблема заключается в том, чтобы назначить "значение" для каждого элемента таким образом, чтобы, как бы вы ни подделывали, общая стоимость вашего инвентаря не увеличивается. Если предмет цели оценивается больше, чем доступный инвентарь, то вы не можете его подделать. Вы можете использовать любой метод, который вы можете придумать для назначения этих значений.

Ответ 2

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

Например, рассмотрим проблему нахождения максимального числа независимых строк в двоичной матрице.
Это известная проблема NP-complete (например, демонстрируя эквивалентность максимальной независимой задаче установки).

Мы можем уменьшить эту проблему до вашего вопроса следующим образом:

Мы можем начать удерживать одно оружие для каждого столбца в двоичной матрице, и тогда мы представляем, что каждая строка описывает альтернативный способ создания нового оружия (например, боевой топор). Мы строим таблицу переводов оружия таким образом, чтобы сделать боевой топор с использованием метода i, нам нужно все оружие j, такое, что M [i, j] равно 1 (это может быть связано с изобретением дополнительного оружия).

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

Например, мега боевой топор может потребовать объединения четырех боевых осей.

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

Ответ 3

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

Итак, если вы добавили чек, если result_weapon был того же типа, что и один из входов, и не пошел вперед и рекурсивно вызвал find_possible_weapons (new_weapons), вы немного обрезали бы поиск.

Другое, что я мог придумать, это то, что вы не отслеживаете работу, поэтому, если возвращение из find_possible_weapons (new_weapons) возвращает то же оружие, которое у вас уже есть, объединив другое оружие, вы вполне можете выполнить одна и та же ветвь поиска несколько раз.

например. если у вас есть a, b, c, d, e, f, g и если a + b = x и c + d = x, тогда вы будете выполнять два массива сравнения x с e, f и g, Поэтому, если вы будете отслеживать то, что вы уже вычислили, вы станете победителем...

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

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

Ответ 4

Возможно, вам захочется начать с создания матрицы Weapon [] [], чтобы показать результаты подделывания каждой пары. Вы можете сопоставить имя оружия с индексом оси матрицы, и поиск результатов комбинации оружия будет происходить в постоянное время.