3D立方晶格下递归生成多条无重叠自规避聚合物链的方案咨询

先修复原有代码的已知问题 #

原有代码存在几个逻辑bug，会导致功能异常，需要先修正：

• 变量名不匹配：函数形参为大写DoP，但代码中写的是小写dop--，会导致递归终止条件完全失效
• 赋值运算符误用：标记格点占用的语句写为this->occupied[next] == 1，双等号是判断逻辑，实际不会修改格点占用状态，会出现重复占用问题
• 无回溯逻辑：当前遇到路径阻塞时直接返回失败，没有回退已选格点尝试其他方向，长链生成成功率极低
• 无随机逻辑：固定方向遍历顺序会导致所有生成的链结构完全一致，不符合自规避随机游走的特性

批量无起点指定植入的实现思路 #

不需要递归查找可用起始位置，直接遍历全局空格点即可，实现逻辑如下：

1. 新增批量植入入口函数，每次植入新链前，先从全局未被占用的格点中随机选择一个作为起始点
2. 重构单条链生成逻辑，增加回溯机制：如果当前路径走不通，回退已占用的格点、尝试其他方向，整条链生成失败则释放所有已占格点，更换起始点重试
3. 全局共享occupied占用标记，新增链生成时自动规避所有已被其他聚合物占用的格点

参考实现代码 #

#include <random>
#include <algorithm>

// 全局随机数生成器，可根据需要调整
std::random_device rd;
std::mt19937 g(rd());
const std::vector<int> ex{1,0,0}, nex{-1,0,0}, ey{0,1,0}, ney{0,-1,0}, ez{0,0,1}, nez{0,0,-1};
const std::vector<std::vector<int>> drns = {ex, nex, ey, ney, ez, nez};

// 私有辅助函数：带回溯的单条链生成
bool Grid::plant_single_polymer(int remain_DoP, std::vector<std::vector<int>>* loc_list) {
    if (remain_DoP == 0) {
        Polymer p(loc_list);
        this->polymer_chains.push_back(p);
        return true;
    }
    // 打乱方向顺序，保证链的随机性
    auto shuffled_drns = drns;
    std::shuffle(shuffled_drns.begin(), shuffled_drns.end(), g);
    
    std::vector<int> next(3,0);
    for (auto& v : shuffled_drns) {
        next = add_vectors(&((*loc_list).back()), &v);
        impose_pbc(&next, this->x_len, this->y_len, this->z_len);
        
        if (this->occupied[next] == 0) {
            // 标记占用
            this->occupied[next] = 1;
            loc_list->push_back(next);
            // 递归生成下一个节点
            if (plant_single_polymer(remain_DoP - 1, loc_list)) {
                return true;
            }
            // 生成失败，回溯
            loc_list->pop_back();
            this->occupied[next] = 0;
        }
    }
    // 所有方向都走不通，返回失败
    return false;
}

// 公有批量植入函数，参数为要植入的链数、每条链的聚合度，返回是否全部植入成功
bool Grid::batch_plant(int chain_count, int DoP) {
    // 先检查总容量是否足够
    int total_needed = chain_count * DoP;
    int total_available = x_len * y_len * z_len - polymer_chains.size() * DoP; // 可根据实际已占用数精确计算
    if (total_available < total_needed) {
        std::cout << "晶格剩余空间不足，无法植入指定数量的聚合物链" << std::endl;
        return false;
    }

    for (int i = 0; i < chain_count; i++) {
        bool success = false;
        // 遍历所有格点找可用起点，加重试上限避免无限循环
        int retry = 0;
        const int max_retry = 1000;
        while (retry < max_retry) {
            // 随机生成起点
            std::vector<int> start(3);
            start[0] = std::uniform_int_distribution<int>(0, x_len-1)(g);
            start[1] = std::uniform_int_distribution<int>(0, y_len-1)(g);
            start[2] = std::uniform_int_distribution<int>(0, z_len-1)(g);
            
            if (occupied[start] == 0) {
                // 初始化位置列表
                std::vector<std::vector<int>> loc_list;
                loc_list.push_back(start);
                occupied[start] = 1;
                // 尝试生成链
                if (plant_single_polymer(DoP - 1, &loc_list)) {
                    success = true;
                    break;
                }
                // 生成失败，释放起点
                occupied[start] = 0;
            }
            retry++;
        }
        if (!success) {
            std::cout << "第" << i+1 << "条聚合物链植入失败，已重试" << max_retry << "次" << std::endl;
            return false;
        }
    }
    return true;
}

注意事项 #

• 可以根据实际需求调整重试次数上限，聚合度越大需要的重试次数越多
• 如果需要生成大量高聚合度的链，可以改用蛇形填充等确定性算法提升成功率
• 可以优化空格点的获取逻辑，不用每次随机试错，直接维护一个空格点列表随机选取，提升运行效率

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