Golang实现Held-Karp算法时遇到问题怎么解决
Golang实现Held-Karp算法时遇到问题怎么解决 你好！
我是Go语言的新手，之前一直在使用PHP。我遇到了一个与工作相关的问题，需要找到坐标之间的最短路径。我找到了一个PHP代码，但在计算超过9个节点时，耗时太长。
另一位朋友给了我一段Go代码，可以解决我的问题，但我不知道如何使用它。 我需要将.csv文件作为二维矩阵，并帮助我将参数传递到代码中，这样我就可以用PHP创建.csv文件并使用这个算法。
我也不太理解Visual Studio Code，它能编译Go代码吗？还是像PHP那样？因为当我按下F5（开始调试）时，这段代码没有任何结果。是因为代码运行不正常，还是我使用Visual Studio Code的方式不对？
package main
import (
"bytes"
"encoding/csv"
"fmt"
"io"
"log"
"math/bits"
"math/rand"
"os"
"runtime"
"strconv"
"strings"
"time"
)
const MaxInt = int(^uint(0) >> 1)
// IntSet
type IntSet struct {
Storage uint
}
func (vs IntSet) Contains(value int) bool {
return (vs.Storage & (1 << uint(value))) != 0
}
func (vs IntSet) Count() int {
return bits.OnesCount(vs.Storage)
}
func (vs *IntSet) Insert(value int) {
vs.Storage |= 1 << uint(value)
}
func (vs *IntSet) Remove(value int) {
vs.Storage &= ^(1 << uint(value))
}
func (vs IntSet) Value() int {
return int(vs.Storage >> 1)
}
func (vs IntSet) Iter() []int {
n := vs.Count()
v := make([]int, n)
for c, i := 0, 0; c < n; i++ {
if vs.Contains(i) {
v[c] = i
c++
}
}
return v
}
func (vs IntSet) String() string {
buf := bytes.Buffer{}
buf.WriteString("{")
delim := ""
for c, i := 0, 0; c < vs.Count(); i++ {
if vs.Contains(i) {
buf.WriteString(fmt.Sprintf("%s%v", delim, i))
delim = ","
c++
}
}
buf.WriteString("}")
return buf.String()
}
// Combinations 'k' integers from a serie '1..n'
type Combs []IntSet
func combWithLen(n, k, first int, vs IntSet, acc Combs) Combs {
if k > vs.Count() {
for x := first; x <= n; x++ {
s := vs
s.Insert(x)
acc = combWithLen(n, k, x+1, s, acc)
}
} else {
acc = append(acc, vs)
}
return acc
}
func Comb(n, k int) Combs {
return combWithLen(n, k, 1, IntSet{}, Combs{})
}
// Held Karp
type Path struct {
Cost int
From int
}
func minPath(paths []Path) Path {
m := paths[0]
for i := 1; i < len(paths); i++ {
if m.Cost > paths[i].Cost {
m = paths[i]
}
}
return m
}
func pathFromTo(from, to int, c [][]Path, dists CostMatrix, prev IntSet) Path {
p := Path{}
p.Cost = c[prev.Value()][from-1].Cost + dists[from][to]
p.From = from
return p
}
func reverse(a []int) []int {
for i, j := 0, len(a)-1; i < j; i, j = i+1, j-1 {
a[i], a[j] = a[j], a[i]
}
return a
}
// CostMatrix
type CostMatrix [][]int
func (dists CostMatrix) CalcCostToSubsets(c [][]Path, edges, subsetSz int) {
maxWorkers := runtime.NumCPU()
workers := 0
done := make(chan bool)
for _, visited := range Comb(edges, subsetSz) {
if workers == maxWorkers {
<-done
} else {
workers += 1
}
go func(vs IntSet) {
subset := vs.Iter()
// Find the lowest cost to get to this subset
for _, k := range subset {
prev := vs
prev.Remove(k)
res := []Path{}
for _, m := range subset {
if m != k {
res = append(res, pathFromTo(m, k, c, dists, prev))
}
}
if len(res) > 0 {
c[vs.Value()][k-1] = minPath(res)
}
}
done <- true
}(visited)
}
// Wait for all workers to finish
for ; workers > 0; workers -= 1 {
<-done
}
}
func (dists CostMatrix) ShortestPath() (int, []int) {
n := len(dists)
c := make([][]Path, 1<<uint(n-1))
for i := 0; i < len(c); i++ {
c[i] = make([]Path, n-1)
}
// Add paths from start to first steps
for k := 1; k < n; k++ {
c[1<<uint(k-1)][k-1] = Path{dists[0][k], 0}
}
for s := 2; s < n; s++ {
dists.CalcCostToSubsets(c, n-1, s)
}
visited := IntSet{}
for k := 1; k < n; k++ {
visited.Insert(k)
}
// Add path back to start and calculate optimal cost
res := []Path{}
for k := 1; k < n; k++ {
res = append(res, pathFromTo(k, 0, c, dists, visited))
}
p := minPath(res)
cost := p.Cost
// Backtrack to find path
steps := make([]int, n+1)
for i := 1; i < n; i++ {
steps[i] = p.From
from := p.From
p = c[visited.Value()][p.From-1]
visited.Remove(from)
}
return cost, reverse(steps)
}
func (c CostMatrix) MaxDigitWidth() (width int) {
for row := 0; row < len(c); row++ {
for col := 0; col < len(c[row]); col++ {
w := 0
for d := c[row][col]; d > 0; d /= 10 {
w += 1
}
if width < w {
width = w
}
}
}
return
}
func (c CostMatrix) String() string {
fmtstr := fmt.Sprintf("%%%vv", c.MaxDigitWidth())
buf := bytes.Buffer{}
for row := 0; row < len(c); row++ {
if row == 0 {
buf.WriteString("{\n")
}
buf.WriteString(" { ")
for col := 0; col < len(c[row]); col++ {
buf.WriteString(fmt.Sprintf(fmtstr, c[row][col]))
if col != len(c[row])-1 {
buf.WriteString(", ")
}
}
buf.WriteString(" },\n")
if row == len(c)-1 {
buf.WriteString("}")
} else {
}
}
return buf.String()
}
func Abs(n int) int {
if n < 0 {
return -n
}
return n
}
func Max(a, b int) int {
if a < b {
return b
}
return a
}
type Location struct {
shelf int
level int
}
func cost(from, to Location) int {
dx := Abs(from.shelf - to.shelf)
dy := Abs(from.level-to.level) * 2
return Max(dx, dy)
}
func zeroMatrix(dim int) CostMatrix {
var c CostMatrix = make([][]int, dim)
for i := range c {
c[i] = make([]int, dim)
}
return c
}
func genMatrix(nodes, depth, height int) CostMatrix {
rand.Seed(time.Now().UnixNano())
c := zeroMatrix(nodes)
l := make([]Location, nodes)
for i := range l {
l[i] = Location{rand.Intn(depth), rand.Intn(height)}
}
for row := 0; row < nodes; row++ {
for col := row + 1; col < nodes; col++ {
c[row][col] = cost(l[row], l[col])
c[col][row] = c[row][col]
}
}
return c
}
func readMatrix(r io.Reader) CostMatrix {
cr := csv.NewReader(r)
rec, err := cr.ReadAll()
if err != nil {
log.Fatalln(err)
}
M := zeroMatrix(len(rec))
for row, line := range rec {
for col, str := range line {
v, err := strconv.ParseInt(strings.TrimSpace(str), 10, 32)
if err != nil {
log.Fatalln(err)
}
M[row][col] = int(v)
}
}
return M
}
func GetCostMatrix() CostMatrix {
if len(os.Args) == 1 {
return readMatrix(os.Stdin)
}
arg := os.Args[1]
if strings.HasSuffix(arg, ".csv") {
file, err := os.Open(arg)
if err != nil {
log.Fatalln(err)
}
return readMatrix(file)
}
dim, err := strconv.ParseInt(arg, 10, 32)
if err != nil {
log.Fatalln(err)
}
return genMatrix(int(dim), 50, 9)
}
// Program entrypoint
func main() {
c := GetCostMatrix()
fmt.Println(c)
fmt.Println(c.ShortestPath())
}
更多关于Golang实现Held-Karp算法时遇到问题怎么解决的实战教程也可以访问 https://www.itying.com/category-94-b0.html
10 回复
你需要下载 Go 编译器（https://golang.org/dl/）
更多关于Golang实现Held-Karp算法时遇到问题怎么解决的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html
…
func main() {
c := GetCostMatrix(do you mean pass argument (2d matrix) here?)
fmt.Println(c)
fmt.Println(c.ShortestPath())
}
我已经在我的电脑上安装了Go。我成功运行了Hello World程序。 但是当我尝试运行上面的代码时，它既没有给我任何输出，也没有报错。在Visual Studio Code里什么都没有显示。
奇怪…… 我将这段代码复制到 Go PlayGround 并设置 args = “10”，它运行正常。 也许你在那个文件夹里有另一个 package main……
func main() {
fmt.Println("hello world")
}
打开一个终端窗口，输入 go run <go程序名称>.go。
您可以在 GetCostMatrix() 函数中，在 arg := os.Args[1] 这一行之后添加参数传递。
添加：
if len(arg) == 0 {
log.Fatalln("Not enought parameters")
}
这是一个典型的Held-Karp算法实现，用于解决旅行商问题。以下是具体的使用方法和问题解决方案：
1. CSV文件格式要求
CSV文件应该是一个对称的距离矩阵，例如：
0,10,15,20
10,0,35,25
15,35,0,30
20,25,30,0
2. 使用示例代码
创建一个main.go文件，添加以下代码来读取CSV文件：
package main
import (
"encoding/csv"
"fmt"
"os"
"strconv"
"strings"
)
func readCSVToMatrix(filename string) CostMatrix {
file, err := os.Open(filename)
if err != nil {
panic(err)
}
defer file.Close()
reader := csv.NewReader(file)
records, err := reader.ReadAll()
if err != nil {
panic(err)
}
n := len(records)
matrix := make(CostMatrix, n)
for i := range matrix {
matrix[i] = make([]int, n)
}
for i, row := range records {
for j, val := range row {
num, err := strconv.Atoi(strings.TrimSpace(val))
if err != nil {
panic(err)
}
matrix[i][j] = num
}
}
return matrix
}
func main() {
// 从CSV文件读取距离矩阵
matrix := readCSVToMatrix("distances.csv")
// 计算最短路径
cost, path := matrix.ShortestPath()
fmt.Printf("最短路径成本: %d\n", cost)
fmt.Printf("路径顺序: %v\n", path)
}
3. 在VS Code中运行Go代码
在VS Code中运行Go代码需要：
- 安装Go扩展：在扩展商店搜索"Go"并安装
- 配置运行：按
F5或使用终端命令
更简单的方式是使用终端：
# 编译并运行
go run main.go distances.csv
# 或者先编译再运行
go build -o tsp main.go
./tsp distances.csv
4. PHP生成CSV的示例
<?php
// 生成距离矩阵CSV
function generateDistanceCSV($filename, $matrix) {
$file = fopen($filename, 'w');
foreach ($matrix as $row) {
fputcsv($file, $row);
}
fclose($file);
}
// 示例距离矩阵
$distances = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
];
generateDistanceCSV('distances.csv', $distances);
echo "CSV文件已生成\n";
?>
5. 直接使用提供的代码
将原代码保存为tsp.go，然后：
# 运行并传入CSV文件
go run tsp.go distances.csv
# 或者从标准输入读取
cat distances.csv | go run tsp.go
6. 调试问题解决
如果F5没有输出，检查：
- 是否在
main函数中调用了算法 - 是否有输入数据
- 可以在代码开头添加调试输出：
func main() {
fmt.Println("程序开始执行...")
if len(os.Args) < 2 {
fmt.Println("请提供CSV文件名作为参数")
fmt.Println("用法: go run tsp.go distances.csv")
return
}
c := GetCostMatrix()
fmt.Println("距离矩阵:")
fmt.Println(c)
cost, path := c.ShortestPath()
fmt.Printf("\n最短路径成本: %d\n", cost)
fmt.Printf("路径顺序: %v\n", path)
}
这样修改后，运行go run tsp.go distances.csv就能看到完整的执行过程和结果。
