2024-03-28T22:42:24Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000138062022-10-21T05:24:51Z00581:00755:00758
タグ付き環境によるATMSの探索範囲絞り込み方式Focussing the Search Space in the ATMS with Tagged Environmentjpn論文http://id.nii.ac.jp/1001/00013806/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=13806&item_no=1&attribute_id=1&file_no=1Copyright (c) 1995 by the Information Processing Society of Japan人工知能(株)日立製作所システム開発研究所(株)日立製作所ソフトウエア開発本部古賀, 明彦増位庄一人工知能の問題解決では、多くの仮説の組合せから目的を達成する組合せを探索する。このような仮説管理の手法としてATMSが提唱されている。従来のATMSは、横型探索であり、矛盾する仮説の組合せの刈り取りだけで探索範囲を絞り込むため、(1)割り当て問題などの許容解が多く存在する問題に対して、すべての許容解を生成し、組含せの爆発を起こす、(2)横型探索以外の探索戦略を組み込むことが難しいので、解決戦略があらかじめ分かっている場合でもその戦略の適用が困難である、などの欠点を持つ。本論文では、これらの欠点を解消する新しい方式を提案する。これは(a)仮説の組合せにタグを付け、探索の範囲をあるタグに限定することにより組合造爆発を防ぐ、(b)タグを動的に変更することにより、ATMSの探索を横型以外にも制御できる方式である。この実現のため、(C)ラベルを伝播するものとしないものに分け、またタグから仮説の組合せにリンクを張ることにより、タグの切り替え時にラベルを効率的に再伝播するアルゴリズムを開発した。提案方武を時間割り作成問題に適用した結果、従来、組合せ爆発を起こし、解を求めることができなかった問題の解を求められるようになった。また、時問割り作成問題を一般化した問題に対して、本方式により最良探索の探索戦略の組み込みが可能となることを明らかにした。AN00116647情報処理学会論文誌3610239123991995-10-151882-77642009-06-29