AnswerBun.com

Расширение матрицы смежностей

Stack Overflow на русском Asked on January 6, 2022

Есть некоторое псевдо дерево квадрантов, которое изначально представляет из себя четыре прилежащих друг к другу областей:

введите сюда описание изображения

Слева представлена матрица смежностей этих четырех элементов. Для индексации используеться одно правило A – по часовой от верхнего левого угла.

Теперь, скажем, я хочу разбить область №2 на четыре части.

введите сюда описание изображения

Чтобы обновить матрицу смежностей я должен заменить элемент №2 матрицей подобной изначальной, согласно установленному правилу A (зеленая зона).

введите сюда описание изображения

Собсвенно вопрос заключается есть ли операция или серия операция в математике матриц, которые позволили бы подставить вместо одного элемента другую матрицу смежностей и пересчитать связи между новыми и старыми элементами (красная зона)??

2 Answers

Такая концепция есть: иерархические матрицы (с соответсвующим набором операций иерархической матричной арифметики). В данном представлении, матрица представляет собой в общем случае - дерево матриц, c данными хранящимися на листьях, при этом листья могут быть расположены на разных уровнях.

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

Кроме того, замечание Mikhailo имеет полную силу:

введите сюда описание изображения

соседствование 3 с индивидуальными элементами 2.1, 2.2, 2.3 и 2.4 не определяется напрямую из структуры (в общем случае и с произвольными модификациями областей).

Поэтому, советую обратить внимание на более простые структуры данных и представление смежности. В зависимости от прикладной задачи, такие структуры как k-d деревья могут быть гораздо предпочтительнее.

Answered by Anton Menshov on January 6, 2022

В общем случае - никак. Просто потому, что одного описания зеленой матрицы недостаточно - надо еще описывать, как ее НОВЫЕ ЭЛЕМЕНТЫ (на которые она разбита) соотносятся со старыми.

Из зеленой матрицы никак не следует, что с 3 смежны 2.1 и 2.3, а не 2.2 и 2.4. Если вы замените в зеленой матрице 2.1 и 2.3, зеленая матрица не изменится, а вот красные поменяются. Так что ожной зеленой матрицы мало, и такая операция невозможна.

Answered by Mikhailo on January 6, 2022

Add your own answers!

Related Questions

Не сохраняются cookie в php-webdriver

0  Asked on December 31, 2020 by vadosiq

   

Совет Си/Си++. Синтаксический разбор

0  Asked on December 29, 2020 by cyberwaffl

   

Сетка на гридах в IE

0  Asked on December 28, 2020

   

Qt наследование и parent

0  Asked on December 27, 2020 by slav9n92

   

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir