Golang Проблема коммивояжера по сетке - Моя рекурсия отключена?

Question

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

По сути, мне нужно получить путь минимального веса с левой стороны сетки справа, учитывая размеры сетки и ее содержимое. Количество строк будет от 1 до 10 включительно; количество столбцов будет от 1 до 100 включительно. Вес пути не превышает целочисленных значений, представимых с помощью 30 битов. Мы отправляемся к соседним узлам. В ссылке есть визуальный элемент, если это поможет. Таким образом, ввод может выглядеть так:

10 10
8 8 8 8 8 8 8 8 8 8
8 8 7 8 8 8 8 8 8 8
8 7 8 7 8 8 8 8 8 8
7 8 8 8 7 8 8 8 8 8
8 8 8 8 8 7 8 8 8 8
8 8 8 8 8 8 7 8 8 8
8 8 8 8 8 8 8 7 8 7
8 8 8 8 8 8 8 8 7 8
8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10 9 10

и должен выводить:

4 3 2 3 4 5 6 7 8 7
70
1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19

Вот мой супер-уродливый код.

package main

import (
   "bufio"
   "fmt"
   "os"
   "strconv"
   "strings"
)

type gridNode struct {
   weight   int
   location []int
   adjNodes []gridNode
   isEnd    bool
}

func (n gridNode) getX() int {
   return n.location[1]
}

func (n gridNode) getY() int {
   return n.location[0]
}

// This function converts string array to integer array
func convertToIntArr(stringArr []string) []int {
   var returnArr []int
   for _, item := range stringArr {
       integer, _ := strconv.Atoi(item)
       returnArr = append(returnArr, integer)
   }
   return returnArr
}

// This works fine as well, though moveY changes the path output slightly
func getAdjNodes(grid [][]gridNode, currentNode gridNode) []gridNode {
   moveY := []int{0, -1, 1}
   var adjNodes []gridNode
   maxHeight := len(grid)
   nextCol := currentNode.getX() + 1
   currentY := currentNode.getY()

   for _, yDiff := range moveY {
       adjNode := grid[getNewY(maxHeight, currentY+yDiff)][nextCol]
       adjNodes = append(adjNodes, adjNode)
   }

   return adjNodes
}

func getNewY(gridHeight int, maybeY int) int {
   if maybeY < 0 {
       maybeY = gridHeight - 1
   } else if maybeY == gridHeight {
       maybeY = 0
   }
   return maybeY
}

func getPathWeight(path []gridNode) int {
   totalWeight := 0
   for _, node := range path {
       totalWeight += node.weight
   }
   return totalWeight
}

// This function returns if a weight is found in the grid
func contains(arr [][]gridNode, num int) bool {
   for arrindex := range arr {
       for _, b := range arr[arrindex] {
           if b.weight == num {
               return true
           }
       }
   }
   return false
}

// FOR OUTPUT
func getRows(path []gridNode) string {
   rowString := ""
   for i, item := range path {
       rowString = rowString + strconv.Itoa(item.getY()+1)
       if i < len(path)-1 {
           rowString = rowString + " "
       }
   }
   return rowString
}

func getSmallestNode(nodes []gridNode) gridNode {
   var smallestNode gridNode
   for _, node := range nodes {
       if node.weight < smallestNode.weight || smallestNode.weight == 0 {
           smallestNode = node
       }
   }
   return smallestNode
}

// Function I'm concerned about
func findPath(grid [][]gridNode, currentNode gridNode, allPaths *[][]gridNode, path []gridNode) {
   path = append(path, currentNode)
   currentNode.adjNodes = getAdjNodes(grid, currentNode)
   if currentNode.adjNodes[0].isEnd {
       path = append(path, getSmallestNode(currentNode.adjNodes))
       *allPaths = append(*allPaths, path)
   } else {
       for _, node := range currentNode.adjNodes {
           findPath(grid, node, allPaths, path)
       }
   }
}

// This works fine
func makeGrid(scanner *bufio.Scanner) [][]gridNode {
   dims := convertToIntArr(strings.Fields(scanner.Text()))
   scanner.Scan()
   grid := make([][]gridNode, dims[0])
   heightIndex, widthIndex := 0, 0
   for i := 0; i < dims[0]; i++ {
       grid[i] = make([]gridNode, dims[1])
   }
   for ok := true; ok; ok = contains(grid, 0) {
       line := convertToIntArr(strings.Fields(scanner.Text()))
       for _, item := range line {
           var currentNode gridNode
           currentNode.weight = item
           currentNode.location = []int{heightIndex, widthIndex}
           if widthIndex < dims[1]-1 {
               currentNode.isEnd = false
           } else {
               currentNode.isEnd = true
           }
           grid[heightIndex][widthIndex] = currentNode
           widthIndex++
           if widthIndex == dims[1] {
               heightIndex++
               widthIndex = 0
           }
       }
       if heightIndex != dims[0] {
           scanner.Scan()
       }

   }
   return grid
}

func findMinWeight(paths [][]gridNode) []gridNode {
   var smallestWeight []gridNode
   for _, path := range paths {
       if getPathWeight(path) < getPathWeight(smallestWeight) || getPathWeight(smallestWeight) == 0 {
           smallestWeight = path
       }
   }
   return smallestWeight
}

func main() {
   // After opening/preparing the files..
   inputFile, err := os.Open("tsp.in")
   if err != nil {
       fmt.Println(err)
   }
   defer inputFile.Close()
   scanner := bufio.NewScanner(inputFile)

   outputFile, err := os.Create("tsp.out") // creating...
   if err != nil {
       fmt.Printf("error creating file: %v", err)
       return
   }
   defer outputFile.Close()

   // We interate through the file
   for scanner.Scan() {
       grid := makeGrid(scanner)
       var emptyPath []gridNode
       var allPaths [][]gridNode
       for _, row := range grid {
           findPath(grid, row[0], &allPaths, emptyPath)
       }
       minWeightPath := findMinWeight(allPaths)

       pathRowArr := getRows(minWeightPath)
       pathWeight := getPathWeight(minWeightPath)

       outputFile.WriteString(pathRowArr + "\n")
       outputFile.WriteString(strconv.Itoa(pathWeight) + "\n")
       outputFile.Sync()

   }
}

У меня такое чувство рекурсия отключена, хотя я не могу понять, как это сделать. Он также не работает на больших файлах. Помощь приветствуется! Спасибо!