Сортировка массива с минимальными затратами

Question

У меня есть массив A [] с 4 элементами A = { 8 1 2 4}. Как отсортировать с минимальными затратами. Критерии определены следующим образом -

а. Можно поменять местами любые 2 элемента.

б. Стоимость любого свопа равна сумме значения элемента. Например, если я поменяю местами 8 и 4, то стоимость равна 12, результирующий массив выглядит как A = {4 1 2 8}, который все еще не отсортирован, поэтому требуется больше свопа.

с. Нужно найти способ сортировки массива с минимальными затратами.

По моим наблюдениям, жадность не сработает, так как на каждом шаге размещайте любой элемент в его отсортированной позиции в массиве с минимальными затратами. Таким образом, требуется решение DP. Может ли кто-нибудь помочь ??

Answer 1

Поменяйте местами 2 и 1, затем 1 и 4, а затем 1 и 8? Или это общий вопрос?

Для более общего подхода вы можете попробовать:

1. Поменяйте местами каждую пару из 2 элементов (с наибольшей суммой), если они являются идеальными свопами (т. Е. Поменяв их, вы поместите их в правильное место). Th

2. Используйте самый низкий элемент в качестве разворота для свопов (путем замены элемента, место которого он занимает), пока он не достигнет своей конечной точки

3. Тогда у вас есть две возможности:

   1. Повторите шаг 2: используйте самый нижний элемент, не находящийся на последнем месте, в качестве точки поворота, пока он не достигнет своего последнего места, затем вернитесь к шагу 3

   2. Или поменяйте местами самый низкий элемент, не находящийся в его последней точке (l2), с самым низким элементом (l1), повторяйте шаг 2, пока l1 не достигнет конечной точки l2. Тогда:

      1. Либо поменяйте местами l1 и l2, перейдите к шагу 3.1
      2. Или снова перейдите к шагу 3.2, когда следующий самый младший элемент не находится в своем последнем месте.

Когда все это будет сделано, если некоторые противоположные перестановки будут выполняться один за другим (например, это может произойти при переходе к шагу 2. - к шагу 3.2.), Удалите их.

Есть еще некоторые вещи, на которые стоит обратить внимание, но это уже довольно хорошее приближение. Шаг первый и второй всегда должны работать, хотя шаг третий может быть улучшен в некоторых пограничных случаях.

Пример используемого алгоритма:

С {8 4 5 3 2 7}: (целевой массив {2 3 4 5 7 8})

• Шаг 2: 2 <> 7, 2 <> 8

• Массив теперь {2, 4, 5, 3, 7, 8}

• Выбор между 3,1 и 3,2:

  • 3.1 дает 3 <> 5, 3 <> 4

  • 3.2 дает 2 <> 3, 2 <> 5, 2 <> 4, 2 <> 3

  • 3 <> 5, 3 <> 4 - лучший результат

Вывод: 2 <> 7, 2 <> 8, 3 <> 5, 3 <> 4 - лучший ответ.

С {1 8 9 7 6} (результирующий массив {1 6 7 8 9})

• Вы уже начинаете с третьего шага

• Выбор между 3,1 и 3,2:

  • 3.1 дает 6 <> 9, 6 <> 7, 6 <> 8 (всего: 42)

  • 3.2 дает 1 <> 6, 1 <> 9, 1 <> 7, 1 <> 8, 1 <> 6 (всего: 41)

Итак, 1 <> 6, 1 <> 9, 1 <> 7, 1 <> 8, 1 <> 6 - лучший результат

Answer 2

Это пахнет домашней работой. То, что вам нужно сделать, это отсортировать массив, но сделать это при минимальной стоимости свопов. Так что это скорее проблема оптимизации, чем проблема сортировки.

Жадный алгоритм, несмотря на эту работу, все, что вы делаете, это исправляете решение, сначала меняя самое дешевое (выясняя, где в списке оно принадлежит). Это, однако, не обязательно оптимально.

Пока вы никогда не меняете один и тот же элемент дважды, жадный алгоритм должен быть оптимальным.

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

Если вы используете более сложный алгоритм сортировки, вам будет гораздо сложнее ломать голову над этим вместе с динамическим программированием, поэтому я предлагаю вам начать с простой, медленной O(n^2) сортировки. И надстройка над этим.

Вместо того, чтобы предоставить вам решение, я бы хотел объяснить своими словами, как работает динамическое программирование.

• Первое, что вам нужно сделать, - это найти алгоритм, который изучит все возможные решения (это может быть очень глупый алгоритм грубой силы).
• Затем вы реализуете это с помощью рекурсии, потому что динамическое программирование основано на способности быстро находить перекрывающиеся подзадачи, т.е. на рекурсии.
• При каждом рекурсивном вызове вы смотрите, где вы находитесь в своем решении, и проверяете, где вы ранее вычисляли эту часть дерева решений. Если вы сделали это, вы можете проверить, является ли текущее решение более оптимальным. , если это так, вы продолжаете, в противном случае вы закончили с этой веткой проблемы.
• Когда вы придете к окончательному решению, вы решите проблему.

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

Вот что я рекомендую вам сделать:

1. Написать алгоритм рекурсивной сортировки
2. Добавьте параметр в вашу рекурсивную функцию, который поддерживает стоимость этого пути выполнения, при сортировке массива добавьте к этой стоимости. Для каждого возможного свопа в любой заданной точке выполните другой рекурсивный вызов (это ответвит ваше дерево решений)
3. Всякий раз, когда вы понимаете, что стоимость решения, которое вы в настоящее время изучаете, превышает ту, что у вас уже есть где-то еще, прервите (просто верните).

Чтобы иметь возможность ответить на последний вопрос, вам необходимо поддерживать разделенную область памяти, в которой вы можете индексировать в зависимости от того, где вы находитесь, ваш рекурсивный алгоритм. Если есть предварительно рассчитанная стоимость, вы просто возвращаете это значение и не продолжаете обработку (это сокращение, которое делает его быстрым).

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

Удачи!

Answer 3

Если вы выполняете сортировку с высоким-низким уровнем выбора, вы можете гарантировать, что N-й наибольший элемент не будет заменен более чем в N раз. Это простой алгоритм с довольно простой и заманчивой гарантией ... Может быть, проверьте это на нескольких примерах и посмотрите, как его можно настроить. Примечание: это не может привести к оптимальному ответу ...

Answer 4

Чтобы найти абсолютную минимальную стоимость, вам нужно попробовать все способы обмена, а затем найти самый быстрый.

def recsort(l, sort):
  if sorted(l2):
    if min>cost:
      cost=min
      bestsort=sort
  if(len(sort) > len(l)*len(l)): //or some other criteria
    return

  for p1 in (0,len(l)):
    for p2 in (0,len(l)):
      cost += l[p1] + l[p2]
      l2 = swap(l, p1,p2)
      if cost<min:
        recsort(l2, append sort (p1,p2))

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