Род Стивенс

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

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

Момент остановки

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

В программе Неиг этот подход реализован в процедуре MakeChanges Fixed. Она выполняет определенное количество случайных изменений на множестве раз­личных исследуемых решений.

// Одновременное изменение к элементов, чтобы улучшить исследуемое // решение.

// Выполненить num_trials испытаний, сделав num_changes изменений // для каждого.

procedure THeurForm.MakeChangesFixed(k, num_trials, num_changes : Integer) ; var

trial, change, i, removal : Integer; begin

for trial := 1 to num_trials do begin

/ / Определение случайного исследуемого решения, с которого // необходимо начать. while (AddtoSolution) do ;

11 Начинаем работать с этим решением как с экспериментальным // решением.

TrialProfit := TestProfit;

TrialCost := TestCost; for i ••= 1 to Numltems do

TrialSolution[i] := TestSolution[i] ;

for change :=1 to num_changes do begin

// Удаление k случайных элементов, for removal := 1 to k do RemoveFromSolution;

// Добавление случайных элементов, пока они помещаются // в пределах границы стоимости. while (AddtoSolution) do ;

// Если решение улучшается, эксперимент сохраняется.

// В противном случае восстанавливаются - исходные значения.

if (TestProfit > TrialProfit) then

begin

// Сохранение улучшения.

TrialProfit := TestProfit;

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

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

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