Переборные алгоритмы

Переборные алгоритмы
Информатика, 10-11 класс
Ознакомление с методами выбора оптимального решения, с понятием переборного алгоритма.

Переборные алгоритмы
КАК ПРИНЯТЬ ПРАВИЛЬНОЕ РЕШЕНИЕ ?
использовать опыт других людей?
интуитивно
Использовать алгоритмы
?

Переборные алгоритмы
Сенека
Для корабля, который не знает куда плыть, нет попутного ветра.

Переборные алгоритмы
Задача имеет n вариантов возможных решений. Как найти и выбрать лучшее?
Можно найти алгоритм улучшенного ПЕРЕБОРА, когда конструируется сразу наилучшее решение
Один способ есть всегда - перебрать ВСЕ варианты.

Переборные алгоритмы
Как сформулировать понятие "хорошее решение"?
Чем ”хорошее” решение отличается от “плохого”?
Как можно найти "хорошее" решение, если допустимых решений конечное число?
Почему метод полного перебора всех решений для нахождения наилучшего невыгодно использовать?
Можно ли ускорить метод полного перебора?
Направляющие вопросы

Переборные алгоритмы
Работа по группам
Группа разработчиков модели
Группа историков
Группа, демонстрирующая работу алгоритма

Переборные алгоритмы
Построить схему возможных маршрутов из пункта А в пункт В:
Группа 1: «разработчики модели»
пример
назад

Переборные алгоритмы
1) А: школа, В: стадион «Уралан»
Модель задачи
Пример решения
Схема города

Переборные алгоритмы
Собрать сведения об авторах алгоритмов улучшенного перебора:
Группа 2: «историки»
назад

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

Переборные алгоритмы
найти кратчайший путь из вершины 1 в вершину 6 методом перебора
Задание для всех групп: