Презентация Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло. онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло. абсолютно бесплатно. Урок-презентация на эту тему содержит всего 54 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Образование » Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло.
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:54 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.75 MB
- Просмотров:68
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Темы лекций Поиск с](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img1.jpg)
Содержание слайда: Темы лекций
Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло.
Метод ветвей и границ. Общая схема. Задача коммивояжера (ЗК).
Метод ветвей и границ. ЗК (продолжение). Приближенные решения.
Динамическое программирование. Идея и общая схема. Оптимальное умножение матриц.
Динамическое программирование. Оптимальные БДП. Хорошие БДП. Аналогии.
№3 слайд
![Продолжение Графы и структуры](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img2.jpg)
Содержание слайда: Продолжение
Графы и структуры данных. Задачи связности.
Остовные деревья графа. Алгоритм Краскала. Алгоритм ЯПД.
Непересекающиеся подмножества.
Обходы графа. Алгоритм Борувки для МОД.
МОД как приближение в ЗК. Двусвязные компоненты (применение обхода в глубину).
ПВГ в орграфах. Топологическая сортировка. Сильно связные компоненты.
Кратчайшие пути в графе (1).
Кратчайшие пути в графе (2).
№4 слайд
![Лабораторные работы и](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img3.jpg)
Содержание слайда: Лабораторные работы и курсовая работа
Задание 1.
Алгоритмы сортировки, частичного упорядочения, хеширования.
Задание 2.
Перебор с возвращением (Backtracking).
Задание 3.
Метод ветвей и границ
Задание 4.
Динамическое программирование.
Курсовая работа (КР): Алгоритмы на графах.
№8 слайд
![Общий алгоритм Решение вида a](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img7.jpg)
Содержание слайда: Общий алгоритм
Решение вида (a1, a2, a3, …, an)
n – конечно, но, вообще говоря, заранее не известно
ai Ai ;
Ai – конечное линейно упорядоченное множество
Исчерпываем все элементы множества A1A2A3…Ai
i = 0 ()
i = 1; S1 A1; a1 S1; () (a1)
i = 2; S2 A2; a2 S2; (a1) (a1, a2)
…
i = k; Sk Ak; ak Sk; (a1,…, ak-1) (a1,…, ak-1,ak)
При Sk = backtrack и новый выбор ak-1 Sk-1;
№10 слайд
![Общий алгоритм S А k count](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img9.jpg)
Содержание слайда: Общий алгоритм
S1 = А1; k = 1; count = 0;
while (k>0) { //пока не все решения найдены
while (Sk != ) {
// продвижение вперед
ak = элемент из Sk; //выбор очередного элемента из Sk
Sk = Sk {ak};
count ++;
if ((a1,…, ak-1,ak) – решение) { /*фиксировать решение*/}
else {
// переход к следующему уровню
k ++;
вычислить Sk;
}
} // end while продвижения вперед
k --; // backtrack
} //все решения найдены; count – число обследованных узлов
№15 слайд
![Ak , , ,n номера клеток](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img14.jpg)
Содержание слайда: Ak = (1, 2, …,n) – номера клеток вертикалей.
Ak = (1, 2, …,n) – номера клеток вертикалей.
Множество Sk явно не формируется,
но, выбирая очередного кандидата k Ak, проверяем k Sk
Используется sk - нижняя граница в Ak,
т.о. кандидаты в Sk выбираются из множества
(sk, sk+1, …, n) , т.е. Sk (sk, sk+1, …, n).
Обсудить альтернативу.
№17 слайд
![Проверка s k bool noQueen uns](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img16.jpg)
Содержание слайда: Проверка s[k]
bool noQueen (uns s, uns k)
// ферзь не может быть поставлен в строку s столбца k
{ bool Flag = true;
uns i = 1;
while ((i<k) && Flag) {
// Flag='ферзи [1..i) не атакуют поле <k,s>'
// атакует ли ферзь из i-го столбца поле <k,s>?}
Flag = !( (a[i]==s) || (abs(a[i]-s)== k-i) );
i++;
} //end - while
return (!Flag);
} // end noQueen
№20 слайд
![while k gt while k gt while k](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img19.jpg)
Содержание слайда: while (k>0) {
while (k>0) {
while ((k>=1) && (s[k]<=n)) {
a[k]= s[k]; s[k]++;
// найти следующее наименьшее значение s[k]
while ((s[k]<=n) && noQueen (s[k],k)) s[k]++;
count++;
if (k==n) {countS++; …} //решение найдено - фиксировать !
else {// переход к следующей вертикали
k++;
s[k]= 1;
//найти следующее наименьшее значение s[k],
while ((s[k]<=n) && noQueen (s[k],k)) s[k]++;
}
}
k--; // backtrack
}
№28 слайд
![количество ферзей количество](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img27.jpg)
Содержание слайда: количество ферзей = 8
количество ферзей = 8
р е ш е н и я :
1 :: 2 4 6 8 3 1 7 5
2 :: 2 5 7 1 3 8 6 4
3 :: 2 5 7 4 1 8 6 3
4 :: 2 6 1 7 4 8 3 5
5 :: 2 6 8 3 1 4 7 5
6 :: 2 7 3 6 8 5 1 4
7 :: 2 7 5 8 1 4 6 3
8 :: 2 8 6 1 3 5 7 4
9 :: 3 1 7 5 8 2 4 6
10 :: 3 5 2 8 1 7 4 6
11 :: 3 5 2 8 6 4 7 1
12 :: 3 5 7 1 4 2 8 6
13 :: 3 5 8 4 1 7 2 6
14 :: 3 6 2 5 8 1 7 4
15 :: 3 6 2 7 1 4 8 5
16 :: 3 6 2 7 5 1 8 4
17 :: 3 6 4 1 8 5 7 2
18 :: 3 6 4 2 8 5 7 1
19 :: 3 6 8 1 4 7 5 2
20 :: 3 6 8 1 5 7 2 4
21 :: 3 6 8 2 4 1 7 5
№29 слайд
![количество ферзей количество](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img28.jpg)
Содержание слайда: количество ферзей = 9
количество ферзей = 9
р е ш е н и я :
1 :: 2 4 1 7 9 6 3 5 8
2 :: 2 4 7 1 3 9 6 8 5
3 :: 2 4 8 3 9 6 1 5 7
4 :: 2 4 9 7 3 1 6 8 5
5 :: 2 4 9 7 5 3 1 6 8
6 :: 2 5 7 1 3 8 6 4 9
7 :: 2 5 7 4 1 3 9 6 8
8 :: 2 5 7 9 3 6 4 1 8
9 :: 2 5 7 9 4 8 1 3 6
10 :: 2 5 8 1 3 6 9 7 4
11 :: 2 5 8 1 9 6 3 7 4
12 :: 2 5 8 6 9 3 1 4 7
13 :: 2 5 8 6 9 3 1 7 4
14 :: 2 5 9 4 1 8 6 3 7
15 :: 2 6 1 3 7 9 4 8 5
16 :: 2 6 1 7 4 8 3 5 9
17 :: 2 6 1 7 5 3 9 4 8
18 :: 2 6 1 9 5 8 4 7 3
19 :: 2 6 3 1 8 4 9 7 5
20 :: 2 6 9 3 5 8 4 1 7
21 :: 2 7 5 1 9 4 6 8 3
22 :: 2 7 5 8 1 4 6 3 9
23 :: 2 7 9 6 3 1 4 8 5
24 :: 2 8 1 4 7 9 6 3 5
25 :: 2 8 5 3 9 6 4 1 7
26 :: 2 8 6 9 3 1 4 7 5
27 :: 2 9 5 3 8 4 7 1 6
28 :: 2 9 6 3 5 8 1 4 7
29 :: 2 9 6 3 7 4 1 8 5
30 :: 2 9 6 4 7 1 3 5 8
31 :: 3 1 4 7 9 2 5 8 6
32 :: 3 1 6 8 5 2 4 9 7
33 :: 3 1 7 2 8 6 4 9 5
№37 слайд
![Функция индикатор ,](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img36.jpg)
Содержание слайда: 2) Функция «индикатор», описывающая случайность
2) Функция «индикатор», описывающая случайность
1, если узел x пройден при испытании
I(x) =
0, если узел x не пройден при испытании
Случайное событие = «узел x пройден»,
а I(x) случайная величина {0,1}
Вероятность дойти до узла x = vj есть
(1/m1) (1/m2) … (1/mj)
№40 слайд
![Общий алгоритм Монте-Карло SV](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img39.jpg)
Содержание слайда: Общий алгоритм
// Монте-Карло
SV = 0; // M – число испытаний
for (i = 1; i<=M; i++) {
k = 1; S1 = А1; m1 = S1;
Sum = 0; Prod = 1;
while (mk 0) {
{ //продвижение вперед
Prod* = mk;
Sum+ = Prod;
ak = случайный выбор очередного элемента из Sk;
k ++;
вычислить Sk и mk;
}
SV := SV + Sum;
} // end - for
V = SV/ M;
№41 слайд
![begin MonteCarlo begin](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img40.jpg)
Содержание слайда: begin { MonteCarlo }
begin { MonteCarlo }
Randomize; n_div_2 := n div 2; all := 0;
for iExp:=1 to nExp do
begin { очередное испытание }
m_k := n_div_2 - 1; num := Random ( m_k ) + 1;
a[1] := 1+num; k := 2; prod := m_k; sum := prod;
FormSk ( k, m_k, S_k );
while m_k<>0 do
begin
prod := prod*m_k; sum := sum + prod;
num := Random ( m_k ) + 1; a[k] := S_k[num];
k := k + 1; FormSk ( k, m_k, S_k );
end {while};
all := all + sum
end {for};
v := all/nExp
end { MonteCarlo };
№42 слайд
![procedure FormSk k Nat var m](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img41.jpg)
Содержание слайда: procedure FormSk ( k: Nat; var m_k: Nat0; var S_k: pos );
procedure FormSk ( k: Nat; var m_k: Nat0; var S_k: pos );
{ формирует "множество" (вектор) S_k возможных ходов и
его мощность m_k; если S_k пусто, то m_k=0 }
var s: Nat;
begin
m_k := 0;
for s:=1 to n do
if not NoQueen( k, s) then
begin { можно ставить }
m_k := m_k + 1;
S_k[m_k] := s
end;
end {FormSk};
№51 слайд
![Для случая эту задачу впервые](/documents_5/5a8b56bd10bf94f65a8bf6e241387c93/img50.jpg)
Содержание слайда: Для случая 6×10 эту задачу впервые решил в 1965 году Джон Флетчер [1].
Для случая 6×10 эту задачу впервые решил в 1965 году Джон Флетчер [1].
Существует ровно 2339 различных укладок пентамино в прямоугольник 6×10, не считая поворотов и отражений целого прямоугольника, но считая повороты и отражения его частей
(иногда внутри прямоугольника образуется симметричная комбинация фигур, поворачивая которую, можно получить дополнительные решения; для прямоугольника 3×20, приведённого на рисунке, второе решение можно получить поворотом блока из 7 фигур, или, иначе говоря, если поменять местами четыре фигуры, крайние слева, и одну крайнюю справа, см.предыдущий слайд).
Скачать все slide презентации Поиск с возвращением. Задача о ферзях. Оценка методом Монте-Карло. одним архивом:
Похожие презентации
-
Расчет интегралов методом Монте-Карло Понятие о методах Монте-Карло. Расчет интегралов
-
Метод Монте-Карло для сверхпроводящей ВТСП-пластины Вихри в сверхпроводниках. Постановка задачи. Алгоритм Монте-Карло
-
Траекторный алгоритм Монте-Карло для конкретных задач t-J-модель. Моделирование сверхпроводящих плоскостей в ВТСП
-
Разбор двух задач поисковой системы: Борьба с оптимизаторами Влияние юзабилити на ранжирование
-
8. СЛЕДУЮЩИЕ ШАГИ. . . Определение цели, задач, предположения (гипотезы), методов ведения исследования. Планирование. Работа в команде
-
Новая книга «Оценка программ: методология и практика» Российско-американский проект представляют Росс Коннер, Алексей Кузьмин и
-
ПРЕДМЕТ,МЕТОДОЛОГИЯ И ЗАДАЧИ КУРСА 1. ПРЕДМЕТ КУРСА; 2. ОБЪЕКТ ИЗУЧЕНИЯ; 3. МЕТОДОЛОГИЧЕСКИЕ И МЕТОДИЧЕСКИЕ ОСНОВЫ; 4. ЗАДАЧИ КУРСА.
-
Тема курсовой работы «Совершенствование методов оценки кадров организации» Выполнила: Сазонова Антонина Александровна
-
Семинар «Методологические основы оценки качества образования»
-
Анализ финансового состояния Общие задачи, цели и этапы анализа. Общая оценка финансового состояния. Оценка ликвидности. Оце