Род Стивенс

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

На рис. 8.5 изображено окно программы BandB после решения задачи о фор­мировании портфеля с двадцатью элементами. В данном случае алгоритм ветвей и границ нашел лучшее решение после исследования всего 1613 из более 2 млн узлов дерева. Перед тем как запустить исчерпывающий перебор дерева для 20 элементов, попробуйте запустить примеры меньшего размера. На компьютере, где установлен процессор Pentium с тактовой частотой 90 МГц, поиск решения задачи формирова­ния портфеля для 20 позиций методом полного перебора занял более 30 с.

Перебор методом ветвей и границ исследует гораздо меньше узлов, чем пол­ный перебор. Дерево решений для задачи о формировании портфеля с 20 элемен­тами содержит 2 097 151 узел. В то время как полный перебор всегда исследует все узлы, метод ветвей и границ может перебрать только примерно 1 600 узлов.

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

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

Эвристика

Иногда даже алгоритм ветвей и границ не может полностью перебрать дерево решения. Дерево для задачи о формировании портфеля с 65 элементами содержит более 7 * 1019 узлов. Если алгоритм ветвей и границ перебирает только десятую часть процента этих узлов, а компьютер проверяет* миллион узлов в секунду, то потребовалось бы более 2 млн лет, чтобы решить эту задачу. В задачах, где алго­ритм ветвей и границ работает недостаточно быстро, можно использовать эврис­тику (heuristic).

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

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

В этом разделе рассматривается эвристика, которая используется для решения многих сложных задач. Программа Неиг демонстрирует каждый из эвристических подходов. Кроме того, она позволяет сравнить эвристику с полным перебором и ме­тодом ветвей и границ. Введите информацию в области Parameters (Параметры), чтобы задать параметры создаваемых данных. Выберите алгоритмы, которые вы хотите протестировать, и щелкните по кнопке Go. Программа отображает общую стоимость и прибыль для наилучшего решения, найденного каждым из выбран­ных алгоритмов. Она также сортирует решения по максимальному полученному доходу и отображает время работы каждого алгоритма. Используйте метод ветвей и границ только для небольших задач, а метод полного перебора только для задач еще меньшего объема.

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

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