37. Рекурсия и игры двух игроков.

Шашки.

(?)

38. Дерево решений для игр двух игроков.

И гры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.

На рисунке слева — игра для двух игроков. Игрок 1 ходит первым и выбирает стратегию F или U. Игрок 2 анализирует свою позицию и решает — выбрать стратегию A или R. Скорее всего первый игрок выберет U, а второй — A (для каждого из них это оптимальные стратегии); тогда они получат соответственно 8 и 2 очка.

Экстенсивная форма очень наглядна, с её помощью особенно удобно представлять игры с более чем двумя игроками и игры с последовательными ходами. Если же участники делают одновременные ходы, то соответствующие вершины либо соединяются пунктиром, либо обводятся сплошной линией.

39. Стратегия минимакса.

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

Основной принцип, лежащий в основе каждой стратегии минимакса, – контролировать ситуацию так, чтобы некоторые эффекты были минимизированы (обычно собственные потери), а другие максимизированы (обычно собственный выигрыш).

40. Альфа-Бета отсечение.

Альфа-бета отсечение (англ. Alpha-beta pruning) — это алгоритм поиска, стремящийся сократить количество узлов, оцениваемых в дереве поиска алгоритмом минимакс. Этот алгоритм предназначен для антагонистических игр и используется для машинной игры (в шахматах, го и других). В основе алгоритма лежит идея, что оценивание ветви дерева поиска может быть досрочно прекращено (без вычисления всех значений оценивающей функции), если было найдено, что для этой ветви значение оценивающей функции в любом случае хуже, чем вычисленное для предыдущей ветви. Альфа-бета отсечение является оптимизацией, так как результаты работы оптимизируемого алгоритма не изменяются.

41. Последовательный поиск.

Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.

42. Последовательный поиск.

Логарифмический (бинарный или метод деления пополам) поиск данных применим к сортированному множеству элементов a[1] < a[2] < … < a[n], размещение которого выполнено на смежной памяти. Для большей эффективности поиска элементов надо, чтобы пути доступа к ним стали более короткими, чем простопоследовательный перебор. Наиболее очевидный метод: начать поисксо среднего элемента, т.е. выполнить сравнение с элементом a⌊(1+n)/2⌋. Результат сравнения позволит определить, в какой половине последовательности a[1], a[2], … , a⌊(1+n)/2⌋, … a[n] продолжить поиск, применяя к ней ту же процедуру, и т.д. Основная идея бинарного поиска довольно проста, однако “для многих хороших программистов не одна попытка написать правильную программу закончилась неудачей”. Чтобы досконально разобраться в алгоритме, лучше всего представить данные a[1] < a[2] < … < a[n] ввиде двоичного дерева сравнений, которое отвечает бинарному поиску.

Двоичное дерево (бинарное дерево) называется деревом сравнений, если для любой его вершины (корня дерева или корня поддерева) выполняется условие:

Вершина левого поддерева < Вершина корня < Вершина правого поддерева

43. Какие таблицы называются статическими, динамическими?

Статистические таблицы – таблицы, размер которой задается при создании.

Динамические таблицы – таблицы, данные в которых можно изменить в течении работы программы.

44. Задача построения оптимального дерева в общем виде.

Чтобы поиск выполнялся быстрее, требуется расположить тяжелые или наиболее часто используемые ключи ближе к корню.

45. Какой алгоритм называется эвристическим?

Эвристический алгоритм – алгоритм, имеющий следующие свойства:

- Он находит хорошее, но не обязательно оптимальное решение.

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

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

46. Эвристики построения оптимальных деревьев.

Эвристика №1: К построенному дереву добавляем очередной узел таким образом, чтобы его левые и правые поддеревья имели максимально близкое количество вершин, считая листья.

Эвристика №2: К построенному дереву добавляем очередной узел таким образом, чтобы его левые и правые поддеревья имели максимально близкие суммы весов или суммы частот обращения к вершинам.

Эвристика №3: Самые тяжелые ключи помещаем ближе к корню.

47. AVL-Деревья.

АВЛ-дерево — сбалансированное по высоте двоичное дерево поиска: для каждой его вершины высота её двух поддеревьев различается не более чем на 1.