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

Question

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

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

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

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

Answer 4

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

Давайте вместо этого определим 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 .