Массив вида в порядке возрастания, в то время как уменьшение “стоится”
Вы не можете положиться на navigator.userAgent, не каждое устройство показывает свою настоящую ОС. На моем HTC например это зависит от настроек ("использование мобильной версии" вкл / выкл). На http://my.clockodo.com мы просто использовали screen.width для обнаружения небольших устройств. К сожалению, в некоторых версиях Android есть ошибка с screen.width. Вы можете комбинировать этот способ с userAgent:
if(screen.width < 500 ||
navigator.userAgent.match(/Android/i) ||
navigator.userAgent.match(/webOS/i) ||
navigator.userAgent.match(/iPhone/i) ||
navigator.userAgent.match(/iPod/i)) {
alert("This is a mobile device");
}
7 ответов
Если вы хотите удивить своего профессора, вы можете использовать Simulated Annealing . Опять же, если вам это удастся, вы, вероятно, можете пропустить несколько курсов :). Обратите внимание, что этот алгоритм даст только приблизительный ответ.
В противном случае: попробуйте алгоритм Backtracking или Branch and Bound . Они оба найдут оптимальный ответ.
Вы выучили деревья? Вы можете создать дерево со всеми возможными изменениями, которые приведут к желаемому результату. Уловка, конечно же, состоит в том, чтобы не создавать все дерево целиком - особенно когда его часть явно не лучшее решение, верно?
Что вы имеете в виду «грубая форсировка»? Вы имеете в виду «попробовать все возможные комбинации и выбрать самую дешевую»? Просто проверяю.
Я думаю, что "ветвление и граница" - это то, что вы ищете - проверьте любой источник по алгоритмам. Это похоже на грубую силу, за исключением того, что вы пробуете последовательность ходов, как только эта последовательность ходов будет менее оптимальной, чем любая другая последовательность ходов, испробованных до сих пор, вы можете отказаться от последовательности, которая привела вас к этой точке - Стоимость. Это одна из разновидностей упомянутого выше "обратного отслеживания".
Я предпочитаю для этого язык Prolog, но я странный.
Simulated Annealing - это ВЕРОЯТНЫЙ алгоритм - если пространство решений имеет локальные минимумы, тогда вы можете попасть в ловушку одного и получить то, что, по вашему мнению, является правильным ответом, но это не так. Есть способы обойти это, и всю литературу об этом можно найти, но я не согласен, что это тот инструмент, который вам нужен.
Если хотите, можете попробовать и соответствующие генетические алгоритмы.
Я думаю, что правильный подход - это хорошенько подумать о том, какие определяющие свойства имеет сортировка с минимальной «стоимостью». Затем рассчитайте стоимость, смоделировав эту идеальную сортировку. Ключевым элементом здесь является то, что вам не нужно реализовывать общий алгоритм сортировки с минимальной стоимостью.
Например, скажем, определяющим свойством сортировки с минимальной стоимостью является то, что каждый обмен помещает по крайней мере один из обмениваемых элементов в свой отсортированный положение (не знаю, правда ли это). Каждой сортировке, основанной на обмене, хотелось бы иметь это свойство, но в общем случае это непросто (возможно?). Однако вы можете легко создать программу, которая принимает несортированный массив, принимает отсортированную версию (которая сама может быть сгенерирована неоптимальным алгоритмом),
Описание
Я думаю, что самый дешевый способ сделать это - обменять самый дешевый потерянный предмет на предмет, который находится на его месте . Я считаю, что это снижает затраты, поскольку самые дорогие вещи перемещаются всего один раз. Если есть 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] перемещается только один раз и заменяется элементом с наименьшей стоимостью.
] Код
Упс: «Пожалуйста, не предоставляйте полный алгоритм, только подход». Мой код удален.
Это может не иметь полного смысла только для того, чтобы вы начали это делать.
Определить все возможные ходы, стоимость каждого хода и их каким-то образом сохранить, выполнить наименее затратный ход, затем определить ходы, которые могут быть выполнены из этого варианта, сохранить их вместе с остальными вашими сохраненными ходами, выполнить наименее затратное и т. д., пока массив отсортирован.
Я люблю решать подобные вещи.
Попробуйте разные алгоритмы сортировки для одних и тех же входных данных и выведите минимум.