Род Стивенс

Книги → Delphi. Готовые алгоритмы → Глава 8. Деревья решений

Эвристика ,

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

Например, в шахматах обычной эвристикой является «усиление преимуще­ства». Когда у противника меньше сильных фигур и одинаковое с вами число ос­тальных, то следует идти на размен при каждой возможности. Например, если вы можете захватить коня, но потеряете своего коня при обмене, то вы должны обме­няться. Сокращая число оставшихся фигур, вы уменьшаете дерево решений и уве­личиваете относительное преимущество в силе. Эта стратегия не гарантирует, что вы выиграете игру, но увеличивает ваши возможности. Другое эвристическое пра­вило, используемое во многих стратегических играх, - присвоение различным час­тям игрового поля разных значений. В шахматах значение ближайших к центру поля квадратов выше, потому что фигуры в этих позициях могут атаковать фигу­ры на большей части поля. Когда процедура BoardValue вычисляет значение по­зиции на поле, она может присвоить большее значение фигурам, которые стоят на этих ключевых квадратах.

Поиск нестандартных решений

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

Ветви и границы

Метод ветвей и границ (brunch-and-bound technique) является одним из мето­дов упрощения деревьев решений таким образом, чтобы не рассматривать все вет­ви дерева. Общая стратегия состоит в том, чтобы отслеживать границы уже обна­руженных и возможных решений. Если вы достигаете точки, где лучшее решение на данный момент эффективнее, чем лучшее возможное решение в нижних вет­вях, вы можете проигнорировать все пути ниже данного узла.

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

Задача такого типа называется задачей формирования портфеля (knapsack problem). У вас есть несколько позиций (инвестиций), которые должны поместить­ся в портфеле с фиксированным размером (100 млн долларов). Каждая позиция имеет некоторую стоимость (деньги) и значение (тоже деньги). Необходимо най­ти набор позиций, которые помещаются в портфеле и дают максимально возмож­ное значение.

Вы можете смоделировать эту задачу с помощью дерева решений. Каждый узел в дереве соответствует определенным комбинациям позиций, помещенных в пор­тфель. Каждая ветвь — это принятое решение о том, поместить элемент в портфель или извлечь его оттуда. Левая ветвь в первом узле соответствует расходу денег на первое вложение. Правая ветвь представляет отказ в первом вложении. На рис. 8.4 показано дерево решений для четырех возможных вложений.

← предыдущая следующая →

Страницы раздела: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Публикация компанией Dropbox кода Zulip – средства общения для IT-разработчиков

20.11.2015
Одной из одобрительно встреченных программистами инициатив, реализующихся в рамках акции Hack Week, стала публикация исходного кода приложения Zulip – веб-приложения для общения между собой разработчиков в сфере IT-технологий.

Объединение ОС Android и Chrome

17.11.2015
Слухи об объединении двух крупнейших ОС компании Google, Android и Chrome, гуляют по Интернету уже более 5 лет, но до сих пор этого не случилось, хотя очевидно, что с течением времени эти ОС становятся всё более похожими: так, в последнее время появилось немало Android-устройств, к которым прилагаются клавиатуры, а Chrome OS «научилась» работать с сенсорными экранами.

Конференция Linux Piter 2015

15.11.2015
Уже почти через неделю в Санкт-Петербурге впервые в истории пройдёт конференция, посвящённая проблемам свободного программного обеспечения – Linux Piter 2015.