Оптимизация создания матрицы смежности из 2D-массива узлов

Question

Я пытаюсь создать матрицу смежности из 2D-массива узлов. Матрица смежности будет передан в программу, будут группироваться узлы либо через

1. Спектральный алгоритм кластеризации
2. алгоритм кластеризации Kmeans

** класса Node **

public class Node{ 
    public int _id; 
    public bool _isWalkable; 
    public int _positionX; 
    public int _positionY; 
    public Vector3 _worldPosition; 
    } 

Класс сетки

public class Grid : MonoBehaviour 
    { 

     void CreateGrid() 
     { 
     grid = new Node[_gridSizeX, _gridSizeY]; 
     Vector3 worldBottomLeft = transform.position - 
     Vector3.right * worldSize.x/2 - Vector3.forward * worldSize.y/2; 

     //set the grid 
     int id = 0; 

     for (int x = 0; x < _gridSizeX; x++) 
     { 
      for (int y = 0; y < _gridSizeY; y++) 
      { 
       Vector3 worldPosition = worldBottomLeft + Vector3.right * 
        (x * _nodeDiameter + _nodeRadius) + 
        Vector3.forward * (y * _nodeDiameter + _nodeRadius); 
       //check to see if current position is walkable 
       bool isWalkable = 
        !Physics.CheckSphere(worldPosition, _nodeRadius, UnwalkableMask); 

       grid[x, y] = new Node(isWalkable, worldPosition, x, y); 
       grid[x, y].Id = id ++; 

      } 
     } 
     totalNodes = id; 
    } 
} 

Узлы хранятся внутри 2D-массива, называемого сеткой, и представляют собой путь, способный двигаться, чтобы персонаж мог двигаться дальше. Я успешно реализовал алгоритм A * с эвристикой эвклидовой дистанции. Я бы хотел, чтобы кластер этих узлов использовал вышеупомянутые алгоритмы кластеризации, но сначала мне нужно создать для них алгоритм смежности. Это лучший псевдокод я мог придумать

int[][] _adjacencyMatrix = new int[gridSizeX*gridSizeY][gridSizeX*gridSizeY]; 

    for(int x = 0; x < gridSize;x< XgridSize; i++) 
    { 
     for(int y = 0; y < gridSize;y< YgridSize; i++) 
     { 
      if(!Grid[x][y]._isWalkable) 
       continue; 
      Node n = Grid[x][y]; 
      List<Node> neighbors = GetNeighbors(n); 
      for(int k; k<neighbors.Count(); k++) 
      { 
       _adjacencyMatrix[n._id][neighbors[k]._id]=1; 
      } 
     } 
    } 

    public List<Node> GetNeighbours(Node n) 
    { 
     //where is this node in the grid? 
     List<Node> neighbours = new List<Node>(); 

     //this will search in a 3X3 block 
     for (int x = -1; x <= 1; x++) 
     { 
      for (int y = -1; y <= 1; y++) 
      { 
       if (x == 0 && y == 0) 
        continue; //we're at the current node 

       int checkX = n._positionX + x; 
       int checkY = n._positionY + y; 

       if (checkX >= 0 && checkX < _gridSizeX && checkY >= 0 
        && checkY < _gridSizeY) 
       { 
        if(grid[checkX, checkY]._isWalkable) 
         neighbours.Add(grid[checkX, checkY]); 
        else 
         continue; 
       } 
      } 

     } 
     return neighbours; 

    } 

Моя главная забота

Моя главная забота с этим общая сложность алгоритма выше. Похоже, что это будет тяжело, и у меня есть в общей сложности (75^2 = 5625) узлов в матрице смежности, размер которой будет 5625X5625! Должен быть лучший способ найти соседей, чем это, не так ли?

Answer 1

Матрица симметрична, поэтому вам нужно сохранить ее половину, см. (How to store a symmetric matrix?) для примера. Матричные значения являются двоичными, поэтому сохранение их в виде булевых элементов или в битовом векторе сократит объем памяти в 4 или 32 раза соответственно.

В качестве альтернативы, поскольку проверка для двух соседних узлов принимает постоянное время (abs(n1.x - n2.x) <= 1 && abs(n1.y - n1.y) <= 1 && grid[n1.x, n2.x].isWalkable() && grid[n2.x, n2.y]), вы можете просто передать алгоритму кластеризации функцию, которая проверяет смежность на лету.

Answer 2

5k by 5k не очень большой. 100 МБ - это то, что вы можете сохранить в памяти. Если вы хотите избежать этой стоимости, не используйте алгоритмы, основанные на матрицах расстояний!

Однако, поскольку ваше сходство, как представляется,

д (х, у) = 1, если р дом и оба узла проходимую еще 0

ваши результаты будут вырождаются. Если вам повезет, вы получаете что-то вроде подключенных компонентов (которые вы могли бы получить намного проще). Пустые кратчайшие пути были бы более полезными, но также более дорогими для сборки. Может быть, подумайте об этом. Думаю, наличие полной матрицы смежности - хорошая отправная точка.

k-средство не может работать с попарными расстояниями вообще. Ему нужны расстояния только от точки к среднему, для любых средств.

Предлагаю взглянуть на алгоритмы графа и потратить некоторое время на понимание своей цели, прежде чем пытаться сжать данные в алгоритмы кластеризации, которые могут решить другую проблему.