русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Задача оптимального выбора


Дата добавления: 2015-08-06; просмотров: 3518; Нарушение авторских прав


Последний пример алгоритма с возвратом — логическое обобщение последних двух примеров, построенных по общей схеме (35). Вначале использовался принцип возврата для поиска единственного решения поставленной задачи. Примерами были обход доски ходом коня и размещение восьми ферзей. Затем целью явился поиск всех решений некоторой задачи, рассмотренный на задаче о восьми ферзях. Далее рассмотрим поиск оптимального решения. Для этого необходимо формировать все возможные решения и в процессе их получения оставлять одно, в определенном смысле оптимальное. Предположим, оптимальность оценивается с помощью некоторой положительной функции f(s). В этом случае, заменяя в схеме (35) оператор печатать решения на оператор

IF f(решение) > f(optimum) THEN optimum := решение END; (47)

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

В качестве примера общей проблемы поиска оптимального решения выберем такую важную и часто встречающуюся задачу: нужно найти, руководствуясь некоторыми ограничениями, оптимальную выборку из заданного множества объектов. Выборки, представляющие приемлемые решения, строятся постепенно: один за другим просматриваются отдельные объекты из исходного множества. Процедура Try описывает процесс исследования пригодности одного отдельного объекта — она вызывается рекурсивно (для исследования очередного объекта) до тех пор, пока все они не будут рассмотрены.

Из этого следует, что при рассмотрении каждого объекта (в предыдущих примерах мы называли их кандидатами) возможны два заключения, а именно либо включать исследуемый объект в текущую выборку, либо не включать. В такой ситуации оператор цикла уже не подходит, вместо этого нужно явно описать оба варианта (этот процесс и описан ниже). В приведенном примере объекты пронумерованы 1, 2,..., n:



PROCEDURE Try(i: INTEGER);

BEGIN

IF включение приемлемо THEN BEGIN включение i-го объекта;

IF i < n THEN Try(i+1)

ELSE BEGIN проверка оптимальности END;

исключение i-го объекта (48)

END;

IF приемлемо невключение THEN BEGIN

IF i < n THEN Try(I+1)

ELSE BEGIN проверка оптимальности END

END

END;

Из схемы (48) видно, что существует всего 2n возможных выборок, поэтому нужно использовать такой критерий приемлемости, который значительно бы сократил число перебираемых кандидатов. Для пояснения этого процесса возьмем конкретный пример построения выборки. Пусть каждый из n объектов а1,..., aп характеризуется весом и ценностью. Оптимальной назовем выборку с максимальной суммой ценностей и суммой весов, ограниченной некоторым пределом. С такой проблемой сталкивается любой путешественник, упаковывающий чемоданы и стремящийся выбрать так n предметов, чтобы ценность их была оптимальной, а общий вес не превышал какого-то допустимого предела.

Теперь надо решить задачу как же все это представить в виде определенных данных. Будем использовать такие описания:

TYPE

objects = RECORD value, weight: INTEGER END;

VAR i,j,n: INTEGER;

obj: ARRAY [1..30] OF Objects; (49)

limw, totv, maxv: INTEGER;

s, opts: STRING;

 

Переменные limw и totv соответствуют предельному весу и общей ценности всех n объектов. В процессе построения выборки эти две величины фактически остаются постоянными. Через s обозначена текущая выборка, здесь каждый из объектов представлен своим именем (индексом); opts — оптимальная выборка, полученная к данному моменту, a maxv — ее ценность.

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

1. Общий вес tw выборки, полученной к данному моменту.

2. Общую ценность av текущей выборки, которую можно еще достичь.

Эти две величины удобно представить как параметры процедуры Try. Условие включение приемлемо в (48) теперь формулируется так:

tw + a[i].weight £ limw, (50)

и последующая проверка на оптимальность выглядит следующим образом:

IF av > maxv THEN (* новый оптимум, его запись *)

BEGIN

