Род Стивенс

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

Структура программ, реализующих эвристики минимальной стоимости и эв­ристики восхождения на холм, почти идентична. Единственная разница заключа­ется в выборе следующей позиции, которая добавляется к имеющемуся решению. Метод минимальной стоимости вместо позиции с максимальной прибылью выби­рает позицию, которая имеет самую низкую стоимость. Поскольку эти два метода очень похожи, сложность их одинакова. Если позиции должным образом отсорти­рованы, оба алгоритма имеют сложность порядка O(N). При случайном располо­жении позиций их сложность составит порядка 0(№).

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

if ((not BestSolution[j]) and

(small_cost > Items [ j ] .Cost) and (BestCost+Items[j].Cost <= AllowedCost)) ' then begin

small_cost := Items[j].Cost; small i := j;

end;

Сбалансированная прибыль

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

Эвристика сбалансированной прибыли (balanced profit) сравнивает как при­быль, так и стоимость позиций, чтобы определить, какие позиции необходимо выб­рать. На каждом шаге эвристика выбирает элемент с самым большим отношением прибыли к стоимости.

В табл. 8.4 приведены те же значения, что и в табл. 8.3, но с дополнительным столбцом отношения прибыль/стоимость. При этом подходе вначале выбирается позиция С, потому что она имеет самое высокое отношение - 0,27. Затем добавля­ется D с отношением 0,26 и В с отношением 0,20. В этой точке потрачено 92 млн из 100 млн, и в решение больше нельзя добавить ни одной позиции.

Это решение имеет стоимость 92 млн и дает прибыль в 22 млн. Это на 4 млн лучше, чем решение, найденное с помощью метода минимальной стоимости и на 5 млн лучше, чем решение, найденное эвристикой восхождения на холм. Более того, полученное решение вообще будет наилучшим из всех возможных, что подтвердят результаты поиска полным перебором или методом ветвей и границ. Однако сба­лансированная прибыль - это все же эвристика, поэтому не всегда отыскивает луч­шее возможное решение. Она часто находит лучшие решения, чем методы восхож­дения на холм и минимальной стоимости, но это случается не всегда.

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

test_ratio := Itemslj] . Profit/items[j] .Cost; if ( (not BestSolution[j]) and

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

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