Алгоритм оптимизации для списка последовательных ресурсов

Question

Учитывая список из 1 - 12, предполагая, что я использую каждое число каждые 10 минут, как максимизировать количество минут между близкими числами.

Другими словами, максимизируйте разницу между каждым значением в каждой точке списка.

Попытка максимизировать время между n & n + 1, но также и n & n + 2, и n & n + 3

1 рядом с 2 является худшим. 1 рядом с 12 было бы лучше, однако в конечном итоге это привело бы к более близким числам вниз по списку.

Например,

1 2 3 ... Не было бы оптимальным, потому что 1 и 2 разнесены всего на 10 минут. 1 12 2 11 ... Не будет оптимальным, потому что 1 и 2 разнесены всего на 20 минут. 1 5 9 2 6 ... Было бы более предпочтительно, потому что число находится дальше друг от друга.

Существует ли оптимальная дельта между каждой из них, которая может быть рассчитана с учетом количества элементов в списке?

Answer 1

Предполагая, что входные значения в наборе равномерно распределены, я бы порекомендовал использовать следующий подход для определения последовательности.

Пройдитесь по упорядоченным значениям, каждый раз выполняя количество значений X, где X определяется как общее количество значений / Phi. Представьте, что конец набора значений возвращается к началу.

Таким образом, для набора значений 1 - 12 вы должны иметь:

Х = 12 / Фи

X = 12 / 1,618 = 7,4

Округлить 7,4 до ближайшего целого числа, поэтому предположим, что X = 7.

Тогда ваша последовательность будет 1, 8, 3, 10, 5, 12, 7, 2, 9, 4, 11, 6

Чтобы определить (или оценить) насколько «максимизирована» эта последовательность, вы должны взять сумму следующего расчета для КАЖДОГО члена в наборе.

Для КАЖДОГО установленного элемента рассчитайте абсолютное значение разницы в «значении» между собой и каждым другим элементом, деленное на это «расстояние» до этого элемента. Например, для члена 8 в приведенной выше последовательности его оценка будет:

8,1 = | 8-1 | / 1 = 8

+ * * тысяча двадцать-один

8,3 = | 8-3 | / 1 = 5

+

8,10 = | 8-10 | / 2 = 1

+

8,5 = | 8-5 | / 3 = 1

+

8,12 = | 8-12 | / 4 = 1

+

...

Сделайте это для каждого участника набора и возьмите сумму, чтобы получить общий «балл». Чем выше оценка, тем более «развернутой» будет последовательность.

Answer 2

Похоже, что для любого положительного n наилучший ответ - нечетные числа в порядке возрастания, соединенные с четными числами в порядке возрастания.

С 1-12 у нас есть 1, 3, 5, 7, 9, 11, 2, 4, 6, 8, 10, 12. Между последовательными числами есть расстояние в час.

Реализация (Ruby)

def optimize_resources(n)
  answer = Array.new(n)
  for i in 1..n
    if i % 2 == 1
      answer[(i - 1) / 2] = i
    else
      answer[(n - 1) / 2 + i / 2] = i
    end
  end
  answer
end