opts := s; maxv := av; (51)

END;

Последнее присваивание основано на том соображении, что достижимое значение будет получено только после обработки всех объектов. Условие приемлемо невключение в (48) выражается так:

av - a[i].value > maxv. (52)

Поскольку полученное значение av - a[i].value вновь используется, оно, чтобы избежать повторного вычисления, “сохраняется” в переменной av1.

Из схемы (48) и фрагментов (49)-(52) получаем, добавив соответствующие операторы инициализации глобальных переменных, всю программу целиком. Следует заметить, что для включения и исключения из множества s здесь очень удобно пользоваться операциями над множествами. В табл. 5 приводятся результаты работы программы (листинг 7) с допустимыми весами от 10 до 120.

Таблица 5.Результаты работы программы оптимального выбора

Beс Ценность  
*                  
            *      
        *   *      
*       *   *      
* *   *     *      
* * * * *          
* *     *   *   *  
* * *   *   * *    
* *     *   *   * *
* *   * *   * * *  
* * * * * * *   *  
* *     * * * * * *

 

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

Листинг 7.Оптимальный выбор

Program Selection;

{ поиск оптимального выбора объекта при ограничении }

TYPE

objects = RECORD value, weight: INTEGER END;

VAR i,j,n: INTEGER;

obj: ARRAY [1..30] OF Objects;

limw, totv, maxv: INTEGER;

s, opts: STRING;

WeightInc, WeightLimit: INTEGER;

tick: ARRAY [0..1] OF CHAR;

 

FUNCTION InStr(i: INTEGER; VAR s: STRING): BOOLEAN;

{ входит ли число i в строку s}

VAR j:INTEGER;

BEGIN

InStr:=FALSE;

FOR j:=1 TO Length(s) DO

IF Chr(i) = s[j] THEN InStr:=TRUE;

END;

 

PROCEDURE Try(i, tw, av: INTEGER);

VAR av1: INTEGER;

BEGIN { попытка включения }

IF tw + obj[i].weight <= limw THEN BEGIN

s := s + Chr(i);

IF i < n THEN Try(i+1, tw + obj[i].weight, av)

ELSE IF av > maxv THEN BEGIN maxv := av; opts := s; END;

END;

{ попытка исключения }

Delete(s,Pos(Chr(i),s),1);

av1 := av - obj[i].value;

IF av1 > maxv THEN

IF i < n THEN Try(i+1, tw, av1)

ELSE BEGIN maxv := av1; opts := s; END;

END;

 

BEGIN totv := 0; limw := 0;

tick[0] := ’ ’; tick[1] := ’*’;

Write('Enter number of objects N = ');

ReadLn(n);

Write('Through SPASE enter weight of ',n,' object and it`s value: ');

FOR i := 1 TO n DO BEGIN

Read(obj[i].weight); Read(obj[i].value);

totv := totv + obj[i].value

END;

Write('Enter change step of weight: ');

Read(WeightInc);

Write('Enter weight limit: ');

Read(WeightLimit);

Write('Weight');

FOR i := 1 TO n DO Write(obj[i].weight:5);

WriteLn;

Write('Value ');

FOR i := 1 TO n DO Write(obj[i].value:5);

WriteLn;

REPEAT limw := limw + WeightInc; maxv := 0;

s := ’’; opts := ’’; Try(1, 0, totv);

Write(limw:5);

FOR i := 1 TO n DO

IF InStr(i,opts) THEN Write(tick[1]:5) ELSE Write(tick[0]:5);

WriteLn(maxv:8);

UNTIL limw >= WeightLimit;

ReadLn;

END.


* Если бы программа отыскивала лишь 12 принципиально различных решений, причем делала бы это максимально быстро, то и она сама, и данные, которыми она должна была бы манипулировать, оказались бы значительно более сложными



<== предыдущая лекция | следующая лекция ==>
Задача о восьми ферзях | Этапы жизненного цикла промышленных изделий


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.199 сек.