Member 11247684 Ответов: 1

Как создать связующее дерево в C# для заданного элемента матрицы

Мне нужно извлечь наилучший путь с точки зрения его длины из прямоугольного массива, подобного этому массиву:

Цитата:
|1||0||1||0|
|1||0||0||1|
|1||1||0||1|
|0||0||1||1|


Правила поиска пути:

1-Начните с индексов, указанных в сигнатуре метода, где rowIndex и colIndex являются позициями начальной точки.

2-они должны быть способны соединяться друг с другом по горизонтали, вертикали или диагонали.

3 - Вы не можете перейти к ячейке, содержащей ноль.

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

5-наилучший путь из всех извлеченных путей (возможных решений) является самым длинным с точки зрения связанных друг с другом.

6-Нет проблем, если значение начальной ячейки равно 0.

Я попробовал следующий алгоритм рекурсии, но он не работает для меня и генерирует неправильный вывод, т. е. не так, как ожидалось!!.

Вот результаты: Результаты 

        using System;
        using System.IO;
        using System.Text;
        using System.Drawing;
        using System.Collections;
        using System.ComponentModel;
        using System.Windows.Forms;
        using System.Data;
        using System.Threading;
        using AUV_Topology;
        using System.Collections.Generic;
        using System.Media;
        using System.Linq;

        namespace AUVtopology
        {
            public partial class Form1 : Form
            {        
              static int[,] array;
              static List<int[]> path;

// *******************************************************************************************************************************//
        //This method is used to make sure the coordinate array 
        //is contained in the list. List.contains(new int[] {val1,val2}) was not enough.
        static Boolean containsArray(List<int[]> list, int[] array)
        {
            if (array == null || array.Length == 0)
            {
                return false;
            }
            foreach (var listArray in list)
            {
                if (listArray != null && listArray.Length == array.Length)
                {
                    for (int i = 0; i < listArray.Length; i++)
                    {
                        if (i != listArray.Length - 1)
                        {
                            if (array[i] != listArray[i] && array[i + 1] != listArray[i + 1])
                            {
                                continue;
                            }


                            return true;

                        }

                    }

                }
            }
            return false;
        }    



// *******************************************************************************************************************************//

        //This is the recursive method of the algorithm. It finds the 
        //maximum path of 1 cells in a matrix of 0/1 cells
        static List<int[]> getMaxPath(int[,] array, List<int[]> maxPath, int rowIndex, int colIndex)
        {

            //Add the current cell to the path.
            maxPath.Add(new int[] { rowIndex, colIndex });

            //Get the array limits.
            int rowLength = array.GetLength(0);
            int colLength = array.GetLength(1);

            //If the path contains all the cells in the matrix, stop
            if (maxPath.Count >= rowLength * colLength)
            {
                return maxPath;
            }

            //remove one from lengths to make it the maximum index
            colLength = colLength - 1;
            rowLength = rowLength - 1;

            //We'll use this variable to see which of the 
            //potential 7 paths are the longest.
            List<int[]> futurePath;

            //Go over all 8 possible adjoining cells:
            //If we can go one down, one right, and it's a spot we 
            //have not yet visited
            if (colIndex < colLength && rowIndex < rowLength &&
                array[rowIndex + 1, colIndex + 1] == 1 &&
                !containsArray(maxPath, new int[] { rowIndex + 1, colIndex + 1 }))
            {

                //We use maxPath first, since this is the first 
                //direction and by default is the longest
                maxPath = getMaxPath(array, maxPath, rowIndex + 1, colIndex + 1);
            }

            //If we can go one down, and it's a spot we have not
            //yet visited
            if (colIndex < colLength &&
              array[rowIndex, colIndex + 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex, colIndex + 1 }))
            {

                //We use futurePath now, since this is a second
                //direction and a potential contender
                futurePath = getMaxPath(array, maxPath, rowIndex, colIndex + 1);

                //We only need the maximum path.
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //If we can go one down and one left, and it's a spot
            //we have not yet visited
            if (rowIndex > 0 && colIndex < colLength &&
               array[rowIndex - 1, colIndex + 1] == 1 &&
               !containsArray(maxPath, new int[] { rowIndex - 1, colIndex + 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex + 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //If we can go one left, and it's a spot we have not
            //yet visited
            if (rowIndex > 0 &&
               array[rowIndex - 1, colIndex] == 1 &&
               !containsArray(maxPath, new int[] { rowIndex - 1, colIndex }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one left and one up, and it's a spot we
            //have not yet visited
            if (rowIndex > 0 && colIndex > 0 &&
              array[rowIndex - 1, colIndex - 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex - 1, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one up, and it's a spot we have not yet
            //visited
            if (colIndex > 0 &&
                array[rowIndex, colIndex - 1] == 1 &&
                !containsArray(maxPath, new int[] { rowIndex, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one up and one right, and it's a spot we
            //have not yet visited
            if (colIndex > 0 && rowIndex < rowLength &&
              array[rowIndex + 1, colIndex - 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex + 1, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex + 1, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one right, and it's a spot we have not
            //yet visited
            if (rowIndex < rowLength &&
              array[rowIndex + 1, colIndex] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex + 1, colIndex }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex + 1, colIndex);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //We return the max path. Note: If none of the directions around 
            //us was applicable, we simply return the path we started 
            //with our cell included.
            return maxPath;
        }


Так что я думал по-другому!!. Если мы можем сгенерировать связующее дерево для каждого узла с помощью еще одной вещи; то есть вы можете вернуться к более низкой ячейке с точки зрения ее индексов, если она не указана в качестве предыдущего родителя. Смотрите пример:

Видеть изображение

Ветвь внутри круга с синим цветом представляет собой самый длинный путь с точки зрения количества ячеек со значением 1.
Мой вопрос в том, как это реализовать. Как создать массив для каждой ветви, чтобы сравнить их по длине и получить самую длинную как лучшее решение ?.

Что я уже пробовал:

Функция рекурсии для извлечения пути в виде правил, но я не работал для меня, так как это дало неправильные результаты и с большим размером массива это сделало переполнение стека!!.

1 Ответов

Рейтинг:
0

Member 13291909 

using System; 
using System.Collections.Generic; 
 
namespace Prim 
{ 
    class PriorityQueue 
    { 
        int heapSize; 
        List<Node> nodeList; 
 
        public List<Node> NodeList 
        { 
            get 
            { 
                return nodeList; 
            } 
        } 
 
        public PriorityQueue(List<Node> nl) 
        { 
            heapSize = nl.Count; 
            nodeList = new List<Node>(); 
 
            for (int i = 0; i < nl.Count; i++) 
                nodeList.Add(nl[i]); 
        } 
 
        public void exchange(int i, int j) 
        { 
            Node temp = nodeList[i]; 
 
            nodeList[i] = nodeList[j]; 
            nodeList[j] = temp; 
        } 
 
        public void heapify(int i) 
        { 
            int l = 2 * i + 1; 
            int r = 2 * i + 2; 
            int largest = -1; 
             
            if (l < heapSize && nodeList[l].Key > nodeList[i].Key) 
                largest = l; 
            else 
                largest = i; 
            if (r < heapSize && nodeList[r].Key > nodeList[largest].Key) 
                largest = r; 
            if (largest != i) 
            { 
                exchange(i, largest); 
                heapify(largest); 
            } 
        } 
 
        public void buildHeap() 
        { 
            for (int i = heapSize / 2; i >= 0; i--) 
                heapify(i); 
        } 
 
        int heapSearch(Node node) 
        { 
            for (int i = 0; i < heapSize; i++) 
            { 
                Node aNode = nodeList[i]; 
 
                if (node.Id == aNode.Id) 
                    return i; 
            } 
 
            return -1; 
        } 
 
        public int size() 
        { 
            return heapSize; 
        } 
 
        public Node elementAt(int i) 
        { 
            return nodeList[i]; 
        } 
 
        public void heapSort() 
        { 
            int temp = heapSize; 
 
            buildHeap(); 
            for (int i = heapSize - 1; i >= 1; i--) 
            { 
                exchange(0, i); 
                heapSize--; 
                heapify(0); 
            } 
 
            heapSize = temp; 
        } 
 
        public Node extractMin() 
        { 
            if (heapSize < 1) 
                return null; 
 
            heapSort(); 
 
            exchange(0, heapSize - 1); 
            heapSize--; 
            return nodeList[heapSize]; 
        } 
 
        public int find(Node node) 
        { 
            return heapSearch(node); 
        } 
    } 
}

Member 11247684

Как называется этот алгоритм? и как это назвать для моего случая? не могли бы вы оптимизировать свой ответ ?