2024-03-29T21:22:48Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000136532022-10-21T05:24:51Z00581:00742:00749
並列局所探索法における近傍サイズの最適決定方式とその組合せ回路テスト生成への応用Optimization of Neighborhood Size for Parallel Local Search and Its Application to Test Generation of Combinational Circuitsjpn論文http://id.nii.ac.jp/1001/00013653/Journal Articlehttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=13653&item_no=1&attribute_id=1&file_no=1Copyright (c) 1996 by the Information Processing Society of Japan並列処理株式会社日立製作所日立研究所株式会社日立製作所日立研究所株式会社日立製作所日立研究所夏目, 幸一郎畠山, 一実伊達, 博局所探索法は組合せ最適化問題を解く発見的手法のひとつであり 可能解Xの近傍にあるより良い可能解YをXに代入するという処理を行う.本論文では 特別な組合せ最適化問題を局所探索法で解く場合において 可能解Xをできるだけ速く最適解に近づけることを考える.その速度を理論的に求め それを最大にする近傍サイズの近似式を導く.さらに その結果を応用した組合せ回路の並列テストパターン生成手法を提案する.The local search is a heuristic approach to solve a combinational optimization problem. It includes the step of searching a better feasible solution Y in the neighborhood of a feasible solution X and substituting Y for X. In this paper, we consider an approach to bring a feasible solution X close to the optimum solution as fast as possible in the case of solving specific combinational optimization problem by the local search. We analyze the speed theoritically and present an approximation of optimal neighborhood size which maximize the speed. Moreover we apply the result to the parallel test generation of combinational circuits.AN00116647情報処理学会論文誌376118711951996-06-151882-77642009-06-29