概整合ラベリング問題における併合法の最適化と効率評価

概要

論文の詳細を見る
A consistent labeling problem, given an object consisting of many subparts and locally legal interpretations of each subparts, is an NP-complete problem of finding all of the totally consistent interpretations. An inexact consistent labeling problem is an extended version of the exact one as above, in which to each of the local interpretation a weight representing its appropriateness is attached. Thus solving an inexact problem is to find all of the total interpretations, or labelings,such that the sum of the weights of local interpretations does not exceed a certain error budget. Strategies for the inexact consistent labeling problem have been proposed in various ways so far,which fall into two main classes: the depth-first approach and the breadth-first approach. We investigate here another breadth-first approach called a merge method, which repeats local synthesizing operations using a given merge sequence. After giving precise definition of the inexact consistent labeling problem and its equivalent representation,the constraint network, we describe the strategy of the merge method and introduce two factors, the common length and the induction length,which seem to significantly affect the efficiency of the method. It is proved that,to shorten the total processing time,a large common length and a small induction length are preferable. Making use of this characteristic, we develop algorithms that give an optimal and a semioptimal merge sequences. Finally, we make some experiment to prove the efficiency of each algorithm and to clarify the influence of each factor.
社団法人人工知能学会の論文
1988-03-20

概整合ラベリング問題における併合法の最適化と効率評価

スポンサーリンク

概要

著者

関連論文

スポンサーリンク