Выражение метод ветвей и границ связано с естественной графической интерпретацией всего изложенного

Функция j, которой мы при этом выборе пользуемся, называется  оценочной. Очевидно, что рекорд не обязан доставлять минимум  функции f; однако, при благоприятных обстоятельствах возникает возможность сократить  перебор.

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

Пусть A1,…,As — подмножества множества M, возникшие на предпоследнем этапе построения рекорда, и пусть множество A1 оказалось выбранным с помощью оценочной функции. Именно при разбиении A1 и возник рекорд, который сейчас для определенности    обозначим через {mi}. Согласно сказанному выше, ,  ;

 кроме того, по определению оценочной функции, .

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

            Выражение метод ветвей и границ связано с естественной графической интерпретацией всего изложенного: строится многоуровневое дерево, на нижнем уровне которого располагаются  элементы множества M. На дереве ветви ведут к рекорду и его  улучшениям и  часть ветвей остается «отсеченной», потому что их развитие оказалось нецелесообразным.

Рассмотрим   пример применения метода ветвей и границ  для решения задачи о коммивояжере.  

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

Ссылка на основную публикацию
Adblock detector