Сътрудник на Obirvalger

1.1.2 Критерии за разлагане

В зависимост от спецификата на проблема, който се решава, могат да бъдат наложени различни изисквания за вида на декомпозицията на графиката. Има много критерии за декомпозиция, но най-класическият от тях е минимизирането на максималното тегло на ръбовете, излизащи от домейна (в най-простия случай, минимизирането на броя на режените ръбове). Други критерии включват следното:

  • разпределяне на отделни домейни;
  • минимизиране на максималния обхват на домейни;
  • осигуряване на домейн свързаност;
  • осигуряване на свързаността на много вътрешни домейнови възли.

1.1.3 Метод на рекурсивно разделяне

Методът на рекурсивно координирано разделяне е частен случай на по-общ метод на рекурсивна бисекция. При този метод решетката се разделя последователно на [math] k [/ math] части след стъпка [math] k-1 [/ math]. На първата стъпка мрежата се разделя на две части, след това всяка от получените по-рано части също се разделя на две части и т.н. Специфични алгоритми за разделяне на мрежата на две части (bisections) определят метода на рекурсивно bisection. Съотношението на размерите на частите зависи от броя на домейните и процедурата за изчисляване на желания брой върхове във всяка от формираните части на графиката.

1.1.4 Метод на рекурсивно координирано разделяне

За разлагането на големи мрежи се използват паралелни алгоритми, като се приема, че мрежата вече е разпределена по възлите на процесора. Те са ефективни само ако върховете са разпределени по процесорите в компактни групи, а не произволно. Докато алгоритмите за декомпозиция започват да работят, все още не е намерено мрежово декомпозиция, така че е необходим някакъв прост начин за предварително разпределение на графиката между процесорите, извършващи декомпозицията. За да се реши този проблем, се използва методът на рекурсивно координатно деление. Въпреки факта, че той отстъпва по качество на генерираното разлагане на някои други методи, препоръчително е да го използвате на предварителния етап, поради скоростта на работа, фокуса върху разпределената обработка и простотата.

Методът на рекурсивно координирано bisection се основава на метода на рекурсивно bisection. Следващата процедура се използва за разделяне на мрежата на две части:

  • е избрана една от координатните оси;
  • множеството върхове се сортира по тази координата;
  • сортираният набор е разделен на две части, т.е. индексът [math] i [/ math] е посочен така, че първата част съдържа върховете с числа, по-малки или равни на [math] i [/ math], и второ - останалите върхове; геометрично, това съответства на хиперплоскост, перпендикулярна на избраната ос, която разделя множеството мрежести върхове на две части, чието съотношение зависи

1.1.5 Избор на координатна ос

В зависимост от критериите за разлагане и други характеристики на проблема могат да се използват различни критерии за избор на координатната ос, по която мрежата ще бъде разделена на две части. Най-често използваните са следните:

  • Дължината на областта по дадена ос: за всяка ос се изчислява разликата между максималната и минималната координати на върховете на мрежата по дадена ос и се избира оста с най-голямата стойност на тази стойност;
  • Броят на режените ръбове при разделяне на окото по дадена ос: върховете са подредени по всяка от осите и е избрана опцията, която води до най-малък брой режещи ръбове;

1.2 Математическо описание на алгоритъма

Първоначални данни: графика [math] G = (V, E) [/ math], вложена в [math] \ mathbb ^ N [/ math] (т.е. всеки връх на тази графика е точка в [math] N [/ math] размерно пространство) и броя [math] k [/ math] на домейни, в които да се раздели графиката. Под разлагане Графика в [math] k [/ math] домейни означава разделяне на набора от върхове [math] V [/ math] в [math] k [/ math] подмножества [math] V_1, \ dots, V_k [/ math ] такъв, че

[математика] V = \ bigcup_^ k V_i [/ ​​math] и [math] V_i \ cap V_j = \ varnothing [/ math] за [math] i \ neq j [/ math] .

Всеки домейн може да бъде свързан с подграфа, генериран от него [math] G (V_i) = (V_i, E_i) [/ math], където [math] E_i \ subseteq E [/ math] е набор от ръбове, двата края на които принадлежат към домейна.

Задачата е да се намери разлагането [math] V_1, \ dots, V_k [/ math], като се осигури минимумът на някои функционалности (вижте съответния абзац), например броят на изрязаните ръбове [math] E_> = | \ | = | E | - \ sum_^ k | E_i | [/ математика] .

Нека дадем официално описание на алгоритъма. Както вече споменахме, методът се основава на рекурсивен алгоритъм на бисекция, следователно е рекурсивна процедура, чийто вход е графиката [math] G = (V, E) [/ math] и броят на домейните [math ] k [/ math], с което трябва да разделите набора от върхове на дадената графика. Вътре в тази процедура се извършва следната последователност от действия:

  • в зависимост от броя на домейните се изчислява "желаният" брой домейни и върхове във всяка част на дяла;
  • процедурата за разделяне на координати се извиква, за да се получи графичното разделяне на две части;
  • за всяка от двете получени части описаната процедура се извиква рекурсивно (ако броят на домейните за тази част е повече от един).

Процедурата за разделяне на координати е структурирана, както следва:

  • координатната ос е избрана [math] m ^ * \ in \ [/ math];
    • в случай на максимизиране на дължината: за всяка ос [math] m [/ math] се изчислява стойността [math] l_m = \ max_ v_m - \ min_ v_m [/ math] и оста [math] m ^ * = \ arg \ max_> l_m [/ math];
    • в случай на минимизиране на броя на режените ръбове: върховете са подредени по всяка от осите, за всяка ос се изчислява стойността [math] E ^ m _> [/ math], равна на броя на режените ръбове при разделяне по тази ос и е избрана оста [math] m ^ * = \ arg \ max_> E ^ m _> [/ math];