JPH06203071A - パターン探索装置 - Google Patents

Abstract

(57)【要約】 【目的】 ノードの集合とノード間のアークとからなる
ネットワークとして表現された探索対象から効率的に特
定のパターンを探索するパターン探索装置を提供する。 【構成】 探索すべきパターンを入力する探索パターン
入力部１１、探索パターンに含まれるノードの探索順序
をユーザが指定するための探索順序指定部１２、探索パ
ターンに依存しない一般探索順序知識を入力する一般探
索順序知識入力部１３、探索順序を合成するための探索
順序合成知識を入力する探索順序合成知識入力部１５、
探索順序合成知識に従って一般探索順序知識とユーザに
より指定された探索順序から新たな探索順序を合成する
探索順序合成部１７、合成された探索順序に対して編集
を施す探索順序編集部１８および最終的に得られた探索
順序に従って探索対象から探索パターンを探索する探索
エンジン１９を有する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ノードの集合とノード
間のアークとからなるネットワークとして表現される探
索対象から特定のパターンを探索するパターン探索装置
に関する。

【０００２】

【従来の技術】ノードの集合とノード間のアークとから
なるネットワークとして表現されるものとしては、例え
ば電子回路が挙げられる。電子回路を構成するトランジ
スタ、抵抗等の素子がノードに、素子間の接続関係がア
ークに、回路全体がネットワークに相当する。このよう
なネットワークとして表現された対象（以下、探索対象
という）から、特定のパターンを探索したいという要求
がある。具体的には、例えば集積回路のレイアウト設計
に際しては、一般にある特定のパターンを構成している
部分はチップ上の近傍位置にまとめて配置するが、その
ためにはその特定のパターンを探索する必要がある。

【０００３】このような特定パターンの探索は、一般に
推論システムによって行われる。この特定パターンの探
索に際して、従来では探索したいパターン（以下、探索
パターンという）に含まれるノードと条件を手続き的に
記述している。この場合、ノードおよび条件の探索順序
の記述は、探索パターンに含まれるノードとその条件の
記述の手続きの中で一体となっているため、探索順序の
みを変更することは容易にはできない。また、探索パタ
ーンに含まれるノードとその条件および探索順序をプロ
ダクションシステムのルールのような形式で記述した場
合にも、探索順序は書き方に依存するため、細かい順序
の指定はできない。これらのことから、従来の方法では
探索パターンの探索効率が悪い。

【０００４】さらに、上述した探索パターンに含まれる
ノードとその条件および探索順序を記述する二つの方法
のいずれにおいても、探索順序の指定は個々の探索パタ
ーンについて個別に行わなければならないため、探索パ
ターンの種類が多くなるとパターンの探索効率が低下す
る。また、パターンの記述をグラフィカルに行なえるよ
うなものでは、探索順序を指定して推論効率を上げるこ
とができない。

【０００５】

【発明が解決しようとする課題】以上のように従来の技
術では、ノードの集合とノード間のアークとからなるネ
ットワークとして表現される探索対象から特定の探索パ
ターンを探索する場合、探索順序の変更ができないため
探索効率が悪いという問題があった。

【０００６】本発明は、ノードの集合とノード間のアー
クとからなるネットワークとして表現された探索対象か
ら、効率的に特定のパターンを探索することができるパ
ターン探索装置を提供することを目的とする。

【０００７】

【課題を解決するための手段】上記の課題を解決するた
め、本発明は探索パターンの記述と、探索パターン中の
ノードや条件の探索順序の指定の記述とを分離すること
を基本とする。

【０００８】すなわち、本発明のパターン探索装置は、
ノードの集合とノード間のアークとからなるネットワー
クとして表現された探索対象から特定の探索パターンを
探索するパターン探索装置において、探索パターンを入
力するための探索パターン入力手段と、この探索パター
ン入力手段により入力された探索パターンに含まれるノ
ードの探索順序を指定するための探索順序指定手段と、
この探索順序指定手段により指定された探索順序に従っ
て探索対象から探索パターンを探索する探索手段とを備
えることを基本的な特徴とする。

