Сортировка списка номеров с измененной стоимостью

Question

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

Проблема: Числа в списке не отсортированы и поддерживают только один тип операции. Операция определяется следующим образом:

При заданной позиции i и позиции j операция перемещает число в позиции i в позицию j без изменения относительного порядка других чисел. Если i> j, позиции чисел между позициями j и i - 1 увеличиваются на 1, в противном случае, если i

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

Попытки: Часть нашего исследования была посвящена NP-полноте, мы решаем проблему и пытаемся найти подходящее преобразование к любой из проблем, перечисленных в книге Гэри и Джонсона: «Компьютеры и неразрешимость», но безрезультатно. Также нет прямой ссылки (с нашей точки зрения) на такого рода вариации в книге Дональда Кнута «Искусство компьютерного программирования», вып. 3 Сортировка и поиск. Мы также проанализировали алгоритмы для сортировки связанных списков, но ни один из них не дает хорошей идеи найти оптимальную последовательность движений.

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

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

Рекурсивный алгоритм грубой силы принимает все возможные комбинации движений от i до j, а затем снова все возможные моменты остальных элементов, в конце он возвращает последовательность с меньшей общей стоимостью, которая отсортировала список, как Вы можете себе представить, что стоимость этого алгоритма жестока и делает его неосуществимым для более чем 8 элементов.

Наши наблюдения:

• n движений не обязательно дешевле, чем n + 1 движений (в отличие от перестановок в массивах O (1)).

• Существует два основных способа перемещения одного элемента из положения i в j: один - перемещать его напрямую, а другой - перемещать другие элементы вокруг i таким образом, чтобы он достиг положения j.

• Самое большее, вы делаете n-1 движений (нетронутый элемент достигает своей позиции в одиночку).

• Если это оптимальная последовательность движений, то вы не перемещали один и тот же элемент дважды.

Answer 1

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

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

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

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

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

---

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

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

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

Теперь у нас есть все элементы, необходимые для включения проблемы в стандартный генетический алгоритм. Остальное просто дорабатывается. Много-много настроек.