Род Стивенс

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

Следующий код использует проверку верхней и нижней границ для реализа­ции алгоритма ветвей и границ.

type

TItem = record

Cost : Integer;

Profit : Integer; end;

TItemArray = array [1..1000000] of TItem;

PItemArray = ''TItemArray;

TBoolArray = array [1..1000000] of Boolean;

PBoolArray = ЛТВоо1Аггау;

TBandBForm = class(TForm)

// Код опущен. . .

private

NumIterns : Integer;

Items : PItemArray;

AllowedCost : Integer;

// Переменные поиска.

// Общее число необъявленных доходов. // True для элементов лучшего решения.

NodesVisited : Longint;

UnassignedProfit : Integer;

BestSolution : PBoolArray;

BestCost : Integer;

// True для элементов исследуемого // решения.

// Стоимость исследуемого решения.

// Доход от рассматриваемого решения.

BestProfit : Integer;

TestSolution : PBoolArray;

TestCost : Integer;

TestProfit : Integer;

// Код опущен. ..

end;

// Инициализация тестовых значений и начало исчерпывающего поиска или

// перебора методом ветвей и границ.

procedure TBandBForm.Search(b_and_b : Boolean);

var

i : Integer;

begin

NodesVisited := 0;

BestProfit := 0;

BestCost := 0;

TestProfit •:= 0;

TestCost := 0;

UnassignedProfit := 0; for i := 1 to Numltems do

UnassignedProfit := Unassignedprofit+Items[ij.Profit;

// Начало перебора с первого элемента. if (b_and_b) then BranchAndBound(1) else

ExhaustiveSearch(l);

end;

// Выполнение перебора методом ветвей и границ,

// начиная с указанного элемента.

procedure TBandBForm.BranchAndBound(item_num : Integer);

var

i : Integer; begin

NodesVisited := NodesVisited+l;

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

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