{"created":"2023-05-15T12:16:51.179247+00:00","id":336,"links":{},"metadata":{"_buckets":{"deposit":"ac73f32e-e077-414a-8c39-f3a1e97dae89"},"_deposit":{"created_by":3,"id":"336","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"336"},"status":"published"},"_oai":{"id":"oai:tuis.repo.nii.ac.jp:00000336","sets":["1:4:37:106"]},"author_link":["1348","1349","1350"],"control_number":"336","item_1701328008552":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"東京情報大学","subitem_publisher_language":"ja"}]},"item_1_biblio_info_14":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2005-02-28","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"2","bibliographicPageEnd":"78","bibliographicPageStart":"67","bibliographicVolumeNumber":"8","bibliographic_titles":[{"bibliographic_title":"東京情報大学研究論集","bibliographic_titleLang":"ja"}]}]},"item_1_creator_6":{"attribute_name":"著者名(日)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"永井, 保夫","creatorNameLang":"ja"},{"creatorName":"ナガイ, ヤスオ","creatorNameLang":"ja-Kana"}],"nameIdentifiers":[{"nameIdentifier":"1348","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Nagai, Yasuo","creatorNameLang":"en"}]}]},"item_1_creator_7":{"attribute_name":"著者名よみ","attribute_type":"creator","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"1349","nameIdentifierScheme":"WEKO"}]}]},"item_1_creator_8":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"1350","nameIdentifierScheme":"WEKO"}]}]},"item_1_description_1":{"attribute_name":"ページ属性","attribute_value_mlt":[{"subitem_description":"P(論文)","subitem_description_type":"Other"}]},"item_1_description_11":{"attribute_name":"抄録(日)","attribute_value_mlt":[{"subitem_description":"制約充足問題は人工知能や画像解析の分野をはじめ、グラフの問題やパズルなどの探索問題、いわゆる組み合わせ問題を対象として研究がおこなわれている。制約充足問題とは、変数の有限集合および各変数に対応する離散値の有限集合のドメインから値を選択し、すべての制約を満足するように各変数に対して値を割り当てる問題である。制約とは適用対象の構成要素およびその属性間で成立する関係を宣言的に記述したものである。 制約充足問題における従来の解法としては、バックトラックを基本とした探索による方法や整合化手法などに代表される前処理を用いる方法が代表的である。この場合には、解法としては探索空間の全域を対象としてすべての可能性を探索するもので、アルゴリズムの完全性を保証している。完全性とは、探索空間に解が存在すれば、必ず見つけられることと、解がなければ必ず存在しないことを保証するものである。 このような体系的探索法を用いる解法では、生成検査法やバックトラック法などに基づき解が求められる。特に、すべての解を求める場合には、探索木全体の探査が要求される。バックトラックに基づいた探索では、無駄なバックトラックが頻発してしまい効率が悪い。特に、全解を求めたい場合には、探索木全体をたどることになってしまうので、無駄な分岐を避けることが望ましい。 本論文では、まず、バックトラックによる効率改善手法として、知的バックトラックの一種であるバックジャンピングやバックトラックと整合化手法を組み合わせたフォワードチェッキングといった無駄な探索枝を刈り込む手法について説明する。次に、制約充足問題の代表例である地図の色塗り問題へ適用し、その結果について示す。","subitem_description_language":"ja-Kana","subitem_description_type":"Other"}]},"item_1_description_12":{"attribute_name":"抄録(英)","attribute_value_mlt":[{"subitem_description":"In this paper, we describe and discuss improvement methods of systematic search for constraint satisfaction problems. Effectiveness of these improvement methods is shown using application of these methods to map coloring problem.","subitem_description_language":"en","subitem_description_type":"Other"}]},"item_1_source_id_13":{"attribute_name":"雑誌書誌ID","attribute_value_mlt":[{"subitem_source_identifier":"AA11155514","subitem_source_identifier_type":"NCID"}]},"item_1_text_10":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_language":"en","subitem_text_value":"Tokyo University of Information Sciences"}]},"item_1_text_9":{"attribute_name":"著者所属(日)","attribute_value_mlt":[{"subitem_text_language":"ja","subitem_text_value":"東京情報大学"}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2005-02-28"}],"displaytype":"detail","filename":"KJ00002362072.pdf","filesize":[{"value":"441.8 kB"}],"format":"application/pdf","license_note":"TUIS","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"KJ00002362072","url":"https://tuis.repo.nii.ac.jp/record/336/files/KJ00002362072.pdf"},"version_id":"86f9345b-80dd-41fe-adfc-27e33a2602da"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"制約充足問題","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"探索","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"バックトラック","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"アルゴリズム","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"効率化","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"constraint satisfaction problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"search","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"backtrack","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"algorithm","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"efficiency","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"departmental bulletin paper","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"制約充足問題における体系的探索手法の効率化についての検討","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"制約充足問題における体系的探索手法の効率化についての検討","subitem_title_language":"ja"},{"subitem_title":"Towards an Improvement of Systematic Search Methods for Constraint Satisfaction Problems","subitem_title_language":"en"}]},"item_type_id":"1","owner":"3","path":["106"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2005-02-28"},"publish_date":"2005-02-28","publish_status":"0","recid":"336","relation_version_is_last":true,"title":["制約充足問題における体系的探索手法の効率化についての検討"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2023-12-22T07:08:44.218863+00:00"}