Сортировка массива в порядке возрастания при минимизации «стоимости»

Question

Я принимаю comp 2210 (Data Structures) в следующем семестре, и я делаю домашнее задание на летний семестр, который публикуется в Интернете. До сих пор у меня не было проблем с выполнением заданий. Взгляните на назначение 4 ниже и посмотрите, можете ли вы дать мне подсказку о том, как подойти к нему. Пожалуйста, не предоставляйте полный алгоритм, просто подход. Благодаря!

«Costed sort» - это алгоритм, в котором последовательность значений должна быть упорядочена в порядке возрастания. Сортировка осуществляется путем изменения положения двух значений по одному, пока последовательность не будет в правильном порядке. Каждый обмен несет стоимость, которая рассчитывается как сумма двух значений, участвующих в обмене. Общая стоимость стоимости сортировки - это сумма стоимости обменов.

Например, начальная последовательность была {3, 2, 1}. Одним из возможных серии развязок является

Interchange 1: {3, 1, 2} interchange cost = 0 
Interchange 2: {1, 3, 2} interchange cost = 4 
Interchange 3: {1, 2, 3} interchange cost = 5, 
given a total cost of 9 

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

Редактировать: Профессор не допускает грубой силы.

Answer 1

Если вы хотите удивить своего профессора, вы можете использовать Simulated Annealing. Опять же, если вы справитесь с этим, вы, вероятно, можете пропустить несколько курсов :). Обратите внимание, что этот алгоритм даст приблизительный ответ.

В противном случае: попробуйте алгоритм Backtracking, или Branch and Bound. Они найдут оптимальный ответ.

Answer 2

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

Answer 3

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

Answer 4

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

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

Answer 5

Что значит «скот»? Вы имеете в виду «попробовать все возможные комбинации и выбрать самый дешевый?» Просто проверяю.

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

Мой предпочтительный язык для этого был бы прологом, но я странный.

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

Вы также можете попробовать связанные генетические алгоритмы, если это так, как вы хотите.

Answer 6

Описание

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

Если глобально дешевый элемент не является неуместным, а разброс между этим самым дешевым и самым дешевым неудовлетворительным, он может быть дешевле поменять самый дешевый в своем правильном месте с самым дешевым неуместным. Стоимость тогда n-1 * самый дешевый + стоимость всего из-за места + стоимость самого дешевого места.

Пример

Для [4,1,2,3], этот алгоритм обмена (1,2) для получения:

[4,2,1,3] 

, а затем обменивает (3,1) с получением :

[4,2,3,1] 

, а затем обменивает (4,1) для получения:

[1,2,3,4] 

Обратите внимание, что каждый неуместный элемент в [2,3,4] перемещается только один раз и заменяется наименьшей стоимостью.

Код

по электронной почте Ой: "Пожалуйста, не предоставляют полный алгоритм, только подход." Удалено мой код.

Answer 7

Чтобы не допустить, чтобы это произошло, это может не иметь полного смысла.

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

Мне нравится решать такие вещи.

Answer 8

Эта проблема также известна как проблема Silly Sort в некоторых конкурсах ACM. Взгляните на this solution, используя Разделить & Conquer.