Род Стивенс

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

TestCost := BestCost; for i := 1 to Numltems do

TestSolution[i] := BestSolution[i];

num_unchanged := num_unchanged+l; end;

// Если ошиблись (сохранили решение, которое не лучше // предыдущего). if (slipped) then begin

nunt_slips := nunt_slips+l;

if (num_slips > max_slips) then

begin

num_slips := 0; t := t * TFACTOR;

num_unchanged : = 0; t

end; end;

end; // Попробуем еще раз.

end;

Сравнение эвристических методов

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

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

Сложные задачи

Многие задачи, отличающиеся от задачи формирования портфеля, решить го­раздо труднее. Некоторые из них имеют сложность неизвестной степени. Другими словами, нет алгоритмов решения проблем, сложность которых оценивается как 0(NC) для любой константы С, и даже O(N100°).17

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

Задача о выполнимости

Дано логическое утверждение, например (А и не В) или С. Требуется опреде­лить, есть ли какое-либо сочетание истинных и ложных значений переменных А, В и С, при котором выражение принимает истинное значение. В данном примере легко увидеть, что выражение будет истинным, если A = True, В = False и С = False. В случаях более сложных выражений, включающих сотни переменных, сложно сказать, может ли утверждение быть истинным.

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

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