利用LKH工具求解哈密顿环问题

在研究相邻节点和为立方数的问题时，以前使用的回溯加更换起点方法没能在期望时间内找到问题的解，从而想到使用专业求解器。

sage是一种能解决这种问题的工具，但对于专门的问题显得太大了。concorder是专业的TSP（旅行商问题）求解器，但在把哈密顿环问题（HCP）转化为TSP时，我遇到了困难。

LKH工具既能解决TSP，也能解决HCP，正合适。所以下面介绍它的使用方法。

LKH的官方网站是http://webhotel4.ruc.dk/~keld/research/LKH-3/ ，提供了源代码和可执行文件下载。

源代码 http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3.0.13.tgz

Windows可执行文件 http://webhotel4.ruc.dk/~keld/research/LKH-3/LKH-3.exe

在Linux上，按照如下步骤编译

tar xfz LKH-3.0.13.tgz
cd LKH-3.0.13
make

编译完成后，在LKH-3.0.13目录下生成LKH可执行文件。

运行LKH需要提供2种文件，一种是HCP文件，即哈密顿环问题的图描述文件。格式如下

NAME: graph_473
TYPE: HCP
DIMENSION: 473
EDGE_DATA_FORMAT: EDGE_LIST
EDGE_DATA_SECTION
1 7
1 26
...

362 367
363 366
364 365
EOF

其中name字段描述问题，TYPE: HCP指出这是一个哈密顿环问题。DIMENSION: 473表示有473个顶点。EDGE_DATA_FORMAT: EDGE_LIST表示格式是边的列表。 EDGE_DATA_SECTION标记边数据的开始，然后每行是一条边，用它的两个端点的编号表示。最后EOF表示文件结束。

手工生成包含大量节点和边的图不现实，所以我让deepseek帮我做了一个HCP文件生成python脚本，如下所示：

def generate_hcp_file(n=473, output_file="graph_473.hcp"):
    """
    生成 HCP 格式的图文件，节点 i 和 j 之间的边满足 i + j 是立方数（i < j）。
    
    参数:
        n (int): 节点总数（默认 473）
        output_file (str): 输出文件路径
    """
    # 预计算所有可能的立方数（i + j ≤ n + (n-1) = 473 + 472 = 945）
    max_sum = n + (n - 1)
    cube_numbers = {i**3 for i in range(1, int(max_sum ** (1/3)) + 2) if i**3 <= max_sum}

    # 生成满足 i + j 是立方数的边列表
    edges = []
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if (i + j) in cube_numbers:
                edges.append((i, j))

    # 写入 HCP 文件
    with open(output_file, "w") as f:
        f.write(f"NAME: graph_{n}\n")
        f.write("TYPE: HCP\n")
        f.write(f"DIMENSION: {n}\n")
        f.write("EDGE_DATA_FORMAT: EDGE_LIST\n")
        f.write("EDGE_DATA_SECTION\n")
        for u, v in edges:
            f.write(f"{u} {v}\n")
        f.write("EOF\n")

    print(f"文件已生成: {output_file}")
    print(f"边数量: {len(edges)}")

# 生成 473 节点的 HCP 文件
generate_hcp_file(n=473)

HCP文件还支持邻接表格式，只要写入EDGE_DATA_FORMAT: ADJ_LIST，然后在EDGE_DATA_SECTION下面以如下格式编写:

节点1 邻居1 邻居2 -1
节点2 邻居1 邻居2 -1
...
-1
EOF

注意-1结束符不可省略。下面是生成脚本

def generate_hcp_file(n=473, output_file="graph_4731.hcp"):
    """
    生成 HCP 格式的图文件，节点 i 和 j 之间的边满足 i + j 是立方数（i < j）。
    
    参数:
        n (int): 节点总数（默认 473）
        output_file (str): 输出文件路径
    """
    # 预计算所有可能的立方数（i + j ≤ n + (n-1) = 473 + 472 = 945）
    max_sum = n + (n - 1)
    cube_numbers = {i**3 for i in range(1, int(max_sum ** (1/3)) + 2) if i**3 <= max_sum}

    # 生成满足 i + j 是立方数的边列表
    edges = []
    for i in range(1, n + 1):
        edges.append([i])
        for j in range(i + 1, n + 1):
            if (i + j) in cube_numbers:
                edges[i-1].append(j)

    # 写入 HCP 文件
    with open(output_file, "w") as f:
        f.write(f"NAME: graph_{n}\n")
        f.write("TYPE: HCP\n")
        f.write(f"DIMENSION: {n}\n")
        f.write("EDGE_DATA_FORMAT: ADJ_LIST\n")
        f.write("EDGE_DATA_SECTION\n")
        for i in edges:
          if len(i)>1:
            for j in i:
               f.write(f"{j} ")
            f.write("-1\n")
        f.write("-1\nEOF\n")

    print(f"文件已生成: {output_file}")
    print(f"边数量: {len(edges)}")

# 生成 473 节点的 HCP 文件
generate_hcp_file(n=473)

运行LKH需要提供的第2种文件是参数文件，可以忽略，忽略时采用默认参数，这里我提供一个：

PROBLEM_FILE = graph_473.hcp
RUNS = 1
MAX_TRIALS = 10000

TOUR_FILE = output473.txt
SEED = 1234    # 随机种子

把它命名为graph_473.par，其中TOUR_FILE指定输出结果的文件，RUNS指定运行次数，MAX_TRIALS指定试验次数，如果太小可能求解失败。

将参数文件和HCP文件放在同一个目录下，然后在命令行输入./LKH graph_473.par,几秒钟即可求出相邻节点和为立方数的问题在473个节点时的解。

以下是output473.txt文件的片段,TOUR_SECTION后面每行输出一个节点，直到-1表示结束，然后是EOF。

NAME : graph_473.0.tour
COMMENT : Length = 0
COMMENT : Found by LKH-3 [Keld Helsgaun] Mon Mar 24 04:04:46 2025
TYPE : TOUR
DIMENSION : 473
TOUR_SECTION
231
281
448
64
61
451
...
112
-1
EOF