Моделирование процессов. Презентация. Методы разработки алгоритмов
 Скачать 167.66 Kb.
|
Методы разработки алгоритмов
Метод грубой силыМетод грубой силы - прямолинейный подход к решению задачи, обычно основанный только на постановке задачи и определениях используемых в ней понятий.Поиск с возвратом -Улучшенная версия исчерпывающего перебора, которая пытается избежать ложных потенциальных решений путём отбрасывания частично построенных кандидатов, которые не могут привести к правильному решению задачи. Поиск с возвратом Метод уменьшения размера задачи может быть определен как подход, который использует связь между решением задачи данного размера и решением той же задачи меньшего размера. · может быть применен либо сверху вниз, то есть рекурсивно, либо снизу вверх, то есть итеративно · также известен под именем «индуктивный подход» Метод декомпозиции можно определить как метод, который рекурсивно делит задачу на несколько подзадач, до тех пор пока они становятся достаточно простыми для прямого решения. Затем эти решения подзадач объединяются , чтобы получить решение первоначальной задачи Метод преобразования Преобразовать · в более простой случай той же задачи · в другую форму той же задачи · в другую задачу с известным решениемЖадный метод – это подход к решению задач оптимизации, в которых на каждом шагу делается выбор, который · удовлетворяет всем ограничениям задачи; · локально оптимален; · необратим. Динамическое программирование В теории оптимизации этот подход интерпретируется как метод решения оптимизационных задач, которые удовлетворяют принципу оптимальности. В информатике ДП интерпретируется как подход к решению задач с пересекающимися подзадачами, не обязательно оптимизационного характера: − решите все меньшие подзадачи, но один раз; − занесите решения в таблицу; − возьмите решение для нужного случая из этой таблицы. Метод ветвей и границ 1) Улучшение поиска с возвратом для оптимизационных задач 2) Для каждого узла (частично построенного решения) в дереве пространства состояний метод вычисляет оценку величины оптимизируемой функции во всех потомках этого узла (расширений этого частичного решения) 3) Оценка используется для · отбрасывания бесперспективных вершин · определения порядка построения дерева (узел с лучшей оценкой обычно исследуется раньше остальных) |