我看过其他一些与此游戏有关的帖子,但没有一个是围绕我选择的算法类型展开的,至少在很多细节上都没有。这也是我冒充了解更多关于图的信息(例如使用igraph包)。不用说,在任何情况下我都不鼓励人们作弊。这确实是我为自己设定的学习挑战-通常是我最后学到的东西最多。

除了明显的French dictionary集合,我的计划还涉及一些准备工作。

第一步是构建一个看起来像这样的图形,以说明Boggle字母之间允许的连接。 (对于不熟悉Boggle的用户,您只能从直接相邻的字母(包括对角线)创建单词,并且单词越长,奖励就越大)。



下一步(这可能不理想,但无法从igraph软件包中直接找出实现方法)。无论如何,它是使用gtools生成所有排列的:

permutations(n=16, r=3)
permutations(n=16, r=4)

然后使用igraph::neigbourhood函数“验证”每个单个排列,以查看它们在Boggle游戏中是否合法。我们从下面的数字中可以看到,“样本”越大(如果您喜欢,单词越长),则拒绝的排列就越多。因此,获取很少的附加信息具有很大的处理能力。显然不是最佳的。当r超过7时,所有地狱都松散了(我的8 Gb Ram还不够!)

4 letter permutations - total : 43680
                        legit : 1764 (4.0%)
6 letter permutations - total : 5765760
                        legit : 22672 (0.4%)
and so forth


因此,现在我想找到一种以更明智的方式生成这些排列的方法(也许可以将它们称为“路径”或“轨迹”),也许可以使用诸如ig​​raph之类的工具,这样我就不会炒主板太有趣了。使用图对我来说是新手,所以它可能直立在我的脸上,但是我看不到诸如“生成通过图上N个相邻节点的所有轨迹”之类的东西,或文档中类似的东西。也许它存在,但是它被称为“某些人的算法”,不幸的是我从未听说过。

完成所有准备工作后,我对结果感到非常满意。它相当快且完全准确。我只是停留在7个字母的单词上(5个悲惨点)。如果对ppl感兴趣,我可能会在某个时候将其放在GitHub上。我认为对图形足够了解的人应该能够为我指明正确的方向,这就是为什么我不认为将任何长度的编码用于这里都没有用。

提前致谢!

(为完整起见,一旦计算出“有效排列”,我就对字典条目运行结果单词,并把匹配的单词放在一边。我正在使用RSQLite并处理长度越来越大的单词块;将各部分分开这样,代码就很容易遵循,并且数据库搜索也很快。)

最佳答案

这是一个递归解决方案,可以找到所有长度不超过L的路径。

使用此Gist创建的图形:

getPaths <- function(v, g, L = 4) {
  paths <- list()
  recurse <- function(g, v, path = NULL) {
    path <- c(v, path)

    if (length(path) >= L) {
      return(NULL)
    } else {
      for (i in neighbors(g, v)) {
        if (!(i %in% path)) {
          paths[[length(paths) + 1]] <<- c(i, path)
          recurse(g, i, path)
        }
      }
    }
  }
  recurse(g, v)
  return(paths)
}

allPaths <- lapply(V(g), getPaths, g)

# look at the first few paths from vertex 1:
> head(allPaths[[1]])
[[1]]
[1] 2 1

[[2]]
[1] 3 2 1

[[3]]
[1] 4 3 2 1

[[4]]
[1] 6 3 2 1

[[5]]
[1] 7 3 2 1

[[6]]
[1] 8 3 2 1


编辑

这是一个仅保留L长度路径的更有效的解决方案。

getPaths <- function(v, g, L = 4) {
  paths <- list()

  recurse <- function(g, v, path = NULL) {
    path <- c(v, path)

    if (length(path) >= L) {
      paths[[length(paths) + 1]] <<- rev(path)
    } else {
      for (i in neighbors(g, v)) {
        if (!(i %in% path)) recurse(g, i, path)
      }
    }
  }
  recurse(g, v)
  return(paths)
}

allPaths <- lapply(V(g), getPaths, g, 4)

L4way <- do.call(rbind, lapply(allPaths, function(x) do.call(rbind, x)))

> head(L4way)
     [,1] [,2] [,3] [,4]
[1,]    1    2    3    4
[2,]    1    2    3    6
[3,]    1    2    3    7
[4,]    1    2    3    8
[5,]    1    2    5    6
[6,]    1    2    5    9


编辑#2:

library(doSNOW)
library(foreach)

# this is a very parallel problem and can be parallel-ized easily
cl <- makeCluster(4)
registerDoSNOW(cl)

allPaths <- foreach(i = 3:16) %:%
  foreach(v = V(g), .packages = c('igraph')) %dopar% getPaths(v, g, i)

stopCluster(cl)

path.list <- list()
for (i in seq_along(3:16)) {
  path.list[[i]] <- do.call(rbind, lapply(allPaths[[i]],
      function(x) do.call(rbind, x)))
}


L长度字的排列数:

> data.frame(length=3:16, nPerms=sapply(path.list, nrow))
   length  nPerms
1       3     408
2       4    1764
3       5    6712
4       6   22672
5       7   68272
6       8  183472
7       9  436984
8      10  905776
9      11 1594648
10     12 2310264
11     13 2644520
12     14 2250192
13     15 1260672
14     16  343184


总排列

> sum(sapply(path.list, nrow))
[1] 12029540

关于r - Boggle作弊…erm…用R中的图求解,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28609703/

10-10 15:58