Содержание
- 2. Постановка задачи Интересная область программирования— задачи так называемого «искусственного интеллекта»: ищем решение не по заданным правилам
- 3. Задача о ходе коня Дана доска размером n*n. Вначале на поле с координатами (х0, у0) помещается
- 5. Алгоритм выполнения очередного хода Try(int i) { инициализация выбора хода; do выбор очередного хода из списка
- 6. Выбор представления данных Доску можно представлять как матрицу h: h [х][ у] = 0 – поле
- 7. Выбор параметров Параметры должны определять начальные условия следующего хода и результат (если ход сделан). В первом
- 8. Конкретизация схемы int Try(int i, int х, int у) { int u,v; int q = 0;
- 9. Выбор ходов Полю с координатами (х0,у0) присваивается значение 1, остальные поля помечаются как свободные. Если задана
- 10. Ниже приведен фрагмент доски. Конь K стоит в позиции (x, y). Клетки с цифрами вокруг K
- 11. Правило Варнсдорфа, 1823 На каждом ходу ставь коня на такое поле, из которого можно совершить наименьшее
- 12. Задача о восьми ферзях Задача о восьми ферзях — хорошо известный пример использования методов проб и
- 13. Пример
- 14. Схема нахождения всех решений (n – количество шагов, m – количество вариантов на каждом шаге) Try(int
- 15. Задача о стабильных браках Имеются два непересекающихся множества А и В. Нужно найти множество пар ,
- 16. Алгоритм поиска супруги для мужчины m Поиск ведется в порядке списка предпочтений именно этого мужчины. Try(int
- 17. Выбор структур данных Будем использовать две матрицы, задающие предпочтительных партнеров для мужчин и женщин: ForLady и
- 18. Конкретизация схемы Предикат “подходит” можно представить в виде конъюнкции single и stable, где stable — функция,
- 19. Стабильность системы Мы пытаемся определить возможность брака между m и w, где w стоит в списке
- 20. 1) Исследуя первый источник неприятностей, мы сравниваем ранги женщин, которых m предпочитает больше w. Мы знаем,
- 21. Задача о кубике Задано описание кубика и входная строка. Можно ли получить входную строку, прокатив кубик?
- 22. Результат ( в переменной q) 1, если можно получить слово, записанное в глобальной строке w, начиная
- 23. Нахождение оптимальной выборки (задача о рюкзаке) Пусть дано множество вещей {x1, x2, x3, …xn}. Каждая i-я
- 24. Схема перебора всех решений и выбора оптимального Try(int i) { if (включение приемлемо) { включение i-го
- 25. Метод ветвей и границ — метод для нахождения оптимальных решений различных задач оптимизации. Метод — есть
- 26. Дерево поиска В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на
- 27. Использование метода ветвей и границ для решения задачи о рюкзаке Пусть в переменной оптимум будет храниться
- 29. Скачать презентацию