Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 10 лет назад пользователемВиктор Гонохов
1 Приёмы сокращения перебора Метод ветвей и границ Динамическое программирование
2 Числа Фибоначчи f(0)=f(1)=1 f(n)=f(n-1)+f(n-2), при n>1 n f(n)
3 Динамическое программирование Задача. Найти количество кратчайших путей из левого верхнего в правый нижний угол. c[i,j] = c[i-1,j] + c[i,j-1]
4 Сокращение перебора За счёт симметрии задачи Метод ветвей и границ Задача раскраски графа int colors[]; function paintGraph(int n, int k) { // раскрасить n первых вершин в k цветов if( n ) { // осталось раскрасить n вершин int i; for(i=1;i
5 Сокращение перебора Задача раскраски графа Сокращение перебора за счёт симметрии задачи int colors[]; int maxColor; function paintGraph(int n) { // раскрасить n первых вершин if( n ) { // осталось раскрасить n вершин int i; for(i=1;i maxColor) { maxColor++; paintGraph(n-1); maxColor--; } else paintGraph(n-1); } else { // получили раскраску if( maxColor < bestColorNumber ) { bestColorNumber= maxColor; saveColors(); }
6 Сокращение перебора Задача раскраски графа Метод ветвей и границ int colors[]; int maxColor; function paintGraph(int n) { // раскрасить n первых вершин if( n ) { // осталось раскрасить n вершин int i; int limit=min(bestColorNumber-1,maxColor+1); for(i=1;i maxColor) { maxColor++; paintGraph(n-1); maxColor--; } else paintGraph(n-1); } else { // получили раскраску if( maxColor < bestColorNumber ) { bestColorNumber= maxColor; saveColors(); }
7 Порядок перебора Имеет значение порядок в котором мы выбираем вершины Распространение ограничений
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.