利用sage软件快速计算哈密顿回路解决相邻数组成平方数问题 - l1t1/note GitHub Wiki

sage是数学工具软件包，包含计算各种数学问题的高效工具，它的安装相对复杂，因此选择用docker镜像方式安装，最新镜像不含arm64版本，因此在Windows的WSL中运行。

一、抓取sage镜像并登录在后台运行的容器

docker pull docker.1ms.run/sagemath/sagemath:latest

docker run -it -d -v/mnt/c/d:/par --name sage docker.1ms.run/sagemath/sagemath:latest

docker exec -it sage bash

二、在命令行输入sage进入交互界面

sage@bf8a8e869acb:~$ sage
┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 10.5, Release Date: 2024-12-04                    │
│ Using Python 3.12.5. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘

针对如下问题：请把数字从1到33放到圆周上，没有重复，每个相邻对之和都是一个平方数，请从1开始输出这个序列，用过Deepseek和Le Chat写的回溯法程序，总是不够高效， Moritz Firsching发表在数学溢出论坛上的回帖，利用sage程序可以高效解决。 但我复制代码后执行出错ValueError: cannot add edge from 4 to 4 in graph without loops。经过分析，我把程序增加一处，判断顶点不同and i!=p-i，就不报错了。

def getgraph(n,N,path):
    powers=[(i+1)^N for i in range(ceil((2*n)^(1/N)))]
    G=Graph()
    G.add_vertices([1,..,n])
    edges=[]
    for p in powers:
        for i in range(1,ceil(p/2)+1):
            if i<=n and p-i<=n and p-i>0 and i!=p-i: #增加
                edges.append([i,p-i])

    if path:   #add an extra vertex connected to all others
        G.add_vertex(0)  #to get path from cycle
        for i in [1,..,n]:
            edges.append([0,i])
    G.add_edges(edges)
    return G

path=False #得出哈密顿回路
n=473
N=3
G=getgraph(n,N,path)
time hami=G.hamiltonian_cycle()
print ([l[(i+l.index(int(not(path))))%len(l)] for i in range(int(path),len(l))])

path=True #得出哈密顿路径
n=25
N=2
G=getgraph(n,N,path)
time hami=G.hamiltonian_cycle()
print ([l[(i+l.index(int(not(path))))%len(l)] for i in range(int(path),len(l))])

并把原计算473个相邻数之和组成立方数改为计算1~100的每对相邻数组成平方数N=2，执行后得到如下结果:

sage: path=False
sage: n=100
sage: N=2
sage: time G=getgraph(n,N,path)
CPU times: user 1.93 ms, sys: 0 ns, total: 1.93 ms
Wall time: 1.88 ms
sage: time hami=G.hamiltonian_cycle()
CPU times: user 17.8 ms, sys: 9.74 ms, total: 27.6 ms
Wall time: 26.3 ms
sage: l=hami.cycle_basis()[0]
sage: print ([l[(i+l.index(int(not(path))))%len(l)] for i in range(len(l))])
[1, 99, 70, 30, 91, 53, 47, 17, 8, 92, 29, 20, 16, 84, 60, 40, 41, 59, 22, 42, 79, 65, 35, 46, 75, 25, 56, 88, 33, 3, 61, 83, 38, 62, 19, 81, 63, 37, 27, 94, 50, 31, 90, 54, 67, 77, 44, 5, 11, 14, 86, 58, 6, 10, 39, 82, 18, 7, 9, 72, 97, 24, 76, 68, 32, 4, 96, 100, 69, 12, 52, 48, 73, 71, 98, 2, 34, 66, 78, 43, 21, 28, 93, 51, 49, 95, 74, 26, 23, 13, 87, 57, 64, 80, 89, 55, 45, 36, 85, 15]

经测试，以上程序计算300以内的哈密顿回路都很快。

⚠️ **GitHub.com Fallback** ⚠️