3-SATを解く乱択アルゴリズムがHello Algorithmで動いた
以前Pythonで実装したソースコードを数学ガールに登場する擬似コード風に書きなおしてみました。省略しているところを補えばこのコードは、Hello Algorithmで動かすことができます。
failed <- [] procedure RANDOM-WALK-3-SAT(f, f_size, n, R) #p353。ただしf_sizeは論理式fの長さ end-procedure procedure get_notsatisfied_clause() return failed[1] end-procedure procedure select_literal(clause) return clause[RANDOM(1, 3)] end-procedure procedure invert(literal, assignments) idx <- literal[1] if assignments[idx] = 1 then assignments[idx] <- 0 else assignments[idx] <- 1 end-if end-procedure procedure is_satisfied(cnf, f_size, assignments) i <- 1 while i <= f_size do clause_ <- cnf[i] if 0 = clause_is_satisfied(clause_, assignments) then failed[1] <- clause_ return 0 end-if i <- i + 1 end-while return 1 end-procedure procedure clause_is_satisfied(clause, assignments) i <- 1 while i <= 3 do literal <- clause[i] if assignments[literal[1]] = literal[2] then return 1 end-if i <- i + 1 end-while return 0 end-procedure procedure random_assignments(n) assignments <- [] i <- 1 while i <= n do assignments[i] <- RANDOM(0, 1) i <- i + 1 end-while return assignments end-procedure