Проблема с производительностью с алгоритмом Vue. js Дейкстры

Question

Я пишу университетский проект, в котором я беру два алгоритма и сравниваю их производительность, основные алгоритмы - Dijkstra и A *, но я не очень разбираюсь ни с Vue. и алгоритмы, и моя первая итерация Дейкстры СУПЕР медленная. Я использую двумерную сетку X на Y с узлом начальной и конечной точки и запускаю алгоритм. Любая сетка выше 10x10 работает слишком медленно.

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

    export default ({
        name: 'Home',
        data() {                                                   // global variables init
            return {
                grid: [],                                          // initializing grid array, rows and columns
                todis: "",                                         // to display
                output: [],                                        // shortest path array
                toCheck: [],                                       // checking neighboring nodes
                startx: Number(0),                                 // starting x position of algorithm
                starty: Number(0),                                 // starting y position of algorithm 
                endx: Number(0),                                   // end x position of algorithm   
                endy: Number(0),                                   // end y position of algorithm 
                sxy: [0, 0],                                       // start x, y array coordinates
                exy: [0, 0],                                       // end x, y array coordinates
                wallx: Number(0),                                  // wall x coordinate
                wally: Number(0)                                   // wall y coordinate
            };
        },
        methods: {                                                 // all needed methods
            addToGrid(adding) {                                    // create the grid 
                this.grid.push(adding)
            },
            setwall(x, y) {
                this.grid[Number(y)][Number(x)].id = 1
            },
            updates(x, y) {                                        // update start position on button press
                this.sxy = [Number(x), Number(y)]
            },
            updatee(x, y) {                                        // update end position on button press
                this.exy = [Number(x), Number(y)]
            },
            makeGrid(width, height) {                              // takes two values to make a grid
                function Node(x, y, id) {                          // 0 - unchecked; 1 - Wall; 2 - Start; 3 - End; 4 - Checked; 5 - Shortest Path
                    this.x = x                                     // initialization of values for class Node
                    this.y = y
                    this.id = id
                    this.visited = false
                    this.prev = []
                }
                if (this.grid.length === 0) {                      // Stops grid being made multiple times
                    for (let y = 0; y < height; y++) {
                        let row = []                               // Create a row, need new empty array every time we go through a row
                        for (let x = 0; x < width; x++) {          // Create nodes for the width of the grid
                            var newNode = new Node(x, y, 0)        // give values x, y, id to the node
                            row.push(newNode)                      // push a node to the row array
                        }
                        this.addToGrid(row)                        // we add row array to grid
                    }
                }
            },
            Dijkstra(start, end) {                          
                this.grid[start[1]][start[0]].id = 2               // node array coordinates (w, h we got from inputs from the front end) width height values set to id of 2, which is the start of the grid 
                this.grid[end[1]][end[0]].id = 3                   // node array coordinates (w, h) for end point, which has an id of 3
                function findNeighbours(grid, x, y) {              // scanning the neighboring nodes, takes the whole grid
                    let Neighbours = []                            // initializing values for neighbours
                    let PosNeighbours = []                         // position of new neighbours
                    let cnode = null                               // checked node 
                    grid[y][x].visited = true
                    if (grid[y][x].id === 0) {                     // if the node at y, x id is 0 (unchecked), set it to checked (for colouring)
                        grid[y][x].id = 4
                    }
                    try {                                          // we go to the right of of the node
                        cnode = grid[y][x + 1]                     // x + 1 and if the node:
                        if (typeof cnode !== "undefined") {        // is valid
                            if (cnode.id !== 1) {                  // is not a wall
                                PosNeighbours.push(grid[y][x + 1]) // we add set the neighbour position to that value
                            }
                        }
                    }
                    catch{
                        null
                    }
                    try {                                          // we go to the left of the node
                        cnode = grid[y][x - 1]                     // x - 1 and if the node:
                        if (typeof cnode !== "undefined") {        // is valid
                            if (cnode.id !== 1) {                  // is not a wall
                                PosNeighbours.push(grid[y][x - 1]) // we add set the neighbour position to that value
                            }
                        }
                    }
                    catch{
                        null
                    }
                    try {                                          // we go to the top of the node
                        cnode = grid[y + 1][x]                     // y + 1 and if the node:
                        if (typeof cnode !== "undefined") {        // is valid
                            if (cnode.id !== 1) {                  // is not a wall
                                PosNeighbours.push(grid[y + 1][x]) // we add set the neighbour position to that value
                            }
                        }
                    }
                    catch{
                        null
                    }
                    try {                                          // we go to the bottom of the node 
                        cnode = grid[y - 1][x]                     // y - 1 and if the node: 
                        if (typeof cnode !== "undefined") {        // is valid
                            if (cnode.id !== 1) {                  // is not a wall
                                PosNeighbours.push(grid[y - 1][x]) // we add set the neighbour position to that value    
                            }
                        }
                    }
                    catch{
                        null
                    }
                    for (let node of PosNeighbours) {              // for each neighboring node
                        if (typeof grid[node.y][node.x] === 'undefined') {
                            null                                   // if the node is not valid, do nothing
                        }
                        else {
                            if (node.visited === false) {          // if the node is not visited, we add the value to the neighbours array
                                Neighbours.push(node)              // we set the new x and new y value to our current node position
                                let nx = node.x
                                let ny = node.y
                                if (grid[ny][nx].prev !== []) {    // if the new grid position has no previous value 
                                    grid[ny][nx].prev = grid[y][x] // we set the previous value to the old x and y positions
                                }
                            }
                        }
                    }
                    return [Neighbours, grid]                      // ??? return an array of nodes visited and whole grid ???
                }
                if (start !== end) {                               // we start the algorithm if the start node is not the same as the end node
                    let startNode = this.grid[start[1]][start[0]]  // set the start node, the checking array, give it a start node and declare what to check next
                    this.toCheck = []           
                    this.toCheck.push(startNode)
                    let toChecknext = []
                    while (this.grid[end[1]][end[0]].visited === false) {
                        if (this.toCheck.length !== 0) {           // while we haven't visited the end node, or if we haven't checked all the nodes
                            let node = this.toCheck.shift()        // we set the node to the first value of our toCheck array
                            let fn = findNeighbours(this.grid, node.x, node.y)
                            let nodestoadd = fn[0]                 // we call the findNeighbours function and set the nodes to add to Neighbours 
                            this.grid = fn[1]                      // grid generated with grid values of the the function
                            for (let node of nodestoadd) {         // for each node in the nodestoadd array we push the node valeu to the next node to check
                                toChecknext.push(node)
                            }
                        } else {                                   // otherwise, set the next node to check to the node we are currently at
                            for (let node in toChecknext) {
                                this.toCheck.push(node)
                            }
                        }
                    }
                    let currentNode = this.grid[end[1]][end[0]]    // we set up our currentNode end, if our current node x, y are not the same 
                    let pathnodes = []
                    while (currentNode.x !== startNode.x || currentNode.y !== startNode.y) {
                        pathnodes.push(currentNode.prev)           // we create a path of the previous nodes, using a pathnodes array
                        currentNode = currentNode.prev
                    }
                    let pathnodexy = []                            
                    for (let node of pathnodes) {                  // for each node in the pathnodes array (all the nodes for our shortest path)
                        pathnodexy.push([node.x, node.y])          // we give the pathnodexy array x, y values of the nodes
                        if (this.grid[node.y][node.x].id == 4) {   // if that node has been visited with id 4, we set that to id 5, which is the id of the path
                            this.grid[node.y][node.x].id = 5
                        }
                    }
                    this.output = pathnodexy                       // we set the output value and start the algo
                } else {
                    return [start]
                }
            },

            displayGrid(grid) {                                    // we create a string method, that creates a grid with the ID values we defined
                this.todis = "<div id='block_container'>"
                for(const row of grid) {                           // for each row, and each node in that row we set the ID value of the node and generate html to create our grid
                    for (const node of row) {
                        this.todis += "<button @click.self='changewall' id='block-id-"+node.id+"'></button>"
                    }
                    this.todis += "</div><div id='block_container'>"
                }
                this.todis = this.todis+"</div>"
                return this.todis                                   // we return the constructed html
            },
            changeGrid(thisx, thisy) {
                this.grid[thisy][thisx].id = 1
            }
        },
        created: function () {
            this.makeGrid(7, 7)

        },
        updated: function () {
            // on update
        }
    });

