Разбиение - граф
Cтраница 1
Разбиение графа относится к задачам дискретной условной оптимизации из-за прерывности ее ЦФ и наличия множества ограничений на переменные. Однако применительно к задаче разбиения большинство из вышеприведенных методов не может быть использовано в связи с ее дискретностью, которая приводит к существенному росту трудностей при поиске оптимума. Поэтому данные задачи выделяют в особый класс оптимизационных комбинаторных задач на графах. [1]
Получено разбиение графа на плоские суграфы. [2]
Задача разбиения графа на части имеет много практических применений. Она используется при проектировании устройств автоматики и вычислительной техники, создании систем управления, компьютерных и инженерных сетей, а также при решении различных задач ИИ. [3]
 |
Получение некорректных хромосом потомков и их корректировка. [4] |
Рассмотрим задачу разбиения графа на два подграфа так, чтобы число вершин в подграфах А ] и А2 было равно заданным значениям W, и N2 и при этом целевая функция имела экстремальное значение. Очевидно, что число единиц в хромосоме должно равняться Л, число нулей - Nr Однако это условие для хромосом потомков, получающихся в результате кроссовера или мутаций, в общем случае не соблюдается, причем по-прежнему вероятность получения корректного потомка крайне мала. [5]
Выбор варианта разбиения графа Г на подграфы при решении задачи выбора оптимальной стратегии системной отладки сводится к выбору состава v групп, где v - число программных модулей комплекса, при соответствующих ограничениях на возможные комбинации программных модулей в группах. Выбор варианта объединения полученных при разбиении подграфов графа Г до исходной графовой структуры сводится к выбору состава этапов объединения V непустых подграфов в исходную графовую структуру. [6]
Предлагается алгоритм разбиения графа на плоские суграфы, основанный на использовании условия В, Ба-дера [169] и нахождении семейства максимальных внутренне устойчивых подмножеств множества вершин графа пересечений. [7]
Если при разбиении графа на цикл и связные компоненты среди полученных подмножеств ребер встречаются соединения, относящиеся ко второму случаю, то их необходимо свести к одному из видов первого случая, что выполняется формально по матрице смежности путем удлинения выбранного цикла. Если указанную операцию не выполнить, то в дальнейших преобразованиях из рассмотрения выпадает по крайней мере одно из ребер, которое могло бы влиять на планарность графа. [8]
Получено m - планарное разбиение графа. [9]
 |
Интерфейс графиков. [10] |
В таблице приведены различные данные разбиения графа, содержащего п 450 вершин и т 1000 ребер, на три части по 150 вершин в каждой с минимизацией количества внешних ребер. В первом столбце таблицы указываются номера проведенных экспериментов, во втором - количество вершин. Отметим, что в таблице приведены данные по исследованию разбиения одного нестандартного трудного теста. [11]
Сформулируем постановку задачи разбиения графа на заданное или произвольное число частей. Пусть задан граф G ( X, Е, W), где X представляет множество вершин графа, Е - множество ребер, aW - общий суммарный вес вершин. Вес вершины соответствует интегральной оценке, в которую могут входить различные конструкторско-технологические ограничения на исследуемую модель, причем значения Wi W не превышают некоторой пороговой величины. [12]
Сущность большинства алгоритмов разбиения графов заключается в выборе некоторого начального разбиения исходного графа и последующего его улучшения с помощью итерационного, парного или группового обмена вершин из различных частей разбиения. При этом для каждой итерации осуществляется перестановка таких вершин, которая обеспечивает максимальное уменьшение числа связей между частями разбиения графа или минимальное приращение числа внешних ребер. [13]
При решении проблем разбиения графов на части часто возникают задачи группировки элементов, обладающих одинаковыми свойствами. [14]
На рис. 6.4 показано разбиение графа G ( рис. 6.2) на две части по три вершины в каждой. Отметим, что генетическая процедура поиска может быть применена как единственная, так и множественная оптимизационная процедура. Кроме того, генетические операторы и операторы поиска могут быть вставлены в структурную схему генетического поиска как вспомогательные блоки для повышения качества последовательных алгоритмов. [15]
Страницы: 1 2 3 4