Род Стивенс

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

// Если это лист, то он должен быть лучшим решением, чем решен // которое имеется на данный момент, или он должен был быть // отрезан раньше. if (item_num > Numltems) then begin

// Сохранение улучшенного решения. for i := 1 to Numltems do

BestSolution[i] := TestSolution[i];

BestProfit := TestProfit;

BestCost := TestCost;

exit;

end;

// В противном случае продолжаем исследовать ветви к дочерним уз. // Сначала пробуем включить этот элемент в расход, чтобы убедит // что он вписывается в границу стоимости. if (TestCost + Items[itenmum] .Cost <= AllowedCost) then begin

11 Добавляем элемент в исследуемое решение. TestSolution[itenL_num] := True;

TestCost := TestCost+Items[item_num].Cost;

TestProfit := TestProfit + Items[item_num].Profit; UnassignedProfit := UnassignedProfit - Items[item_num].Prol

// Рекурсивно определяем, какой результат может получиться. -BranchAndBound(item_num+l);

// Удаление элемента из исследуемого решения.1 TestSolution[item_num] := False;

TestCost := TestCost - Items[item_num] .Cost;

TestProfit := TestProfit - Items[item_num] .Profit; UnassignedProfit := UnassignedProfit + Items[item_num] .Profit,- end;

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

UnassignedProfit := UnassignedProfit-ltems[item_num] .Profit; if (TestProfit + UnassignedProfit > BestProfit) then BranchAndBound (item_num + 1),- UnassignedProfit := UnassignedProfit + Items[item_num].Profit;

end;

Программа BandB использует полный перебор и метод ветвей и границ, чтобы решить задачу формирования Портфеля. Введите минимальную и максимальную стоимость и значения, которые вы хотите назначить позициям, и число позиций, которое требуется создать. Затем нажмите кнопку Make Data (Создать данные), и программа сгенерирует элементы.

Затем при помощи группы переключателей внизу формы выберите алгоритм перебора. Когда вы нажимаете кнопку 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.