Род Стивенс

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

Многие сложные реальные задачи можно смоделировать с помощью деревьев ре­шений (decision trees). Каждый узел в дереве представляет собой один шаг реше­ния задачи. Ветвь в дереве соответствует решению, которое ведет к более полному решению. Листы представляют собой окончательное решение. Цель состоит в том, чтобы найти «наилучший» путь ОТ корня до листа при выполнении некоторых ус­ловий. Естественно, ЧТО условия и «наилучший» путь зависят от сложности конк­ретной задачи. '

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

Эта глава посвящена методам работы с этими огромными деревьями. Снача­ла рассматриваются игровые деревья (game trees). На примере крестиков-ноликов показаны способы поиска в деревьях игры наилучшего возможного хода. После­дующие разделы описывают более общие способы исследования деревьев реше­ний. Для самых маленькихдеревьев можно использовать метод полного перебора (exhaustive searching) всех возможных решений. Для работы с большими деревья­ми более подходит метод ветвей и границ (bmnch-and-bound technique), позволя­ющий отыскивать лучшее возможное решение без поиска по всему дереву.

Для огромных деревьев лучше использовать эвристический метод (heuristic). При этом найденное решение может и не быть наилучшим из возможных, но дол­жно быть достаточно близким к нему. Данный метод позволяет исследовать прак­тически любое дерево.

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

Поиск в игровых деревьях

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

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

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

← предущий раздел следующая →

Страницы раздела: 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.