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

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

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

Например, предположим, что начальный последовательность была {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

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

Изменить: Профессор не допускает грубой форсировки.

Ответ 1

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

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

Ответ 2

Что вы подразумеваете под "грубой силой"? Вы имеете в виду "попробовать все возможные комбинации и выбрать самый дешевый?" Просто проверьте.

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

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

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

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

Описание

Я думаю, что самый дешевый способ сделать это - поменять дешевый неулокальный предмет на предмет, который принадлежит его месту. Я считаю, что это снижает стоимость, перемещая самые дорогие вещи только один раз. Если есть 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] перемещается только один раз и заменяется наименьшей стоимостью.

код

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

Ответ 6

В попытке только заставить вас это делать, это может не иметь полного смысла.

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

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

Ответ 7

Эта проблема также известна как проблема Silly Sort в некоторых конкурсах ACM. Посмотрите это решение, используя Divide и Conquer.

Ответ 8

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