Род Стивенс

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

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

Восхождение на холм

Эвристический метод восхождения на холм (hill climbing) вносит изменения в текущее решение, продвигая его максимально близко к цели. Этот процесс назы­вается восхождением на холм, потому что он похож на то, как заблудившийся путе­шественник пытается ночью добраться до вершины горы. Даже если уже слишком темно, чтобы разглядеть что-то вдали, он может попробовать достигнуть вершины горы, постоянно двигаясь вверх.

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

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

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

Для списка инвестиций из табл. 8.3 программа сначала выбирает сделку А, по­тому что она имеет самую большую прибыль - 9 млн долларов. Затем выбирается сделка С, потому что она имеет самую большую прибыль из оставшихся - 8 млн. В этой точке из допустимых 100 млн потрачено уже 93 млн, и программа больше не может выбирать какие-либо сделки. Решение, вычисленное с помощью этой эв­ристики, включает элементы А и С, стоит 93 млн и дает прибыль в 17 млн.

Эвристика восхождения на холм заполняет портфель очень быстро. Если эле­менты изначально сортируются в порядке уменьшения прибыли, то сложность этого алгоритма будет порядка O(N). Программа просто перемещается по списку, добавляя каждую позицию, пока не будет исчерпан лимит средств. Если список не отсортирован, то сложность этого алгоритма составляет всего лишь 0(N2). Эго намного лучше, чем 0(2N) шагов, необходимых для полного перебора всех узлов дерева. Для 20 позиций эта эвристика использует около 400 шагов, метод ветвей и границ - несколько тысяч, а полный перебор - более чем 2 млн.

// Перебор дерева с использованием эвристики восхождения на холм.

procedure THeurForm.HillClimbing(node : Integer);

var

i, j, big_value, big_j : Integer; begin

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

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