Род Стивенс

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

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

Размер этого дерева очень быстро растет с увеличением числа инвестиций. Для 10 возможных инвестиций дерево содержит 210- 1024 листа. Для 20 инвестиций дерево будет иметь более миллиона листьев. Полный поиск по такому дереву еще допустим, но при дальнейшем увеличении числа возможных инвестиций размер дерева станет очень большим.

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

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

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

Предположим, что вы начали перебор дерева, изображенного на рис. 8.4. Вы увидели, что можете потратить 97 млн на сделках А и В при прибыли 23 млн. Это соответствует четвертому листу слева на рис. 8.4.

Продолжив поиск, можно дойтидо второго узла, обозначенного как С на рис. 8.4. Это соответствует инвестиционным пакетам, которые включают сделку А, не вклю­чают сделку В, и могут включать или не включать сделки С и D. В этой точке пакет уже стоит 45 млн для сделки А и дает прибыль 10 млн долларов.

Единственные оставшиеся сделки - это С и D. Вместе они могут улучшить решение на 12 млн. Значение текущего решения равно 10 млн, поэтому лучшее возможное решение ниже этого узла стоит почти 22 млн. Это меньше уже найден­ного решения на 23 млн, поэтому не следует продолжать рассматривать этот путь.

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

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

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

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