【０００９】また、本発明においては探索順序について
の個別の探索パターンに依存しない一般探索順序知識を
入力するための一般探索順序知識入力手段と、この一般
順序知識入力手段により入力された一般探索順序知識と
探索順序指定手段により指定された探索順序を組み合わ
せて新たな探索順序を合成する探索順序合成手段をさら
に備え、探索順序合成手段により合成された探索順序に
従って探索対象から探索パターンを探索する構成として
もよい。

【００１０】さらに、探索順序合成手段において新たな
探索順序を合成する方法を指定する探索順序合成知識を
入力するための探索順序合成知識入力手段をさらに備え
るようにしてもよい。また、探索順序合成手段により合
成された新たな探索順序に対して編集を施すための探索
順序編集手段をさらに備えるようにしてもよい。

【００１１】

【作用】このように本発明では、入力される探索パター
ンの記述とその探索パターン中のノードや条件の探索順
序の指定の記述を分離することにより、それぞれの記述
と保守を容易にし、探索順序をユーザが任意に指定する
ことが可能となる。これにより、探索パターンの探索効
率が向上する。

【００１２】また、一般的な探索順序の指定方法を一般
探索順序知識として用意すれば、この一般探索順序知識
についてはユーザが個々の探索パターンについて個別に
指定する必要がなくなる。探索順序の個別指定が必要な
場合には、データあるいは条件といった適当な単位を選
んで探索順序の指定が行なえることにより、探索順序の
指定・修正による探索パターンの探索効率向上が容易と
なる。

【００１３】

【実施例】以下、図面を参照して本発明の一実施例を説
明する。図１は本発明の一実施例に係るパターン探索装
置の構成を示すブロック図であり、図２は同実施例にお
ける探索順序指定の処理の流れを示すフローチャートで
ある。

【００１４】このパターン探索装置は、探索パターン入
力部１１、探索順序指定部１２、一般探索順序知識入力
部１３、一般探索順序知識ファイル１４、探索順序合成
知識入力部１５、探索順序合成知識ファイル１６、探索
順序合成部１７、探索順序編集部１８および探索エンジ
ン１９を有する。

【００１５】探索パターン入力部１１は探索パターン、
すなわちユーザが探索したいパターンを入力するための
もので、具体的には探索パターンの作成と必要に応じて
編集を行なうためのエディタが用いられる。本実施例に
おいては、探索対象は電子回路であり、トランジスタ・
抵抗等の素子がノードに、素子間の接続関係がアーク
に、回路がネットワークにそれぞれ相当するものとす
る。

【００１６】図３は、探索パターンの一例であり、４つ
のトランジスタＱ１〜Ｑ４と１つの抵抗Ｒが図示のよう
に接続されたネットワークからなる。なお、探索パター
ンには、このようなネットワーク構造以外にも、例えば
「抵抗Ｒの値は１０オーム以上」、「左上のトランジス
タＱ１と右上のトランジスタＱ２は同じタイプ」といっ
た条件が付加される場合もあり得るが、本実施例におい
てはこのような条件は付加されていないものと仮定して
説明する。

【００１７】探索順序指定部１２は、ユーザが探索パタ
ーン入力部１１によって入力した探索パターンに対し
て、探索パターン中に現れる各ノードをどのような順序
で探索するかを指定するためのエディタである。この探
索順序指定部１２による探索順序の指定を個別指定とい
う。

【００１８】図４は、図３の探索パターンに探索順序を
指定した一例であり、「左上のトランジスタＱ１→左下
のトランジスタＱ３→右上のトランジスタＱ２→右下の
トランジスタＱ３→真中の抵抗Ｒ」の順序で探索を行な
うように指定を行っていることを示している。

【００１９】一般探索順序知識入力部１３は、特定の探
索パターンに依存しない一般的な探索順序の指定のため
の基準が存在する場合、それを予め一般探索順序知識と
して入力するためのものである。このような一般的探索
順序知識として格納されている探索順序については、探
索順序指定部１２での個別指定を省略することができ
る。こうして入力された一般探索順序知識は、一般探索
順序知識ファイル１４に格納される。以下に、一般探索
順序知識の一例を示す。 ＜一般探索順序知識＞ （ａ）探索済みのノードと接続されているノードを先に
探す。 （ｂ）探索済みのノードとしてトランジスタがある場
合、そのトランジスタのベースよりもエミッタやコレク
タにつながっているノードを先に探す。 （ｃ）トランジスタと抵抗では、トランジスタを先に探
す。 （ｄ）探索済みのノードに多くつながっているノードを
先に探す。

