Минимизировать функцию в соседних элементах массива

Что означает «такой, чтобы f (arr [i], arr [i + 1]) было как можно меньше для каждого i в arr»? Вы хотите минимизировать сумма? Вы хотите свести к минимуму самые большие из них? Вы хотите сначала минимизировать f (arr [0], arr [1]), а затем среди всех решений, которые минимизируют это, выберите то, которое минимизирует f (arr [1], arr [2]) и т. д., И так на?

Если вы хотите минимизировать сумма, это точно Задача коммивояжера в ее полной общности (ну, может быть, «метрическая TSP», если ваши f действительно образуют метрику). Есть хитроумные оптимизации наивного решения, которые дадут вам точный оптимум и будут работать в разумные сроки примерно в течение n = 30; вы можете использовать один из них или одну из эвристик, которые дают вам приблизительные значения.

Если вы хотите минимизировать максимум, это более простая задача, хотя и NP-трудная: вы можете выполнить двоичный поиск по ответу; для конкретного значения d нарисуйте ребра для пар, у которых f (x, y)

Если вы хотите минимизировать его лексиокографически, это тривиально: выберите пару с наименьшим расстоянием и поместите ее как arr [0], arr [1], затем выберите arr [2], которая ближе всего к arr [1], и так далее. .

В зависимости от того, откуда берутся ваши f (,), это может быть намного проще, чем TSP; Вам было бы полезно упомянуть и об этом.

Вам не совсем понятно, что вы оптимизируете - сумму значений f (a [i], a [i + 1]), максимальное из них или что-то еще?

В любом случае, с вашими ограничениями скорости, жадный, вероятно, ваш лучший выбор - выберите элемент, чтобы сделать [0] (не имеет значения, что из-за переноса), затем выберите каждый последующий элемент a [i + 1] для быть тем, который минимизирует f (a [i], a [i + 1]).

Это будет O (n ^ 2), но с 30 элементами, если только это не внутренний цикл или что-то еще, что будет нормально. Если ваш f () действительно ассоциативен и коммутативен, вы можете сделать это за O (n log n). Ясно, что не быстрее, если перейти к сортировке.

Я не думаю, что проблема четко определена в этой форме:

Вместо этого давайте определим n fcns g_i: Perms -> Reals

g_i(p) = f(a^p[i], a^p[i+1]), and wrap around when i+1 > n

Сказать, что вы хотите минимизировать ж по всем перестановкам, на самом деле подразумевает, что вы можете выбрать значение я и минимизировать g_i по всем перестановкам, но для любого п, который минимизирует g_i, связанное, но разные перматирование минимизирует перестановку g_j (просто сопряжение). Поэтому нет смысла говорить о минимизации f по перестановкам для каждого я.

Если мы не знаем больше о структуре f (x, y), это NP-трудная проблема. Для графа G и любых вершин x, y пусть f (x, y) равно 1, если ребра нет, и 0, если ребро есть. Задача задает такой порядок вершин, чтобы максимальное значение f (arr [i], arr [i + 1]) было минимальным. Поскольку для этой функции это может быть только 0 или 1, возврат 0 эквивалентен поиску гамильтонова пути в G, а 1 означает, что такого пути не существует.

Функция должна иметь какую-то структуру, которая не позволяет этому примеру быть управляемой.