読者です 読者をやめる 読者になる 読者になる

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