【事件の表示】
　平成　３年特許願第２１１２９３号「グラフ探索方法及び装置」拒絶査定に対する審判事件〔平成　５年　２月２６日出願公開、特開平　５−　４６５９０、請求項の数（５）〕について、次のとおり審決する。
【結　論】
　原査定を取り消す。
　本願の発明は、特許すべきものとする。
【理　由】
１．手続の経緯・本願発明
　本願は、平成３年７月３０日の出願であって、その請求項１乃至請求項５に係る発明（以下、本願発明という。）は、当審において平成１４年１月１１日付けの手続補正書によって補正された明細書の特許請求の範囲の請求項１乃至請求項５に記載された次のとおりのものと認める。
「【請求項１】
  入力手段と、演算処理手段と、ノード間の辺に実数値のコストが設定された有向グラフＧを記憶する記憶手段と、前記有向グラフＧの始点ｓからの部分経路を保持するための部分経路記憶手段と、表示装置を有するコンピュータ・システムにおいて、前記有向グラフＧ中の経路を探索するグラフ探索方法であって、
（Ａ）前記有向グラフＧ中の特定の２つのノードを、始点ｓ及び終点ｔとして、前記入力手段により入力する入力ステップと、
（Ｂ）始点ｓから終点ｔに至る経路のうち、探索すべき最適解経路の条件を入力する条件設定ステップと、
（Ｃ）前記演算処理手段により、前記有向グラフＧの全てのノードと終点ｔとの最短コストを算出する最短コスト算出ステップと、
（Ｄ−０）前記部分経路記憶手段に、経路長が長さ０の部分経路として 始点ｓを記憶するステップと、
（Ｄ−１）前記演算処理手段により、前記部分経路記憶手段に記憶された経路長が長さｉ-１（ｉ＝１，２，３，・・・）の部分経路から前記有向グラフＧに含まれる経路長が長さｉの部分経路を展開し、当該経路長が長さｉの部分経路から、始点ｓからのコストの累積と、残りの経路の前記最短コストとの和に基づき、前記最適解経路の条件を満たす部分経路を探索するステップと、
（Ｅ）探索された前記経路長が長さｉの部分経路を前記部分経路記憶手段に記憶するステップと、
（Ｆ）前記部分経路記憶手段中のすべての長さｉの部分経路が終点ｔに達していない場合、前記経路長ｉを１つ増分してステップ（Ｄ−１）に戻り、すべての長さｉの部分経路が終点ｔに達していれば下記ステップ（Ｇ）へ遷移するステップと、
（Ｇ）前記部分経路記憶手段に記憶されている終点ｔに達した全ての部分経路を前記最適解経路の条件を満たす解経路として前記表示装置に表示する解経路表示ステップと
を含むグラフ探索方法。
　【請求項２】
  入力手段と、演算処理手段と、ノード間の辺に実数値のコストが設定された有向グラフＧを記憶する記憶手段と、前記有向グラフＧの始点ｓからの部分経路を保持するための部分経路記憶手段と、表示装置を有するコンピュータ・システムにおいて、前記有向グラフＧ中の経路を探索するグラフ探索方法であって、
