Я считаю, что мы можем свести содержащуюся проблему максимального многообразия к логической удовлетворяемости и показать NP-полноту с помощью любого зависимость от этой подзадачи. Из-за этого предоставленные алгоритмы spinning_plate приемлемы в качестве эвристики, предварительные вычисления и машинное обучение разумны, и уловка сводится к поиску наилучшего эвристического решения, если мы хотим сделать здесь грубую ошибку.
Рассмотрим такую доску:
..S........
#.#..#..###
...........
...........
..........F
Это имеет множество проблем, которые приводят к сбою жадных и привязанных к воротам решений. Если мы посмотрим на этот второй ряд:
#.#..#..###
Наши логические элементы расположены в двумерном массиве с нулевым значением, отсортированном как [row][column]:
[1][4], [1][5], [1][6], [1][7], [1][8]
Мы можем перерисовать это как уравнение, чтобы удовлетворить блок:
if ([1][9] AND ([1][10] AND [1][11]) AND ([1][12] AND [1][13]):
traversal_cost = INFINITY; longest = False # Infinity does not qualify
Исключая бесконечность как неудовлетворительный случай, мы возвращаемся назад и передаем это как:
if ([1][14] AND ([1][15] AND [1][16]) AND [1][17]:
traversal_cost = 6; longest = True
И наши скрытые логические отношения попадают в эти ворота. Вы также можете показать, что геометрические доказательства не могут фрактализироваться рекурсивно, потому что мы всегда можем создать стену ровно N-1 ширины или высоты, и это представляет собой важную часть решения во всех случаях (следовательно, разделяй и властвуй вам не поможет).
Кроме того, поскольку отклонения в разных строках значительны:
..S........
#.#........
...#..#....
.......#..#
..........F
Мы можем показать, что без полного набора вычислимых геометрических тождеств полное пространство поиска сводится к N-SAT.
В дальнейшем мы также можем показать, что это тривиально для проверки и неполиномиально для решения, когда количество ворот приближается к бесконечности. Неудивительно, что именно поэтому игры в жанре Tower Defense остаются такими увлекательными для людей. Очевидно, желательно более строгое доказательство, но это лишь скелет.
Обратите внимание, что вы можете значительно уменьшить число n в соотношении n-select-k. Поскольку мы можем рекурсивно показать, что каждое возмущение должно лежать на критическом пути, и поскольку критический путь всегда вычислим за время O (V + E) (с некоторыми оптимизациями для ускорения работы для каждого возмущения), вы можете значительно уменьшить свои область поиска за счет поиска в ширину каждой дополнительной башни, добавленной на доску.
Поскольку мы можем допустить O (n ^ k) для детерминированного решения, эвристический подход является разумным. Таким образом, мой совет находится где-то между ответом spinning_plate и Soravux, посвященный методам машинного обучения, применимым к этой проблеме.
Нулевое решение: используйте приемлемый, но неоптимальный ИИ, в котором spinning_plate предоставляет два пригодных для использования алгоритма. На самом деле, это приблизительное количество наивных игроков, подходящих к игре, и этого должно быть достаточно для простой игры, хотя и с высокой степенью использования.
Решение 1-го порядка: Используйте базу данных. Учитывая формулировку проблемы, вы не совсем продемонстрировали необходимость вычислять оптимальное решение на лету. Следовательно, если мы ослабим ограничение приближения к случайной плате без информации, мы можем просто предварительно вычислить оптимум для всех K допустимых значений для каждой платы. Очевидно, это работает только для небольшого числа плат: с V! потенциальными состояниями платы для каждой конфигурации мы не можем терпимо предварительно вычислить все оптимумы, поскольку V становится очень большим.
Решение 2-го порядка: используйте этап машинного обучения. Продвигайте каждый шаг по мере того, как вы закрываете пробел, который приводит к очень высокой стоимости обхода, до тех пор, пока ваш алгоритм не сойдется или не будет найдено более оптимальное решение, чем жадное. Здесь применимо множество алгоритмов, поэтому я рекомендую преследовать классику и литературу для выбора правильного который работает в рамках ограничений вашей программы.
Лучшая эвристика может быть простой тепловой картой, созданной локальным рекурсивный обход в глубину с учетом состояния, сортировка результатов по наиболее или менее часто просматриваемым после обхода O (V ^ 2). Просматривая этот вывод, вы жадно идентифицируете все узкие места, и сделать это, не сделав пути невозможным, вполне возможно (проверка на O (V + E)).
Собирая все вместе, я бы попробовал пересечь эти подходы, объединив тепловую карту и идентификационные данные критического пути. Я предполагаю, что здесь достаточно, чтобы предложить хорошее функциональное геометрическое доказательство, удовлетворяющее всем ограничениям задачи.
person
MrGomez
schedule
01.05.2012
