Задача на определение min или max

Алгоритм поиска минимального или максимального значения среди элементов массива:

1. Первый элемент массива принимается в качестве максимального или минимального.

2. Просматривается весь массив. Все элементы сравниваются с зафиксированным. При невыполнении условия проверки новое значение принимается за экстремальное.

3. На выходе из массива имеем минимальное или максимальное значение.

 

Поскольку этот алгоритм исследует список по порядку, он ищет элементы в начале списка быстрее, чем элементы, находящиеся в конце. Поэтому наихудший случай этого алгоритма возникает, когда нужный элемент находится в конце списка или его вообще нет. Так как алгоритм исследует все элементы списка, время его выполнения в наихудшем случае составляет порядка О(N). Этот алгоритм дает неплохие результаты для небольших списков.

Метод двоичного поиска.

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

Индексы концов того интервала, в котором ищется целевое значение, хранятся в переменных min и max. Индекс искомого элемента всегда будет находиться между значениями. min и max, т.е. min <= индекс элемента <= max.

Во время каждого прохода алгоритм присваивает middle = (min+max)/2 и проверяет ячейку с индексом middle. Если ее значение равно целевому, то алгоритм завершает свою работу. Если же целевое значение меньше значения найденного среднего элемента, то переменной max присваивается значение на 1 меньшее, чем значение middle. Если целевое значение превышает значение среднего элемента, min присваивается middle + 1. Если нужное значение не найдено, То на каждой итерации цикла либо возрастает значение min, либо уменьшается значение max. Это означает, что их значения постепенно сближаются.

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

Searches = 0

Do while min <= max

Searches = Searches + 1 ‘ счетчик итераций

middle = (min+max)/2

if target = list(middle) Then ‘целевой элемент найден

Result = middle

End

Else If target < list(middle) then ‘перебираем левую половину

Max = middle - 1

Else ‘ перебираем правую половину.

Min = middle +1

Endif

EndIf

endWhile

Result = 0 ‘

 

Для списка размера N алгоритму потребуется максимум O(logN) шагов, чтобы найти любой элемент или определить, что его нет в писке. При этом двоичный поск работает намного быстрее, чем полный перебор. Полный перебор списка из миллиона элементов занимает в среднем 500 000 шагов. Алгоритм двоичного поиска потребуется максимум log(1 000 000), или 20 шагов.

Интерполяционный поиск

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

Интерполяция – это процесс предсказания неизвестных значений на основе имеющихся. В данном случае мы можем использовать индексы известных значений в списке, чтобы определит, какой индекс должно иметь искомое значение. Предположим, что есть список из 20 элементов со значениями от 1 до 70. Допустим, что мы хотим найти в этом списке элемент со значением 44. Значение 44 составляет 64% размера диапазона от 1 до 70. Если считать, что значения элементов распределены равномерно, то искомый элемент, предположительно, будет находиться в позиции, составляющей 64% от размера списка – то есть в позиции с индексом 13. Если найденная позиция неверна, то он сравнивает целевое значение со значением в выбранной позиции для поиска в первой части списка или во второй.

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

Двоичный следящий поиск. Сравнивается найденное значение из предыдущего поиска с новым искомым значением. Если новое значение меньше, то поиск будет слева, а если больше – справа. Значения min и max для выполнения слежения следует взять из предыдущего поиска.

Если поиск будет, например, слева, то устанавливается сначала min = min – 1 и сравнивается целевое значение с list(min). Если элемент все же меньше, устанавливается max = min, min = min – 2 и проводится сравнение с целевым и т.д.

По завершению фазы отслеживания уже известно, что индекс искомого элемента находится между min и max. После этого можно использовать обычный двоичный поиск для нахождения точной позиции элемента. Если новый элемент близко расположен к старому, алгоритм быстро найдет правильное значение. Если индексы нового и старого целевого значения отличаются на Р, поиск займет приблизительно log(P) шагов.

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

 

Динамическое программирование

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

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

«Жадные алгоритмы».

Пример. Пусть у нас есть монеты достоинством 25. 10 5 и 1 копейка. Нам нужна сдача в 63 коп. Мы возьмем две монеты по 25 коп, одну в 10 коп и три по 1 коп. В результате этого алгоритма выбрали монету самого большого достоинства, но не больше 63.Добавили ее в список сдачи. Вычли из 63 - 25 получили 38. снова выбрали монету самого большого достоинства но не больше 38 коп. Опять добавили в список сдачи. Производим вычитание и т.д.

Этот алгоритм называется «жадным». На каждой отдельной стадии «жадный алгоритм» выбирает тот вариант, который является локально оптимальным. («жадными» являются алгоритмы кратчайшего пути Дейкстры и т.д). Не каждый «жадный»алгоритм позволяет получить оптимальный результат в целом.. Как и в реальности «жадная стратегия» обеспечивает сиюминутную выгоду, в то время как в целом результат может оказаться неблагоприятным.

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

Поиск с возвратом.

Задачи поиска оптимального решения, когда нельзя применить ни один из известных методов, способных помочь отыскать оптимальный вариант решения, то остается последний способ - полный перебор. Определенные приемы позволяют сократить объем операций поиска.

ü Правильно выбирать границы значений перебираемых величин, т.е. оценивать реальные значения перебираемых величин.

ü При оптимизации решения надо отсекать заведомо неверные ветви перебора, т. е. Возвращаться на предыдущие этапы для поиска решения.

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

Любая задача, к которой применим алгоритм поиска с возвратом (бектрекинг), может быть описана в общем случае таким образом: требуется построить к данной задаче вектор решения (а₁, а₂,….., а _n), удовлетворяющий множеству условий и ограничений. Такой вектор строится покомпонентно слава направо. Предположим, что уже найдены значения первых k-1 компонент, а выбор следующей компоненты, а _k зависит о некоторых ограничений и условий. Если условия и ограничения выполнимы, то выбирается а _k и переходят к рассмотрению следующей компоненты а _k+1 , если же оказалось невозможным выбрать компоненту а _k, то необходимо вернуться к предыдущему этапу, выбросить (k-1)-й элемент и выбрать другой а _k-1 , перейдя после этого снова к выбору k-й компоненты. Такой перебор может возвращаться назад на несколько шагов, вплоть до выбора самой первой компоненты.

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

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

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