Главная страница
Навигация по странице:

  • Метод грубой силы

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

  • Метод декомпозиции

  • Метод преобразования

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

  • Метод ветвей и границ

  • Моделирование процессов. Презентация. Методы разработки алгоритмов


    Скачать 167.66 Kb.
    НазваниеМетоды разработки алгоритмов
    АнкорМоделирование процессов
    Дата17.06.2022
    Размер167.66 Kb.
    Формат файлаpptx
    Имя файлаПрезентация.pptx
    ТипДокументы
    #599876

    Методы разработки алгоритмов

    • · метод грубой силы
    • · поиск с возвратом
    • · уменьшение размера задачи
    • · декомпозиция
    • · преобразование
    • · жадные алгоритмы
    • · итеративное улучшение
    • · динамическое программирование
    • · метод ветвей и границ

    Метод грубой силы

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


    Поиск с возвратом -Улучшенная версия исчерпывающего перебора, которая пытается избежать ложных потенциальных решений путём отбрасывания частично построенных кандидатов, которые

    не могут привести к правильному решению задачи.

    Поиск с возвратом
    Метод уменьшения размера задачи может быть определен как подход, который использует связь между решением задачи данного размера и решением той же задачи меньшего размера. · может быть применен либо сверху вниз, то есть рекурсивно, либо снизу вверх, то есть итеративно · также известен под именем «индуктивный подход»
    Метод декомпозиции можно определить как метод, который рекурсивно делит задачу на несколько подзадач, до тех пор пока они становятся достаточно простыми для прямого решения. Затем эти решения подзадач объединяются , чтобы получить решение первоначальной задачи

    Метод преобразования Преобразовать · в более простой случай той же задачи · в другую форму той же задачи · в другую задачу с известным решением


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

    · удовлетворяет всем ограничениям задачи;

    · локально оптимален;

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


    написать администратору сайта