（Ａ）前記有向グラフＧ、および前記有向グラフＧ中の特定の２つのノードを、始点ｓ及び終点ｔとして、前記入力手段により入力する、グラフ入力ステップと、
（Ｂ）始点ｓから終点ｔに至る経路のうち、探索すべき最適解経路の条件を入力する条件設定ステップと、
（Ｃ）前記演算処理手段により、前記有向グラフＧの全てのノードと終点ｔとの最短コストを算出する最短コスト算出ステップと、
（Ｄ−０）前記部分経路記憶手段に、経路長が長さ０の部分経路として 始点ｓを記憶するステップと、
（Ｄ−１）前記演算処理手段により、前記部分経路記憶手段に記憶された経路長が長さｉ-１（ｉ＝１，２，３，・・・）の部分経路から前記有向グラフＧに含まれる経路長が長さｉの部分経路を展開し、当該経路長が長さｉの部分経路から、始点ｓからのコストの累積と、残りの経路の前記最短コストとの和に基づき、前記最適解経路の条件を満たす部分経路を探索するステップと、
（Ｅ）探索された前記経路長が長さｉの部分経路を前記部分経路記憶手段に記憶するステップと、
（Ｆ）前記部分経路記憶手段中のすべての長さｉの部分経路が終点ｔに達していない場合、前記経路長ｉを１つ増分してステップ（Ｄ−１）に戻り、すべての長さｉの部分経路が終点ｔに達していれば下記ステップ（Ｇ）へ遷移するステップと、
（Ｇ）前記部分経路記憶手段に記憶されている終点ｔに達した全ての部分経路を前記最適解経路の条件を満たす解経路として前記表示装置に表示する解経路表示ステップと
　を含むグラフ探索方法。
　【請求項３】
　 前記有向グラフＧが、形態素を解析すべき文のトレリスであり、前記グラフ入力ステップ（Ａ）において、前記有向グラフＧとして、前記トレリスを入力することにより、与えられた前記文について複数の最適な形態素の解を求めることを特徴とする請求項２記載のグラフ探索方法。
　【請求項４】
   前記コンピュータ・システムが、ナビゲーション・システムであり、前記グラフ入力ステップ（Ａ）において、前記有向グラフＧとして、道路網情報を入力することにより、複数の最短ルートを求めることを特徴とする請求項２記載のグラフ探索方法。
　【請求項５】
  入力手段と、演算処理手段と、ノード間の辺に実数値のコストが設定された有向グラフＧを記憶する記憶手段と、前記有向グラフＧの始点ｓからの部分経路を保持するための部分経路記憶手段と、表示装置を有するコンピュータ・システムにおいて、前記有向グラフＧ中の経路を探索するグラフ装置であって、
