如何扩展这个关于病毒传播的想法？

Question

首先，我定义了类型：

type people_group = {
  people : char list; 
  distances : (char * float * char) list
};;

所以这个项目是关于病毒传播的。例如：

let group1 : people_group = {
  people=['1'; '2'; '3'; '4'; '5'];
  distances=[
    ('1', 0.3, '2'); ('2', 0.7, '1');
    ('1', 10.1, '3'); ('3', 3., '4');
    ('3', 0.1, '5'); ('4', 7., '5'); 
    ('2', 6., '3')
  ]
};;

在上面的例子中，我们有一个五人小组（用数字表示）。距离中的元素

('1', 0.3, '2')

表示第一个人和第二个人之间的距离（在本例中为 0.3）。如果距离（浮动）> 0.5，则第二个人被感染。

所以我做了一个函数

quick_infection

：

let quick_infection (group : people_group) c =
  let first = function
    | (a, _, _) -> a
  in
  let scnd = function
    | (_, a, _) -> a
  in
  let third = function
    | (_, _, a) -> a
  in
  [c] @ 
  List.map 
    (fun x -> third x) 
    (List.filter 
       (fun x -> first x = c && scnd x > 0.5) 
       group.distances);;

它有两个参数（一群人和一个被感染的人），作为输出，给出了被某个人+开始传播的人感染的人的字符列表，但在一步之后。例子：

# quick_infection group1 '1';;
- : char list = ['1'; '3']
# quick_infection group1 '2';;
- : char list = ['2'; '1'; '3']
# quick_infection group1 ’5’;;
- : char list = ['5']

现在我想扩展这个想法并创建一个函数

chain_infection

，它作为输出给出间接感染者的字符列表。这个例子应该最好地展示它是如何工作的：

# chain_infection group1 '1';;
- : char list = ['1'; '3'; '4'; '5']

我觉得我之前的功能可以帮助很大，但我不知道如何使用它。那么有什么建议吗？

Answer 1

当您需要对迭代过程进行建模时，您应该使用递归。解决您的问题的总体方法是从零患者

c0

开始，并获取零患者

[c01,.., c0N] = quick_infection group1 '1'

的第一个圈子的人员列表。现在你遍历每个

c01

，直到

c0N

调用

quick_infection

为止。您将获得一个列表列表，您可以使用

List.flatten

将其展平。现在您已经有了一组感染者，您也应该使用

quick_infection

进行映射，然后将其展平。这个过程看起来是无限的，事实上也是如此，除非我们在感染模型中添加更多规则。例如，我们可以添加同一个人不能被感染两次的规则，这样当我们看到一个人已经被感染时，我们不会将其添加到感染列表中。现在我们可以指定感染的终止标准 - 当感染者名单停止增长时，感染就会停止。

就 OCaml 而言，使用递归的一般迭代过程如下所示（其中

<code-in-brackets>

对应于您应填写的用户代码），

let rec loop input output = 
 if <check-condition> input output 
 then loop (<do-the-work> input output) 
 else output

这大致对应于命令式循环（在某些 C 风格伪语言中），

while (<check-condition>(input, output)) {
  <do-the-work>(input, output);  
}

有时没有输出，或者输入在循环过程中没有变化，或者你需要在循环中添加一个归纳变量，例如，

let strnlen chars maxlen = 
  let rec loop i = 
   if chars.[i] <> '\x00' && i < maxlen 
   then loop (i+1)
   else i in
  loop 0

此示例函数模仿 strnlen 函数，该函数返回

'0'

符号或

maxlen

之前的字符数（以较小者为准）。此示例还演示了将循环隐藏为嵌套在主函数中的辅助函数的常见方法。将其与相同函数的 C 实现进行比较，

int strlen(const char *chars, int maxlen) {
  int i = 0;
  while (i < maxlen && chars[i] != '\x00') {
     i++;
  }
  return i;
}

还值得知道的是，您的问题很容易用图建模，事实上，您的组就是一个图。病毒的传播是图可达性问题的一个实例，您正在寻找关系distance p1 p2 < 0.5

1)

的^传递闭包的传递闭包。

---

您的帖子和代码说的是

> 0.5

，但我认为这是一个错字，除非您正在建模一种反社会距离感染，该感染仅在较远的目标上传播，并且不会在不保持社交距离的人之间进行过渡:)