Python实现二维自回避随机行走问题求助（附错误代码）

问题描述 #

我想用Python实现方格网格上的二维自回避随机行走：点仅能上下左右移动，且不能重复经过同一位置。我有思路但代码无法正常运行，预期效果为网格上无交叉的折线轨迹。

我的思路：

• 创建列表存储已走过的坐标
• 生成当前位置的相邻点列表
• 通过求差集得到未走过的相邻点（surviving_neighbors）
• 但目前x和y坐标分开存储，无法直接计算差集；选择新坐标后也没法转化为x、y形式的轨迹。老师建议把x和y存储为向量，但我不知道怎么操作。

错误代码 #

from random import choice
import numpy as np
from matplotlib import pyplot as plt
plt.style.use(['science', 'notebook', 'dark background'])

x, y = 0, 0

coordinates = [(x, y)]
for time in range(10):
    dx, dy = choice([(0, 1), (-1, 0), (0, 1), (0, -1)])
    x, y = x + dx, y + dy
    X.append(x)
    Y.append(y)

    neighbors = [x+1, y
                 x-1
                 y
                 x, y+1
                 x, y-1]

    surviving_neighbors = neighbors.difference(X, Y)
    trajectory = choice(surviving_neighbors)

    plt.plot()

修正实现方案 #

核心是把坐标用元组存储（即老师所说的“向量”形式），这样可直接判断位置是否已走过，操作更简洁。

完整可运行代码 #

from random import choice
from matplotlib import pyplot as plt
plt.style.use(['science', 'notebook', 'dark background'])

# 初始化：起点坐标、已访问位置列表
current_pos = (0, 0)
visited = [current_pos]
walk_length = 50  # 设置行走的总步数

for _ in range(walk_length):
    # 生成当前位置的四个相邻点（上下左右）
    neighbors = [
        (current_pos[0] + 1, current_pos[1]),  # 右
        (current_pos[0] - 1, current_pos[1]),  # 左
        (current_pos[0], current_pos[1] + 1),  # 上
        (current_pos[0], current_pos[1] - 1)   # 下
    ]
    # 筛选出未访问过的相邻点
    surviving_neighbors = [pos for pos in neighbors if pos not in visited]
    
    # 若无可走方向，提前终止行走
    if not surviving_neighbors:
        print("走到死胡同，提前结束行走")
        break
    
    # 随机选择下一个位置并加入已访问列表
    current_pos = choice(surviving_neighbors)
    visited.append(current_pos)

# 提取x、y坐标用于绘图
x_coords = [pos[0] for pos in visited]
y_coords = [pos[1] for pos in visited]

# 绘制轨迹
plt.figure(figsize=(8, 8))
plt.plot(x_coords, y_coords, marker='o', markersize=4, linewidth=1.5)
plt.scatter(0, 0, color='green', s=100, label='起点')
plt.scatter(x_coords[-1], y_coords[-1], color='red', s=100, label='终点')
plt.xlabel('X坐标')
plt.ylabel('Y坐标')
plt.title('二维自回避随机行走轨迹')
plt.legend()
plt.grid(True)
plt.axis('equal')  # 保证坐标轴比例一致，避免轨迹扭曲
plt.show()

关键修正说明 #

• 坐标存储优化：用(x,y)元组存储每个位置，直接存入visited列表，判断是否走过只需pos not in visited，避免原代码分开存储x、y的麻烦。
• 相邻点生成修正：正确生成四个方向的相邻点元组，解决原代码中列表语法错误（换行、逗号缺失）。
• 差集筛选实现：用列表推导式筛选未访问点，替代原代码错误的difference调用（difference是集合方法，原代码的neighbors是列表，无法直接使用）。
• 绘图逻辑完善：统一从visited列表提取x、y坐标后绘图，解决原代码无有效绘图参数的问题。
• 增加终止条件：检测到死胡同时提前终止，避免程序报错。

内容的提问来源于stack exchange，提问作者Teodora