著者

松中 春樹 丹生 智也 番原 睦則 田村 直之

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

vol.27, no.2, pp.10-15, 2012 (Released:2012-01-13)

参考文献数

15

---

Propositional Satisfiability (SAT) is fundamental in solving many application problems in Artificial Intelligence and Computer Science. Remarkable improvements in the efficiency of SAT solvers have beenmade over the last decade. Such improvements encourage researchers to solve constraint satisfaction problems by encoding them into SAT (i.e. ``SAT encoding''). Balanced Incomplete Block Design (BIBD) is one of the most typical block designs. BIBDs have been applied in several fields such as design experiments, coding theory, and cryptography. In this paper, we consider the problem of generating BIBDs by SAT encoding. We present a new SAT encoding that is an enhancement of order encoding with the idea of binary tree. It is designed to reduce the number of clauses required for cardinality constraints, compared with order encoding. In our experiments, our encoding was able to give a greater number of solutions than order encoding and state-of-the-art constraint solvers Mistral and choco.

著者

有住なな 丹生智也 南和宏 丸山宏

雑誌

マルチメディア、分散協調とモバイルシンポジウム2014論文集

巻号頁・発行日

vol.2014, pp.823-827, 2014-07-02

---

近年,インターネット上では様々な位置情報サービスが提供されており,多数のユーザーの間で位置情報の共有が実現されている.しかし位置情報はユーザーのプライバシーに関する行動に深く関連するため,位置情報の公開は適切に制限される必要がある.そこで我々はこれまでユーザーの識別子を仮名に置き換える仮名化方式を検討し,「ミックスゾーン」と呼ばれる複数ユーザーが出会う場所でランダムに仮名を交換する方式を考案し,各ユーザーが取り得る代替経路の不確定性に基づきプライバシーの概念を定式化した.本論文では、このミックスゾーンを用いたプライバシー保護技術において効率的に安全性を検証するアルゴリズムについて考察する.

著者

田村 直之 丹生 智也 番原 睦則

出版者

日本ソフトウェア科学会

雑誌

コンピュータ ソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.27, no.4, pp.4_183-4_196, 2010-10-26 (Released:2010-12-26)

---

本論文では,SAT変換に基づく制約ソルバーであるSugarの概要とその性能評価結果について述べる.Sugarは,制約充足問題(CSP),制約最適化問題(COP)および最大制約充足問題(Max-CSP)を,命題論理の充足可能性判定問題(SAT問題) に変換し,MiniSat等の高速なSATソルバーを用いて求解を行うシステムである.SAT変換には,order encodingと名付けた新しい方法を用いており,従来広く用いられているdirect encodingやsupport encodingよりも,多くの問題に対して高速な求解が可能である.本論文では,order encodingの説明を含めたSugarの概要について述べた後,2008年に開催された第3回国際CSPソルバー競技会およびMax-CSPソルバー競技会での結果を基にSugarの性能評価結果を報告する.なお,Sugarは同競技会の10部門のうち4部門で第1位となった.