5
Trong bức tranh lớn, tôi đang cố triển khai thuật toán Dijkstra bằng hàng đợi ưu tiên.Go - Sử dụng vùng chứa/heap để triển khai hàng đợi ưu tiên
Theo các thành viên của golang-nut, cách thành ngữ để thực hiện việc này trong Go là sử dụng giao diện heap với cấu trúc dữ liệu cơ bản tùy chỉnh. Vì vậy, tôi đã tạo ra Node.go và PQueue.go như vậy:
//Node.go
package pqueue
type Node struct {
row int
col int
myVal int
sumVal int
}
func (n *Node) Init(r, c, mv, sv int) {
n.row = r
n.col = c
n.myVal = mv
n.sumVal = sv
}
func (n *Node) Equals(o *Node) bool {
return n.row == o.row && n.col == o.col
}
Và PQueue.go:
// PQueue.go
package pqueue
import "container/vector"
import "container/heap"
type PQueue struct {
data vector.Vector
size int
}
func (pq *PQueue) Init() {
heap.Init(pq)
}
func (pq *PQueue) IsEmpty() bool {
return pq.size == 0
}
func (pq *PQueue) Push(i interface{}) {
heap.Push(pq, i)
pq.size++
}
func (pq *PQueue) Pop() interface{} {
pq.size--
return heap.Pop(pq)
}
func (pq *PQueue) Len() int {
return pq.size
}
func (pq *PQueue) Less(i, j int) bool {
I := pq.data.At(i).(Node)
J := pq.data.At(j).(Node)
return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}
func (pq *PQueue) Swap(i, j int) {
temp := pq.data.At(i).(Node)
pq.data.Set(i, pq.data.At(j).(Node))
pq.data.Set(j, temp)
}
Và main.go: (hành động là trong SolveMatrix)
// Euler 81
package main
import "fmt"
import "io/ioutil"
import "strings"
import "strconv"
import "./pqueue"
const MATSIZE = 5
const MATNAME = "matrix_small.txt"
func main() {
var matrix [MATSIZE][MATSIZE]int
contents, err := ioutil.ReadFile(MATNAME)
if err != nil {
panic("FILE IO ERROR!")
}
inFileStr := string(contents)
byrows := strings.Split(inFileStr, "\n", -1)
for row := 0; row < MATSIZE; row++ {
byrows[row] = (byrows[row])[0 : len(byrows[row])-1]
bycols := strings.Split(byrows[row], ",", -1)
for col := 0; col < MATSIZE; col++ {
matrix[row][col], _ = strconv.Atoi(bycols[col])
}
}
PrintMatrix(matrix)
sum, len := SolveMatrix(matrix)
fmt.Printf("len: %d, sum: %d\n", len, sum)
}
func PrintMatrix(mat [MATSIZE][MATSIZE]int) {
for r := 0; r < MATSIZE; r++ {
for c := 0; c < MATSIZE; c++ {
fmt.Printf("%d ", mat[r][c])
}
fmt.Print("\n")
}
}
func SolveMatrix(mat [MATSIZE][MATSIZE]int) (int, int) {
var PQ pqueue.PQueue
var firstNode pqueue.Node
var endNode pqueue.Node
msm1 := MATSIZE - 1
firstNode.Init(0, 0, mat[0][0], 0)
endNode.Init(msm1, msm1, mat[msm1][msm1], 0)
if PQ.IsEmpty() { // make compiler stfu about unused variable
fmt.Print("empty")
}
PQ.Push(firstNode) // problem
return 0, 0
}
Vấn đề là, khi biên dịch tôi nhận được thông báo lỗi:
[~/Code/Euler/81] $ make
6g -o pqueue.6 Node.go PQueue.go
6g main.go
main.go:58: implicit assignment of unexported field 'row' of pqueue.Node in function argument
make: *** [all] Error 1
Và nhận xét ra dòng PQ.Push (firstNode) không thỏa mãn trình biên dịch. Nhưng tôi không hiểu tại sao tôi nhận được thông báo lỗi ngay từ đầu. Đẩy không sửa đổi đối số theo bất kỳ cách nào.
UPDATE: Vì lợi ích của những người đi qua này trong các tìm kiếm trong tương lai, các mã trên chứa rất nhiều các quan niệm sai lầm thô thiển. Hãy xem dưới đây để biết một mẫu nhiều hữu ích hơn để làm việc tắt của: Node.go:
// Node.go
package pqueue
import "fmt"
type Node struct {
row int
col int
myVal int
sumVal int
parent *Node
}
func NewNode(r, c, mv, sv int, n *Node) *Node {
return &Node{r, c, mv, sv, n}
}
func (n *Node) Eq(o *Node) bool {
return n.row == o.row && n.col == o.col
}
func (n *Node) String() string {
return fmt.Sprintf("{%d, %d, %d, %d}", n.row, n.col, n.myVal, n.sumVal)
}
func (n *Node) Row() int {
return n.row
}
func (n *Node) Col() int {
return n.col
}
func (n *Node) SetParent(p *Node) {
n.parent = p
}
func (n *Node) Parent() *Node {
return n.parent
}
func (n *Node) MyVal() int {
return n.myVal
}
func (n *Node) SumVal() int {
return n.sumVal
}
func (n *Node) SetSumVal(sv int) {
n.sumVal = sv
}
PQueue.go:
// PQueue.go
package pqueue
type PQueue []*Node
func (pq *PQueue) IsEmpty() bool {
return len(*pq) == 0
}
func (pq *PQueue) Push(i interface{}) {
a := *pq
n := len(a)
a = a[0 : n+1]
r := i.(*Node)
a[n] = r
*pq = a
}
func (pq *PQueue) Pop() interface{} {
a := *pq
*pq = a[0 : len(a)-1]
r := a[len(a)-1]
return r
}
func (pq *PQueue) Len() int {
return len(*pq)
}
// post: true iff is i less than j
func (pq *PQueue) Less(i, j int) bool {
I := (*pq)[i]
J := (*pq)[j]
return (I.sumVal + I.myVal) < (J.sumVal + J.myVal)
}
func (pq *PQueue) Swap(i, j int) {
(*pq)[i], (*pq)[j] = (*pq)[j], (*pq)[i]
}
func (pq *PQueue) String() string {
var build string = "{"
for _, v := range *pq {
build += v.String()
}
build += "}"
return build
}