【００２０】これらの一般探索順序知識は、先に書いて
あるものほど重要であり、適用する場合にはより先に書
いてあるものを優先するものとする。これによって図３
の探索順序の設定を行なう過程を示す。

【００２１】（１）まず、始めは探索済みのノードはな
いので（ｃ）が適用されるが、トランジスタは４つある
ため、そのうちの１つが適当に選ばれる。ここでは、左
上のトランジスタＱ１が選ばれたものとする。 （２）（ａ）が適用されて左下のトランジスタＱ１と真
中の抵抗Ｒが候補として残り、更に（ｃ）が適用されて
左下のトランジスタＱ３が２番目となる。 （３）（ａ）が適用されて右下のトランジスタＱ２と真
中の抵抗Ｒが候補として残り、更に（ｂ）が適用されて
真中の抵抗Ｒが３番目となる。

【００２２】（４）（１）が適用されて右下のトランジ
スタＱ３と右上のトランジスタＱ２が候補として残り、
更に（ｄ）が適用されて右下のトランジスタＱ４が４番
目となる。 （５）右上のトランジスタＱ２が最後（５番目）とな
る。

【００２３】探索順序指定部１２においてユーザにより
指定されたパターン別探索順序と、一般探索順序知識フ
ァイル１４から検索された一般探索順序知識とは探索順
序合成部１７により組み合わされ、新たな探索順序が合
成される。

【００２４】探索順序合成知識入力部１５は、探索順序
合成部１７において新たな探索順序を合成する方法を指
定する探索順序合成知識を入力するためのものである。
こうして入力された探索順序合成知識は、探索順序合成
知識ファイル１６に格納される。以下に、探索順序合成
知識の一例を示す。 ＜探索順序合成知識＞ （Ａ）ユーザによる探索順序の指定があれば、それを優
先する。 （Ｂ）ユーザによる探索順序の指定がなければ、一般探
索順序知識によって探索順序を指定する。 （Ｃ）（Ｂ）でも決まらない部分は、システムが適当に
指定する。

【００２５】このような探索順序合成知識が探索順序合
成知識ファイル１６に格納されており、またユーザが図
５に示したように部分的に探索順序を指定してあり、さ
らに前記（ａ）〜（ｄ）に例示した一般探索順序知識が
一般探索順序知識ファイル１４に格納されているとす
る。この場合、探索順序合成部１７で合成される新たな
探索順序は以下のような過程で行なわれる。 ＜合成される新たな探索順序＞ （１）（Ａ）によりまず左上のトランジスタＱ１が１番
目として確定する。 （２）他にユーザによる指定はないので、次は（Ｂ）に
より一般探索順序知識による指定が行なわれる。 （３）一般探索順序知識の（ａ）および（ｃ）により左
下のトランジスタＱ３が２番目となる。 （４）（１）および（２）により真中の抵抗Ｒが３番目
となる。 （５）（１）および（４）により右下のトランジスタＱ
４が４番目となる。 （６）右上のトランジスタＱ２が最後（５番目）とな
る。 以上のようにして求められた探索順序は、図６に示すよ
うになる。すなわち、Ｑ１→Ｑ３→Ｒ→Ｑ４→Ｑ２とな
る。

【００２６】また、このようにして一般探索順序知識に
よって生成された探索順序で探索を実行したところ時間
がかかったのでもっと効率を高めたいというような場
合、ユーザが見て順序を変更した方が良いと思われる部
分や特殊な順序づけが必要な部分などのみを探索順序編
集部１８で編集（修正）することも可能である。

