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