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

Question

У меня есть массив ( arr ) элементов и функция ( f ), которая принимает 2 элемента и возвращает число.

Мне нужна перестановка массива, чтобы f (arr [i], arr [i + 1]) было как можно меньше для каждого i в <код> обр . (и он должен зацикливаться, т.е. он также должен минимизировать f (arr [arr.length - 1], arr [0]) )

Кроме того, f работает примерно как расстояние, поэтому f (a, b) == f (b, a)

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

Answer 1

Что означает, что 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; было бы полезно упомянуть и это.

Answer 2

Вам не совсем понятно, что вы оптимизируете - сумма значений 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). Понятно, не быстрее за счет сортировки.

Answer 3

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

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

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

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

Answer 4

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

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