rw3sat.r

rw3sat.r

random_walk_3_sat <- function (f, n, rr) {
  # f の各要素に x を適用した結果を Vector で返すクロージャ
  ff <- (function (f) {
    return(function (x) sapply(f, eval, list(x=x)))
  })(f)
  for (r in seq(rr)) {
    # W4
    x <- sample(c(FALSE,TRUE), n, replace=TRUE)
    for (k in seq(3*n)) {
      # W7,8,9
      if (all(ff(x))) {
        return("充足可能である")
      }
      # W10: f の中から ff の結果が FALSE のものを1つ取り出し、文字列化
      cd <- deparse(sample(f[!ff(x)], 1))
      # W11-1: cd の中から数字（＝Vectorのindex）を全て抽出
      m <- gregexpr("[0-9]+", cd)[[1]]
      # W11-2: 取り出した数字を1つ選んで数値化
      idx <- as.integer(sample(substring(cd, m, m + attr(m, 'match.length') - 1), 1))
      # W12
      x[idx] <- !x[idx]
    }
  }
  "おそらく充足不可能である"
}

# 各論理式は文字列で準備
p1 <- " x[1] ||  x[2] ||  x[3]"
p2 <- " x[4] ||  x[2] || !x[3]"
p3 <- "!x[1] ||  x[4] ||  x[3]"
p4 <- "!x[1] || !x[4] ||  x[2]"
p5 <- "!x[4] || !x[2] ||  x[3]"
p6 <- "!x[1] || !x[2] || !x[3]"
p7 <- " x[1] || !x[4] || !x[3]"
p8 <- " x[1] ||  x[4] || !x[2]"
# parse() 関数で expression オブジェクトに変換
f <- parse(text = c(p1, p2, p3, p4, p5, p6, p7, p8))
# random_walk_3_sat() 呼び出し
print(random_walk_3_sat(f, 4, 3))