Блог

Существует сетка.

 static Double [][] myTiles = new Double[row][column];
 

Цель состоит в том, чтобы соединить каждый лист с соседним листом. Сравните значение между парой, создайте связь между плитками, чтобы создать минимальное связующее дерево для данной сетки.

Ниже приведен мой первоначальный подход к этой проблеме:

Идентифицировано девять ( 9) групп листов.

Эти группы имеют одинаковую логику и одинаковую доступность смежных квадратов.

Для каждой ячейки в моей сетке я решил проверить ячейку сверху, снизу, слева и справа. Некоторые ячейки не могут выполнять все проверки, если они расположены на краю сетки. Ниже представлено представление перемещения для каждого типа листа.

Мое текущее решение представляет собой вложенный цикл for с приведенными ниже операторами if-else:

             if ( row == 0 amp;amp; column == 0)   {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));     }
            
            else if ( row == 0 amp;amp; ( column > 0 amp;amp; column < myTiles.length ) )   {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( row == 0 amp;amp; column == myTiles.length )    {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( ( row > 0 amp;amp; row < myTilese[row].length ) amp;amp; column == 0 )    {
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));    }
            
            else if ( row == myTilese[row].length amp;amp; column == 0 )  {
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));    }
            
            else if ( row == myTilese[row].length amp;amp; ( column > 0 amp;amp; column < myTiles.length ) )    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( row == myTilese[row].length amp;amp;  column == myTiles.length )    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));     }
            
            else if ( ( row > 0 amp;amp;  row < myTilese[row].length ) amp;amp; column == myTiles.length )  {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));}
            
            else    {
                mySortingQueue.offer(createEdgeNorth(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeEast(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeWest(myEdge, myTiles, row, column));
                mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, row, column));}
 

Приведенная выше логика создает не менее двух ссылок и не более четырех.
Это много дубликатов для сортировки, когда дело доходит до построения минимального связующего дерева.

Существует ли красноречивый способ представления вышеупомянутого блока if-else?

Это намного проще:

 if(row > 0) {
    // north
}
if(row < height) {
    // south
}
if(column > 0) {
    // west
}
if(column < width) {
    // east
}
 

Очевидно, это предполагает, что у вас есть как минимум сетка 2×2.

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

Наиболее эффективный способ — ограничить количество ссылок, создаваемых на один лист.

Чтобы логика создавала меньше дубликатов, полезно избежать решения с вложенными циклами и вместо этого реализовать два отдельных цикла for .

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

Второй шаг: выполните итерацию по каждому листу каждого столбца строка за строкой и сделайте одну ссылку на юг или вниз, пока не будет обнаружено ребро. Когда ребро обнаружено, пропустите указатель на один столбец вправо.

Эта логика охватывает все листы, предотвращает проверки IndexOutOfBoundsChecks и уменьшает количество создаваемых повторяющихся ссылок.

         for ( tileColumn = 0; tileColumn < 74; tileColumn    )  {
            myEdge = new GraphEdge<String>();
            
            mySortingQueue.offer(createEdgeEast(myEdge, myTiles, tileRow, tileColumn));
            
            if ( tileColumn == 73 amp;amp; tileRow < 34 ) {   
                tileColumn = 0;
                tileRow  ;  }
        }   /*  End of the column for loop  */
        
        tileRow = ZERO;
        tileColumn = ZERO;
        
        for ( tileRow = 0; tileRow < 34; tileRow   )    {
            myEdge = new GraphEdge<String>();
            mySortingQueue.offer(createEdgeSouth(myEdge, myTiles, tileRow, tileColumn));
            
            if ( tileRow == 33 amp;amp; tileColumn < 74)  {   
                tileRow = 0;
                tileColumn  ;   }
        }   // End of the row for loop