（Ａ）前記入力手段において前記有向グラフＧ中の特定の２つのノードを、始点ｓ及び終点ｔとして入力する手段と、
（Ｂ）始点ｓから終点ｔに至る経路のうち、探索すべき最適解経路の条件を入力する条件設定手段と、
（Ｃ）前記演算処理手段により、前記有向グラフＧの全てのノードと終点ｔとの最短コストを算出する最短コスト算出手段と、
（Ｄ−０）前記部分経路記憶手段に、経路長が長さ０の部分経路として 始点ｓを記憶する手段と、
（Ｄ−１）前記演算処理手段により、前記部分経路記憶手段に記憶された経路長が長さｉ-１（ｉ＝１，２，３，・・・）の部分経路から前記有向グラフＧに含まれる経路長が長さｉの部分経路を展開し、当該経路長が長さｉの部分経路から、始点ｓからのコストの累積と、残りの経路の前記最短コストとの和に基づき、前記最適解経路の条件を満たす部分経路を探索する手段と、
（Ｅ）探索された前記経路長が長さｉの部分経路を前記部分経路記憶手段に記憶する手段と、
（Ｆ）前記部分経路記憶手段中のすべての長さｉの部分経路が終点ｔに達していない場合、前記経路長ｉを１つ増分して手段（Ｄ−１）に戻り、すべての長さｉの部分経路が終点ｔに達していれば下記手段（Ｇ）へ遷移する手段と、
（Ｇ）前記部分経路記憶手段に記憶されている終点ｔに達した全ての部分経路を前記最適解経路の条件を満たす解経路として前記表示装置に表示する解経路表示手段と
　を含むグラフ探索装置。」
２．原査定の拒絶の理由
　原査定の拒絶の理由の概容は、「本願の請求項に係る発明は、有向グラフにおいて最短経路を求めるための探索アルゴリズム、すなわち数学的アルゴリズムをコンピュータシステム上で実行するための方法及び装置であって、そのアルゴリズム自体に自然法則の利用性はなく、また、コンピュータのハードウエア資源を利用したと言える構成の記載もない。
　したがって、本願の請求項に係る発明は自然法則を利用した技術的思想の創作には該当せず、特許法第２条でいう「発明」に該当しないから、特許法第２９条第１項柱書に規定する要件を満たしていない。」というものである。
３．当審の判断
　そこで、まず、本願の請求項１に係る発明が、自然法則を利用した技術的思想の創作に該当するか検討する。
　請求項１に係る発明は、上記のとおり、有向グラフにおいて最短経路を求めるための探索アルゴリズムをコンピュータシステム上で実行するための方法であって、当該コンピュータシステムは、入力手段と、演算処理手段と、ノード間の辺に実数値のコストが設定された有向グラフＧを記憶する記憶手段と、前記有向グラフＧの始点ｓからの部分経路を保持するための部分経路記憶手段と、表示装置を有するものであって、上記探索アルゴリズムは、初期設定を行うステップである
（Ａ）前記有向グラフＧ中の特定の２つのノードを、始点ｓ及び終点ｔとして、前記入力手段により入力する入力ステップと、
（Ｂ）始点ｓから終点ｔに至る経路のうち、探索すべき最適解経路の条件を入力する条件設定ステップと、
（Ｃ）前記演算処理手段により、前記有向グラフＧの全てのノードと終点ｔとの最短コストを算出する最短コスト算出ステップと、
（Ｄ−０）前記部分経路記憶手段に、経路長が長さ０の部分経路として 始点ｓを記憶するステップと、
　探索を実行し、探索の終了を判定するステップである
（Ｄ−１）前記演算処理手段により、前記部分経路記憶手段に記憶された経路長が長さｉ-１（ｉ＝１，２，３，・・・）の部分経路から前記有向グラフＧに含まれる経路長が長さｉの部分経路を展開し、当該経路長が長さｉの部分経路から、始点ｓからのコストの累積と、残りの経路の前記最短コストとの和に基づき、前記最適解経路の条件を満たす部分経路を探索するステップと、
（Ｅ）探索された前記経路長が長さｉの部分経路を前記部分経路記憶手段に記憶するステップと、
（Ｆ）前記部分経路記憶手段中のすべての長さｉの部分経路が終点ｔに達していない場合、前記経路長ｉを１つ増分してステップ（Ｄ−１）に戻り、すべての長さｉの部分経路が終点ｔに達していれば下記ステップ（Ｇ）へ遷移するステップと、
　探索終了時の処理を行うステップである
（Ｇ）前記部分経路記憶手段に記憶されている終点ｔに達した全ての部分経路を前記最適解経路の条件を満たす解経路として前記表示装置に表示する解経路表示ステップ
とからなるものである。
　そして、上記ステップ（Ｃ）における「有向グラフＧの全てのノードと終点ｔとの最短コストを算出する」ことが、いわゆるダイクストラ法等の周知の手法で実現可能であることを勘案すると、上記探索アルゴリズムは、当該アルゴリズムをコンピュータ上で実行するプログラムを唯一定めるまで規定されたものではないが、初期設定、処理内容及び処理の終了条件等を明確にし、コンピュータ上のアルゴリズムを、請求項の記載に基づいて当業者が把握できる程度に具体的に記載されたものであり、コンピュータのハードウェアをどのように利用するかも明確なものである。
　したがって、もはや、本願の請求項１に係る発明は、これが、コンピュータシステムを単に利用したのみであって、実質的に自然法則を利用した技術思想ではない、とすることはできない。
　上記請求項１に係る発明についてと同様の理由により、本願の請求項２乃至５に係る発明も、コンピュータシステムを単に利用したのみであって、実質的に自然法則を利用した技術思想ではないとすることはできない。
４．むすび
　以上のとおりであるから、原査定の理由によっては、本願を拒絶することはできない。
　また、他に本願を拒絶すべき理由を発見しない。
　よって、結論のとおり審決する。