На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

В Кубанском государственном технологическом университете предложен метод построения окрестности глобального оптимума в виде ранжированного поддерева, содержащего только субоптимальные решения NPC-задач

02.04.2010

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

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

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

 Подробное описание дается в статье «Метод построения окрестности глобального оптимума NPC-задач на ранжированном дереве поиска решений», авторы: Власенко А.В., Марков В.Н. (Кубанский государственный технологический университет, г. Краснодар).