部分MAXSATを利用した大学情報処理の自動化1

• Item type: SIG Technical Reports(1)
• 公開日: 1998-07-08
• タイトル: 部分MAXSATを利用した大学情報処理の自動化1
• タイトル / 言語: en
• タイトル: Partial MAXSAT for Combinatorial Optimization on University Databases
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 京都大学大学院情報学研究科
• 著者所属: 京都大学大学院情報学研究科
• 著者所属(英): en
• 著者所属(英): School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): School of Informatics, Kyoto University
• 著者所属(英): en
• 著者所属(英): School of Informatics, Kyoto University
• 著者名: 盛田, 保文; 宮崎, 修一; 岩間, 一雄
• 著者名(英): Yasufumi, Morita; Shuichi, Miyazaki; Kazuo, Iwama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 複雑ではあるがそれほど大規模でないデータベース上の情報処理の高速化を目標とする．本研究では，組み合わせ問題(SAT)を利用してデータベース上の問題を解くという方針をとる．変換アルゴリズムの構築が容易であることと，SATに対する既存の高速アルゴリズムを利用できるといった利点が考えられる．本稿では大学情報処理の一つである研究室配属問題を部分MAXSATに変換して解くことを試みた．ランダム例題を用いて，我々の方法と研究室配属問題を直接解くアルゴリズムとを比較した．その結果，変換を用いた方法がある程度有効であることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We focus on combinatorial optimization problems on databases which are complicated but not too large. In this paper, we select the Student Assignment Problem(SAP), in which we assign university students to university laboratories according to their desire and records. Our approach is not to solve the original problem directly but to translate it to Partial MAXSAT, a combinatorial optimization problem, to use fast and efficient SAT algorithms. We compare our approach with three simple algorithms and show the efficiency of our method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 1998, 号 57(1998-DBS-116), p. 335-342, 発行日 1998-07-08
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会