組合せ問題を高速に解くための論理型言語の設計,実現及び応用

用于高速解决组合问题的逻辑语言的设计、实现和应用

• 批准号: 05750383
• 负责人: 周 能法
• 金额: $ 0.38万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1993
• 资助国家: 日本
• 起止时间: 1993 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-05750383/
• 关键词: 組合せ探索; 論理プログラミング; Prolog; コンパイラ; グラク問題; 制約充足問題; プラニング問題; TSP問題

1.まず、Prologの拡張であるBeta-Prologの設計と実現を行なった.PrologにBoolean tableというバツクトラック可能なデータ構造を導入し,Boolean tableに対して,状態が真である組を選ぶ(select),状態をテストする(test),状態を更新する(up-date)及び状態が真である組を数える(count)などの述語を備えた.実際に,Beta-Prologのコンパイラを試作した.2.Beta-Prologを基本的なグラフ問題,制約充足問題,プラニング問題,TSP問題などへ応用した.結果として,これらの組合せ問題を全部状態遷移問題として定式化でき,Beta-PrologがPrologより遥かに有効であることが実証された.3.しかし,まだたくさんの問題が困難あるいは解決不能のままとなっている.例えば,108-queen問題の最初の解を求めるのに,10時間もかかってしまった.また,Deutshの四段層の配線問題は,一週間でも解けなかった.今後,コンパイラの最適化及び言語の並列化によって,さらに高速化を図る必要がある.

1. Design and implementation of Beta-Prolog.Prolog Boolean table to import possible data structures,Boolean table to select, state to test, state to up-date, state to count. 2.Beta-Prolog is a basic problem, constraint sufficiency problem, optimization problem,TSP problem. The result is that the problem of all state transitions is difficult to solve and cannot be solved. For example, 108-queen problem and the initial solution, 10 time limit. The wiring problem of Deutsh's four-segment layer is not solved during the week. From now on, optimization of communication technology and parallelism of speech will be necessary.

项目成果

周能法: "Beta-Prolog:An Extended Prolog with Boolean Tables" Proc.5th IEEE International Conf.on TAI. 312-319 (1993)

扩展 Prolog：“Beta-Prolog：带有布尔表的扩展 Prolog”Proc.5th IEEE International Conf.on TAI（1993 年）。

周能法: "An Etticient Finite-Domain Constraint Solver in Beta Prolog" 人工知能学会誌. 9. 275-282 (1994)

Beta Prolog 中的有效有限域约束求解器。日本人工智能学会杂志 9. 275-282 (1994)

周能法: "On the Scheme of Passing Arquments in Stack Frames" Proc.Int.Conf.On Logic Programming. to appear. (1994)

Shuenho：“关于在堆栈帧中传递参数的方案”，Proc.Int.Conf.On 逻辑编程 (1994)。