| 講演名 | 1996/10/1 等価変換による制約充足問題の解法 吹田 慶子, 赤間 清, 宮本 衛市, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 従来のプログラミングは、組み込みのデータ構造や制約を組み合わせてプログラムを記述することを基本に構成されているので、表視力が十分でなく、その限界を越えると急激に計算の効率が落ちる場合がある。その問題を解消するために本研究では「等価変換に基づく問題解決」を採用する。この計算の枠粗では、ユーザが新たなデータ構造や制約解消ルールを導入して、システムを順次改善できる拡張型のプログラミングを行なう。この方法で実際に制約充足問題の解法を行なった結果、大規模な問題における計算の爆発を回避することができた。 |
| 抄録(英) | In many conventional programming languages, programs are constructed from built-in data structures or built-in constraints. Due to the limitation of the expressive power, the computation may become very inefficeint when they are used to solve large and complicated problems. In order to overcome the difficulty, we adopt a new programming paradigm, called "equivalent transformation programming (ET-programming)", where programs consist of many equivalent transformation rules and control declarations, and problems are solved by reducing problems by equivalent transformation of problem descriptions. In this paper, we show that ET-programming is useful to surpress the combinatorial explosion when solving large constraint satisfaction problems. |
| キーワード(和) | 制約充足問題 / 等価変換 / 制約処理 / 計算の爆発 |
| キーワード(英) | constraint satisfaction / equivalent transformation / transformation rule / combinatorial explosion |
| 資料番号 | SS96-18 |
| 発行日 |
| 研究会情報 | |
| 研究会 | SS |
|---|---|
| 開催期間 | 1996/10/1(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Software Science (SS) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 等価変換による制約充足問題の解法 |
| サブタイトル（和） | |
| タイトル（英） | Solving Constraint Satisfaction Problems based on Equivalent Transformation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 制約充足問題 / constraint satisfaction |
| キーワード(2)（和/英） | 等価変換 / equivalent transformation |
| キーワード(3)（和/英） | 制約処理 / transformation rule |
| キーワード(4)（和/英） | 計算の爆発 / combinatorial explosion |
| 第 1 著者 氏名（和/英） | 吹田 慶子 / Keiko Suita |
| 第 1 著者 所属（和/英） | 北海道大学工学部システム情報工学専攻 Division of System and Information Engineering, Hokkaido University |
| 第 2 著者 氏名（和/英） | 赤間 清 / Kiyoshi Akama |
| 第 2 著者 所属（和/英） | 北海道大学工学部システム情報工学専攻 Division of System and Information Engineering, Hokkaido University |
| 第 3 著者 氏名（和/英） | 宮本 衛市 / Eiichi Miyamoto |
| 第 3 著者 所属（和/英） | 北海道大学工学部システム情報工学専攻 Division of System and Information Engineering, Hokkaido University |
| 発表年月日 | 1996/10/1 |
| 資料番号 | SS96-18 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 283 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |