Алгоритмы разбиения графов на подграфы и их необходимость при решении многих прикладных задач, при автоматизации проектирования и контроля, при автоматическом анализе содержания документов. Поиск в глубину и в ширину; метод динамического программирования.
Аннотация к работе
Разбиение на основе роевого интеллекта и генетической эволюцииПереборные алгоритмы такие, как поиск в глубину, поиск в ширину, метод динамического программирования, метод ветвей и границ и др. обеспечивают абсолютную точность решения, однако не удовлетворяют по одному из основных критериев оценки алгоритма - времени расчета. Для сокращения времени решения, задач разбиения графов на подграфы, используются различные эвристические способы ограничения перебора, основанные на неких математических закономерностях, позволяющих сократить временную и пространственную сложность алгоритма [2]. Рой частиц может рассматриваться как многоагентная система, в которой каждый агент (частица) функционирует автономно по очень простым правилам. В работе предлагается подход к построению структур и принципов кодирования хромосом, обеспечивающих их гомологичность и возможность одновременного использования в генетическом алгоритме, и в алгоритме на основе роя частиц. Хромосома, соответствующая решению Р, состоит из генов, число которых на единицу меньше числа n элементов в векторе P : H={gl | l=1,2,…,(n-1)}.