递归地执行多个自我回避遍历

Executing multiple self-avoiding walks, recursively(递归地执行多个自我回避遍历)

问题描述

我有一个3D简单立方晶格，在我的代码中我称之为Grid，具有大小为20x20x20(数字是任意的)的周期性边界条件。我想做的是种植聚合度为N的多个聚合链(具有N个节点的图)，它们不会重叠，是自我避免的。

目前，我可以递归地种植一个聚合物。这是我的代码

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};     // unit directions 
const std::vector <std::vector <int>> drns = {ex, nex, ey, ney, ez, nez};                           // vector of unit directions 

void Grid::plant_polymer(int DoP, std::vector <std::vector <int>>* loc_list){
    // loc_list is the list of places the polymer has been 
    // for this function, I provide a starting point 
    if (DoP == 0){
        Polymer p (loc_list); 
        this->polymer_chains.push_back(p); // polymer_chains is the attribute which holds all polymer chains in the grid 
        return; // once the degree of polymerization hits zero, you are done
    }; 

    // until then 
    // increment final vector in loc_list in a unit direction 
    std::vector <int> next(3,0); 
    for (auto v: drns){

        next = add_vectors(&((*loc_list).at((*loc_list).size()-1)), &v);
        
        impose_pbc(&next, this->x_len, this->y_len, this->z_len); 
        
        
        if (this->occupied[next]==0){ // occupied is a map which takes in a location, and spits out if it is occupied (1) or not (0)
// occupied is an attribute of the class Grid
            dop--; // decrease dop now that a monomer unit has been added 
            (*loc_list).push_back(next); // add monomer to list 
            this->occupied[next] == 1; 
            return plant_polymer(DoP, loc_list); 
        } 
    }


    std::cout << "no solution found for the self-avoiding random walk...";
    return; 

这不是一般的解决方案。我正在为聚合物提供种子，而且，我只种植一种聚合物。我想让它变得可以种植多种聚合物，而不指定种子。每次我想要添加聚合物时，是否可以递归地寻找起始位置，然后构建聚合物，同时确保它不与系统中已有的其他聚合物重叠？如果您有任何建议，我们将不胜感激。

推荐答案

至少从20世纪60年代起，人们就开始研究自我回避走路了，而且有大量关于这方面的文献。幸运的是，你面临的问题属于最简单的问题(行走的长度固定在一个相对较小的值)。

1

您应该意识到的第一件事是，您的问题范围太广，无法得到唯一的答案。也就是说，如果你在系统中种植许多聚合物，你将得到的结果取决于聚合物种植和生长的动态。有两个主要案例。你要么种下一些种子并开始种植聚合物，要么在其他地方种植每一种聚合物，然后试着把它们一个接一个地种在系统中的一个随机位置，保持自我回避的状态。这两种方法将产生统计上不同的聚合物分布，您对此无能为力，只能更详细地指定系统动力学。

我认为第二种方法更简单一些，因为它使您不必决定在某些聚合物无法生长到所需长度时如何操作(重新启动模拟？)，因此我们只关注它。

一般算法可能如下所示：

• 将maximum_number_of_attempts设置为合理的大小，但不要太大，例如一百万
• 将required_number_of_polymers设置为所需的值
• 将number_of_attempts设置为0
• 将number_of_planted_polymers设置为0
• Whilenumber_of_attempts<；maximum_number_of_attempts和number_of_planted_polymers<；required_number_of_polymers
  • 增加number_of_attempts1
  • 生成下一个随机聚合物
  • 在系统中选择随机位置(点阵站点)
  • 检查聚合物是否可以在没有交叉点的情况下种植在此位置
  • 如果且仅当是，
    • 接受聚合物(将其添加到聚合物列表；更新占用的晶格节点列表)
    • 增加number_of_planted_polymers1

要加快速度，您可以仅从未占用的站点选择初始位置(例如，在while循环中)。另一个想法是，在第一次电镀失败时，尝试并在不同的位置使用聚合物(但不要太多，你需要试验)。

2

现在下一步：如何生成自我避免的随机游动。除了一些误解之外，您的代码几乎没有问题。

在函数void Grid::plant_polymer中有一个严重的错误：它总是以完全相同的顺序在可能的聚合物形状空间中执行搜索。换句话说，它是决定论的。对于蒙特卡罗方法来说，这听起来像是一场灾难。你可以做的一件事就是随机地调整方向。

  auto directions = drns;
  std::shuffle(begin(directions), end(directions), random_generator); // c++17
  for (const auto & v: directions)
  {
    ...

要实现这一点，您需要一个已经定义和初始化的随机数生成器，例如

    std::random_device rd;
    std::mt19937 random_generator(rd());

程序中更早且只有一次的某个位置。

如果您不使用C++17，请使用std::random_shuffle而不是std::shuffle，但要注意前者已经折旧，请参阅https://en.cppreference.com/w/cpp/algorithm/random_shuffle以了解原因。

---

顺便提一句，当提出与软件相关的特定问题时，请尝试并提供Minimal, reproducible example。仅根据阅读代码回答问题几乎总是更耗时，而且答案往往更加粗略和不准确。

这篇关于递归地执行多个自我回避遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！