Answer 1

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

• for (let node in toChecknext): это будет повторять индексы массива, а не значений. Тем не менее, вы относитесь к этим значениям как к узлам, что приведет к нежелательному поведению. Измените на:

  for (let node of toChecknext)
  

Есть и другие, не критичные проблемы:

• if (grid[ny][nx].prev !== []) будет всегда верно, потому что вновь созданный массив никогда не может быть тем же объектом, что и уже существующий объект. Я предполагаю, что вы сначала попробовали с === [], потом обнаружили, что это всегда false, а затем просто переключили его. Вместо этого инициализируйте prev как null и просто проверьте, является ли prev истинным значением. Также просто укажите node вместо grid[ny][nx], который на самом деле является тем же самым объектом (подробнее об этом см. В другом пункте ниже в этом списке):

  this.prev = null; // in Node constructor
  /* ... */
  if (node.prev)
  

• toChecknext никогда не сбрасывается. Должен, иначе алгоритм будет делать ненужную работу. Каждый раз, когда вы копируете содержимое toChecknext в this.toCheck, вы должны очистить toChecknext, чтобы не проверять узлы, которые уже посещены. Поэтому после копии добавьте:

  toChecknext.length = 0;
  

• Нет никаких условий для случая, когда нет пути. Алгоритм попадет в бесконечный l oop. При условии, что вы выполнили предыдущее исправление, также добавьте этот блок перед else:

  } else if (toChecknext.length == 0) {
      this.output = [];
      return []; // No solution!
  

• В пути pathnodes отсутствует конечный узел. Поэтому инициализируйте его с помощью:

  let pathnodes = [currentNode];
  

• Путь pathnodexy на самом деле перевернут, поскольку он перечисляет координаты от конца до начала. Итак, сделайте это:

  this.output = pathnodexy.reverse();
  

• В случае, если начальный узел является конечным узлом, вы return путь, но во всех остальных случаях вы не возвращаете его, а устанавливаете недвижимость. Это непоследовательно. Итак, в случае else сделайте следующее:

  this.output = [start];
  

  , а за пределами блока if..else выполните:

  return this.output;
  

• Делать что-то излишне. например, this.grid[node.y][node.x].id, что на самом деле node.id. Это происходит в нескольких местах вашего кода. Другой пример - currentNode.x !== startNode.x || currentNode.y !== startNode.y, что может быть просто currentNode != startNode. Есть и другие случаи, которые я не буду перечислять ...

• Бесполезно передавать this.grid на findNeighbours, а затем findNeighbours возвращать его. Любая мутация, которую вы сделали для этого аргумента grid, будет прямо на this.grid. grid - это ссылка на то же, что и this.grid. Поэтому просто удалите этот параметр, и пусть функция будет работать с this.grid вместо grid, и просто вернет список соседей.

• Не используйте try { ... } catch { null }, как вы риск пропустить ошибки, которых вы не ожидали.

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