Мои Конспекты
Главная | Обратная связь

...

Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Метод a-b отсечений





Помощь в ✍️ написании работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Альфа-бета отсечение — это алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакс.

В основе алгоритма лежит идея, что оценивание ветви может быть досрочно прекращено, если было найдено, что для этой ветви значение функции хуже, чем вычисленное для предыдущей ветви.

Альфа-бета отсечение является оптимизацией.

7. Метод динамического программирования: общие принципы

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

· Разбиение задачи на подзадачи меньшего размера.

· Нахождение оптимального решения подзадач рекурсивно

· Использование полученного решения подзадач для конструирования решения исходной задачи.

8. Метод динамического программирования: задача о рюкзаке

Наилучшие частичные наборы хранятся в хэш-таблице, т. е. для каждого веса храниться максимальная стоимость.

Стартуем с пустого множества частичных наборов. В каждый момент времени добавляем по одному предмету.

В конце остается только выбрать самый дорогой из них.

Сложность этого алгоритма — O(nB), где В – размер рюкзака.

9. Метод динамического программирования: задачи о минимальной триангуляции и о максимальной общей подпоследовательности.

Задача о минимальной триангуляции:

 

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

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

 

Задача о максимальной общей последовательности:

даны две строки, требуется найти подпоследовательность наибольшей длины, входящую в оба слова.

Вначале найдём длину наибольшей подпоследовательности. Допустим мы ищем решение для случая (n1, n2), где n1, n2— длины первой и второй строк. Пусть уже существуют решения для всех подзадач (m1, m2) меньших заданной. Тогда задача (n1, n2) сводится к меньшим подзадачам следующим образом:

Теперь вернемся к задаче построения подпоследовательности. Для этого в существующий алгоритм добавим запоминание для каждой задачи той подзадачи, через которую она решается.

Теперь, начиная с последнего элемента поднимаемся к началу по направлениям, заданным первым алгоритмом и записываем символы в каждой позиции. Это и будет ответом в данной задаче.

Очевидно, что время работы алгоритма будет O(n2).

Решение - динамическое программирование, где текущее значение ищется с помощью предыдущих, в данном случае нам нужно завести дву-мерный массив и n*m где 0 строка и 0 столбец заполняются 0, затем последовательно заполняем получившуюся матрицу по данному алгоритму(s[n] вроде н-тый символ строки), и в последних строке и столбце находим максимальное значение.

Доверь свою работу ✍️ кандидату наук!
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Поиск по сайту:







©2015-2020 mykonspekts.ru Все права принадлежат авторам размещенных материалов.