【００２７】例えば、上述の例ではＱ１→Ｑ３→Ｒ→Ｑ
４→Ｑ２という探索順序が生成されたが、実は左下のト
ランジスタＱ３は特殊な条件が付けられており、その関
係でこのトランジスタＱ３を最初に探した方が良さそう
だということであれば、探索順序編集部１８によってＱ
３→Ｑ１→Ｒ→Ｑ４→Ｑ２のように探索順序を修正する
ことにより、効率を上げることができる。

【００２８】以上のようにして得られた探索順序の情報
は探索エンジン１９に入力され、この探索順序に従って
探索対象のネットワーク（この例では電子回路）から図
３のような探索パターンが探索される。

【００２９】なお、本発明は上記実施例に限定されるも
のではなく、次のように種々変形して実施することが可
能である。例えば、一般探索順序知識ファイル１４に格
納された一般探索順序知識によって完全には探索順序が
決まらない部分をユーザに逐次指定させるように、探索
順序合成知識ファイル１６から検索された探索順序合成
知識で指定することも可能である。

【００３０】また、同様にユーザが探索順序指定部１２
によって指定した探索順序を一般探索順序知識フファイ
ル１４から検索された一般探索順序知識によってチェッ
ク・修正することも可能である。

【００３１】これとは逆に、一般探索順序知識ファイル
１４から検索された一般探索順序知識によって生成され
た探索順序の一部をユーザが探索順序編集部１８によっ
て修正・変更することも可能である。

【００３２】さらに、上記実施例では探索対象のネット
ワークとして電子回路を示したが、例えば電力系統、上
下水道の管網、電話の回線網、計算機ネットワーク、あ
るいは機械の構成のようなものも探索対象のネットワー
クとすることができる。

【００３３】

【発明の効果】以上説明したように、本発明によれば探
索順序の指定が容易にできるようになるので、ノードと
アークとからなるネットワークとして表現される対象か
ら所望の探索パターンを効率よく探索することができ
る。また、このような探索効率の高い推論システム開発
のための労力や時間を削減することが可能となる。

【図面の簡単な説明】

【図１】本発明の一実施例に係るパターン探索装置の構
成を示すブロック図

【図２】同実施例におけるパターン探索手順を説明する
ためのフローチャート

【図３】同実施例の動作を説明するための探索パターン
の例を示す図

【図４】図３の探索パターンに探索順序を指定した一例
を示す図

【図５】図３の探索パターンに部分的に探索順序を指定
した一例を示す図

【図６】図３の探索パターンに探索順序を指定した他の
例を示す図

【符号の説明】

１１…探索パターン入力部 １２…探索順序
指定部 １３…一般探索順序知識入力部 １４…一般探索
順序知識ファイル １５…探索順序合成知識入力部 １６…探索順序
合成知識ファイル １７…探索順序合成部 １８…探索順序
編集部 １９…探索エンジン

Claims (2)

【特許請求の範囲】
1. 【請求項１】ノードの集合とノード間のアークとからな
   るネットワークとして表現された探索対象から特定の探
   索パターンを探索するパターン探索装置において、 前記探索パターンを入力するための探索パターン入力手
   段と、 この探索パターン入力手段により入力された探索パター
   ンに含まれるノードの探索順序を指定するための探索順
   序指定手段と、 この探索順序指定手段により指定された探索順序に従っ
   て前記探索対象から前記探索パターンを探索する探索手
   段とを備えることを特徴とするパターン探索装置。
2. 【請求項２】ノードの集合とノード間のアークとからな
   るネットワークとして表現された探索対象から特定の探
   索パターンを探索するパターン探索装置において、 前記探索パターンを入力するための探索パターン入力手
   段と、 この探索パターン入力手段により入力された探索パター
   ンに含まれるノードの探索順序を指定するための探索順
   序指定手段と、 前記探索順序についての個別の探索パターンに依存しな
   い一般探索順序知識を入力するための一般探索順序知識
   入力手段と、 この一般順序知識入力手段により入力された一般探索順
   序知識と前記探索順序指定手段により指定された探索順
   序を組み合わせて新たな探索順序を合成する探索順序合
   成手段と、 この探索順序合成手段により合成された探索順序に従っ
   て前記探索対象から前記探索パターンを探索する探索手
   段とを備えることを特徴とするパターン探索装置。