WikiDer > Многоуровневая техника
 | Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) (Узнайте, как и когда удалить этот шаблон сообщения)
|
В математике многоуровневая техника это метод, используемый для решения проблема разбиения графа.
Идея многоуровневой техники состоит в том, чтобы уменьшить величину график объединяя вершины вместе, вычислить раздел на этом сокращенном графе и, наконец, спроецируйте это разбиение на исходный граф.
На первом этапе величина графа уменьшается за счет слияния вершин. Объединение вершин выполняется итеративно: из графа создается новый более грубый граф, а из этого нового более грубого графа создается еще более грубый граф. Это делается до тех пор, пока не появится некий небольшой величина достигнуто. Таким образом индуцируются графы с разной величиной.
На втором этапе вычисляется разбиение графа с наименьшей величиной - самый грубый график.
На третьем и последнем этапе вычисленное разделение итеративно проецируется обратно на исходный граф. На каждой итерации уточнение эвристический применяется. Слияние вершин индуцирует отображение между вершинами графа и вершинами его более грубого графа, которое используется для обратной проекции. Может потребоваться повторная балансировка, чтобы гарантировать размер раздела, поскольку вершины, не принадлежащие одному разделу, могут быть объединены.
Показано, что многоуровневая техника значительно улучшает результаты как с точки зрения качества, так и с точки зрения времени выполнения. Особенно при использовании эвристики, рассматривающей граф только локально, поскольку многоуровневая техника представляет собой более глобальное представление о графике.[1]
Рекомендации
- ^ Г. Карипис, В. Кумар (1999). «Быстрая и качественная многоуровневая схема для разбиения нерегулярных графов». Журнал SIAM по научным вычислениям.