(57)【特許請求の範囲】
【請求項１】
互いに組み合わせて接続することにより物質またはエネルギーまたは信号を伝達する経路を構成可能な複数の配線要素であり、かつ同じ配線設備に設置されたものはその形状、特性および品質が全て同一である配線要素を、１以上の配線要素をそれぞれ含む複数の配線要素グループに分類する方法において、
配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を保持する配線要素データベースと、配線要素を配線要素グループに分類した結果に関する情報を保持する配線要素グループデータベースとを備えたコンピュータを用い、
当該コンピュータは、
配線要素データベースから配線要素を読み出し、全ての配線要素について同じ配線設備に含まれ、かつ下部側および上部側の接続状態が同じである配線要素のみからなる配線要素グループに分類し、更新リストに追加する工程と、
更新リストから配線要素グループを取り出し、当該配線要素グループ内の配線要素について下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである配線要素のみからなる等価配線要素グループに分割し、分割された元の配線要素グループと下部側または上部側で接続されている配線要素グループを更新リストに追加し、これを更新リストが空になるまで繰り返す工程と、
各等価配線要素グループに含まれる配線要素、下部側および上部側の接続状態、下部側と接続可能な配線要素グループの集合および上部側と接続可能な配線要素グループの集合に関する情報を配線要素グループデータベースに登録する工程とを実行する
ことを特徴とする配線要素の配線要素グループへの分類方法。
【請求項２】
互いに組み合わせて接続することにより物質またはエネルギーまたは信号を伝達する経路を構成可能な複数の配線要素であり、かつ同じ配線設備に設置されたものはその形状、特性および品質が全て同一である配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである１以上の配線要素をそれぞれ含む複数の配線要素グループに分類した結果を、いずれかの配線要素グループに含まれる配線要素の配線設備に対する設置状況またはその接続状態が変更された際に更新する方法であって、
配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を保持する配線要素データベースと、前記配線要素を配線要素グループに分類した結果に関する情報を保持する配線要素グループデータベースとを備えたコンピュータを用い、
当該コンピュータは、
設置状況または接続状態が変更された配線要素に関する情報で配線要素データベースを更新するとともに、当該設置状況または接続状態が変更された配線要素と接続済経路によって到達可能な配線要素を配線要素データベースを参照して抽出し、これらの配線要素を配線要素グループデータベースに登録された配線要素グループから削除する工程と、
削除した配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである配線要素のみからなる新たな等価配線要素グループに分類し、配線要素グループデータベースに登録する工程と、
新たな等価配線要素グループの接続済ネットワークと同型の既存の等価配線要素グループの接続済ネットワークを配線要素グループデータベースを参照して抽出し、対応する等価配線要素グループ同士を合成し、配線要素グループデータベースを更新する工程とを実行する
ことを特徴とする配線要素グループの更新方法。
【請求項３】
互いに組み合わせて接続することにより物質またはエネルギーまたは信号を伝達する経路を構成可能な複数の配線要素であり、かつ同じ配線設備に設置されたものはその形状、特性および品質が全て同一である配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである１以上の配線要素をそれぞれ含む複数の配線要素グループに分類した結果に関する情報を用いて、配線要素グループ同士の接続条件に関する組合せ可否を判定する方法であって、
前記配線要素を配線要素グループに分類した結果に関する情報を保持する配線要素グループデータベースを備えたコンピュータを用い、
当該コンピュータは、
一の配線要素グループの下部側と他の配線要素グループの上部側との組合せ可否を、配線要素グループデータベースから一の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベースから他の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定し、また、
一の配線要素グループの上部側と他の配線要素グループの下部側との組合せ可否を、配線要素グループデータベースから一の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベースから他の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定する
ことを特徴とする配線要素グループの組合せ可否判定方法。
【請求項４】
互いに組み合わせて接続することにより物質またはエネルギーまたは信号を伝達する経路を構成可能な複数の配線要素であり、かつ同じ配線設備に設置されたものはその形状、特性および品質が全て同一である配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである１以上の配線要素をそれぞれ含む複数の配線要素グループに分類した結果に関する情報とともに、配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を用いて、複数の配線要素の中から所定の選定条件に適合した経路を構成し得る配線要素の組合せを探索する方法であって、
前記配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を保持する配線要素データベースと、前記配線要素を配線要素グループに分類した結果に関する情報を保持する配線要素グループデータベースとを備えたコンピュータを用い、
当該コンピュータは、
所定の選定条件を満たす配線要素グループの組合せを配線要素データベースおよび配線要素グループデータベースを参照し、かつ配線要素グループ同士の組合せ可否を請求項３記載の配線要素グループの組合せ可否判定方法により判定して求める工程と、
求められた配線要素グループの組合せのうち、選定者から選択された組合せあるいは評価値の優れた組合せを構成する配線要素グループに含まれる配線要素の中から、所定の選定条件を満たす配線要素の組合せを配線要素データベースおよび配線要素グループデータベースを参照して求める工程とを実行する
ことを特徴とする経路探索方法。
【請求項５】
互いに組み合わせて接続することにより物質またはエネルギーまたは信号を伝達する経路を構成可能な複数の配線要素であり、かつ同じ配線設備に設置されたものはその形状、特性および品質が全て同一である配線要素を、１以上の配線要素をそれぞれ含む複数の配線要素グループに分類する装置において、
配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を保持する配線要素データベースと、
配線要素を配線要素グループに分類した結果に関する情報を保持する配線要素グループデータベースと、
配線要素データベースから配線要素を読み出して配線要素分類部へ出力するとともに、配線要素分類部から入力された各等価配線要素グループに含まれる配線要素、下部側および上部側の接続状態、下部側と接続可能な配線要素グループの集合および上部側と接続可能な配線要素グループの集合に関する情報を配線要素グループデータベースに登録する配線要素グループ管理部と、
配線要素グループ管理部から出力された全ての配線要素について、同じ配線設備に含まれ、かつ下部側および上部側の接続状態が同じである配線要素のみからなる配線要素グループに分類し、更新リストに追加し、更新リストから配線要素グループを取り出し、当該配線要素グループ内の配線要素について下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである配線要素のみからなる等価配線要素グループに分割し、分割された元の配線要素グループと下部側または上部側で接続されている配線要素グループを更新リストに追加し、これを更新リストが空になるまで繰り返し、その結果を配線要素グループ管理部へ入力する配線要素分類部とを備えた
ことを特徴とする配線要素の配線要素グループへの分類装置。
【請求項６】
互いに組み合わせて接続することにより物質またはエネルギーまたは信号を伝達する経路を構成可能な複数の配線要素であり、かつ同じ配線設備に設置されたものはその形状、特性および品質が全て同一である配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである１以上の配線要素をそれぞれ含む複数の配線要素グループに分類した結果を、いずれかの配線要素グループに含まれる配線要素の配線設備に対する設置状況またはその接続状態が変更された際に更新する装置であって、
配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を保持する配線要素データベースと、
前記配線要素を配線要素グループに分類した結果に関する情報を保持する配線要素グループデータベースと、
設置状況または接続状態が変更された配線要素に関する情報で配線要素データベースを更新するとともに、当該設置状況または接続状態が変更された配線要素に関する情報を配線要素グループ管理部へ出力する配線要素データベース更新部と、
配線要素データベース更新部から出力された設置状況または接続状態が変更された配線要素と接続済経路によって到達可能な配線要素を配線要素データベースを参照して抽出し、これらの配線要素を配線要素グループデータベースに登録された配線要素グループから削除するともにその情報を配線要素分類部へ出力し、配線要素分類部から入力された新たな等価配線要素グループを配線要素グループデータベースに登録するとともに等価配線要素グループの接続済ネットワーク比較部へ出力し、等価配線要素グループの接続済ネットワーク比較部から入力された同型の既存の等価配線要素グループの接続済ネットワークと新たな等価配線要素グループの接続済ネットワークとの等価配線要素グループ同士を合成し、配線要素グループデータベースを更新する配線要素グループ管理部と、
配線要素グループ管理部から出力された削除した配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである配線要素のみからなる新たな等価配線要素グループに分類し、その情報を配線要素グループ管理部へ入力する配線要素分類部と、
配線要素グループ管理部から出力された新たな等価配線要素グループの接続済ネットワークと同型の既存の等価配線要素グループの接続済ネットワークを配線要素グループデータベースを参照して抽出し、配線要素グループ管理部へ入力する等価配線要素グループの接続済ネットワーク比較部とを備えた
ことを特徴とする配線要素グループの更新装置。
【請求項７】
互いに組み合わせて接続することにより物質またはエネルギーまたは信号を伝達する経路を構成可能な複数の配線要素であり、かつ同じ配線設備に設置されたものはその形状、特性および品質が全て同一である配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである１以上の配線要素をそれぞれ含む複数の配線要素グループに分類した結果に関する情報を用いて、配線要素グループ同士の接続条件に関する組合せ可否を判定する装置であって、
前記配線要素を配線要素グループに分類した結果に関する情報を保持する配線要素グループデータベースと、
一の配線要素グループの下部側と他の配線要素グループの上部側との組合せ可否を、配線要素グループデータベースから一の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベースから他の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定し、また、一の配線要素グループの上部側と他の配線要素グループの下部側との組合せ可否を、配線要素グループデータベースから一の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベースから他の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定する配線要素グループ用組合せ可否判定部とを備えた
ことを特徴とする配線要素グループの組合せ可否判定装置。
【請求項８】
互いに組み合わせて接続することにより物質またはエネルギーまたは信号を伝達する経路を構成可能な複数の配線要素であり、かつ同じ配線設備に設置されたものはその形状、特性および品質が全て同一である配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである１以上の配線要素をそれぞれ含む複数の配線要素グループに分類した結果に関する情報とともに、配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を用いて、複数の配線要素の中から所定の選定条件に適合した経路を構成し得る配線要素の組合せを探索する装置であって、
前記配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を保持する配線要素データベースと、
前記配線要素を配線要素グループに分類した結果に関する情報を保持する配線要素グループデータベースと、
配線要素グループに関する情報の取得を組合せ対象データロード部に依頼し、取得した配線要素グループの中から所定の選定条件を満たす配線要素グループの組合せを、配線要素グループ同士の組合せ可否の判定を配線要素グループ用組合せ可否判定部に依頼して求め、求められた配線要素グループの組合せのうち、選定者から選択された組合せあるいは評価値の優れた組合せを構成する配線要素グループに含まれる配線要素に関する情報の取得を組合せ対象データロード部に依頼し、取得した配線要素の中から所定の選定条件を満たす配線要素の組合せを、配線要素同士の組合せ可否の判定を配線要素用組合せ可否判定部に依頼して求める組合せ探索部と、
組合せ探索部からの依頼に基づき、配線要素グループデータベースまたは配線要素データベースから配線要素グループまたは配線要素に関する情報を取得し、組合せ探索部へ返却する組合せ対象データロード部と、
組合せ探索部から出力された配線要素グループ同士の組合せ可否を、一の配線要素グループの下部側と他の配線要素グループの上部側との組合せ可否については、配線要素グループデータベースから一の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベースから他の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定し、また、一の配線要素グループの上部側と他の配線要素グループの下部側との組合せ可否については、配線要素グループデータベースから一の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベースから他の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定し、結果を組合せ探索部へ出力する配線要素グループ用組合せ可否判定部と、
組合せ探索部から出力された配線要素同士の組合せ可否を、配線要素データベースを参照して判定し、結果を組合せ探索部へ出力する配線要素用組合せ可否判定部とを備えた
ことを特徴とする経路探索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の配線要素の中から所定の条件に適合した経路を構成し得る配線要素の組合せを探索するための技術に関する。
【背景技術】
【０００２】
空間的に離れた複数の物体間で、２以上の配線要素（以下、記号ｅなどで表す）を組合せ、接続して経路を構成し、それら配線要素を経由して物質やエネルギー、信号を伝達する方法がある。但し、物質やエネルギー、信号をやりとりする物体自体も配線要素とする。一例として、光ファイバを使用した通信を行う場合の配線要素とその組合せによって構成される経路を図１に示す。この例では、
・ケーブルに含まれる光ファイバ
・架や電柱などに設置された複数の光ファイバ同士を中継するための各種アダプタやスプリッタに含まれる、ユーザ宅側端子と通信設備ビル側端子の組（コネクタ）
・通信装置のパッケージ（コネクタ）
・ユーザ宅内に設置される通信機器
が配線要素である。
【０００３】
本発明では、予め複数の配線要素が設置され、部分的には配線要素同士が接続されており、通常、配線要素の選定者によって与えられる所定の条件、例えば伝達の性質、速度や品質に関する条件を満たすように物質やエネルギー、信号のやりとりを必要に応じて行えるようにするため、経路を構成する配線要素を選択し、そのうち未接続の部分について配線要素同士を互いに接続する場合を考える。但し、配線要素とそれらの組合せによって構成される経路は、以下の条件を全て満たすものとする。
【０００４】
・配線要素には２個の端点があり（それぞれ「下部側」、「上部側」と呼ぶことにする）、異なる配線要素の下部側同士、上部側同士を接続することはない。また同一の配線要素の下部側と上部側を接続することはない。
【０００５】
・上部側で複数の配線要素と接続できる配線要素を、下部側で複数の配線要素と接続できる配線要素よりも下部側で経由する経路はない（図２参照）。
【０００６】
・各配線要素は、配線設備（以下、記号ｆなどで表す）のどれか１個に含まれる。但し、配線設備とは、以下の条件を満たす配線要素の集合である。
【０００７】
−配線設備ｆiに含まれる任意の配線要素ｅi、配線設備ｆjに含まれる任意の配線要素ｅjに関して、ｅiの下部側とｅjの上部側が接続可能だとする。このとき、配線設備ｆiに含まれる下部側の接続状態が「未接続」の任意の配線要素ｅi’、配線設備ｆjに含まれる上部側の接続状態が「未接続」の任意の配線要素ｅj’に関して、ｅi’の下部側とｅj’の上部側は接続可能である。
【０００８】
−同じ配線設備に含まれる配線要素は全て形状、特性、品質が同じ。
【０００９】
経路を構成する配線要素を選択するときには、以下の種類の条件を満たすように選択される必要がある。
【００１０】
・接続条件
選定者によって与えられた条件を満たすような経路を構成できるように、互いに接続できる位置関係、形状の配線要素を選択しなければならない。
【００１１】
・特性条件
配線要素の特性、品質は、選定者によって与えられる条件を満たすような、物質やエネルギー、信号の種類や内容を伝達できるものでなければならない。
【００１２】
また、配線要素の利用効率の向上、未接続点を接続する施工コストの低減などの評価尺度がある場合、これらの評価値の優れた組合せを求める必要がある。なお評価尺度には、客観的、定量的に評価できる明示的なものと、感覚的に評価する暗黙的なものがある。
【００１３】
〔従来の技術〕
配線要素の数が多い場合には、接続条件と特性条件を満たし、評価値の優れた配線要素の組合せを人手で求めることが困難になる。そのため、配線設備と配線要素の設置状況および接続状態を記憶装置に保持しておき、接続条件と特性条件を満たし、評価尺度が明示的に与えられていれば評価値の優れた組合せを計算機によって機械的に求め、選定者に提示し、その中から選定者が選択できるようにするための、選定方法および装置が考案されている。
【００１４】
〔従来技術１〕
非特許文献１では、光ファイバを使用した通信を行うときに使用する光ファイバやコネクタなどの配線要素を変数として、接続条件と特性条件を論理式で記述し、制約充足問題に帰着する方法が示されている。この方法によると、制約充足問題の各変数の取り得る値は配線要素であり、制約充足問題の解は配線要素の組合せとして表現される。条件を満たす配線要素の組合せが複数存在する場合には、それらの全てあるいは一部を列挙する。
【００１５】
〔従来技術２〕
非特許文献２では、光ファイバを使用した通信を行うときに使用する通信設備ビル内の配線要素を対象として、施工コストの低減を図りながら、接続条件と特性条件を満たす配線要素の組合せを求める方法が示されている。この方法によると、まず、複数の光ファイバからなるケーブル、複数のコネクタからなる架や通信装置などの配線設備に対して、収容関係にあるか否かを接続条件に関する組合せ可否の判定基準として、接続条件と特性条件を満たす配線設備の組合せを全て求める。
【００１６】
なお、配線設備、ここではケーブルと架または通信装置が収容関係にあるとは、そのケーブルが、その架または通信装置と他の架または通信装置との間に設置されており、そのケーブルに含まれる光ファイバとその架または通信装置に含まれるコネクタが接続できる状態にある（接続済も含む）ことをいう。
【００１７】
その後、配線設備の組合せそれぞれについて、その組合せを構成する配線設備に含まれる配線要素を対象として、接続条件と特性条件を満たす配線要素の組合せを求める。その結果、条件を満たす配線要素の組合せが複数存在する場合には、施工コストを評価し、それが最小の組合せを求め、選定者に提示する。
【００１８】
〔従来技術３〕
特許文献１においても非特許文献２と同様に、光ファイバを使用した通信を行うときに使用する通信設備ビル内の配線要素を対象として、配線要素の利用効率の向上と施工コストの低減を図りながら、接続条件と特性条件を満たす配線要素の組合せを求める方法が示されている。
【００１９】
この方法によると、非特許文献２と同様に、まず、配線設備に対して、収容関係にあるか否かを接続条件に関する組合せ可否の判定基準として、接続条件と特性条件を満たす配線設備の組合せを求める。このとき、収容しているケーブルが少ない架を含む配線設備の組合せを優先的に求めることで、配線要素の利用効率の向上を図る。
【００２０】
その後、求めた配線設備の組合せを構成する配線設備に含まれる配線要素を対象として、接続条件と特性条件を満たす配線要素の組合せを求める。その結果、条件を満たす配線要素の組合せが複数存在する場合には、施工コストを評価し、それが最小の組合せを求め、選定者に提示する。一方、条件を満たす配線要素の組合せが存在しない場合には、そのときの配線設備の組合せとともに提供予定の通信サービスの種別、組合せが存在しない原因などを保存し、その後の配線設備の増設計画に利用する。
【特許文献１】特開２００５−６３９７号公報
【非特許文献１】田山健一，山村哲哉“制約充足アプローチによる運用多様化に対応した設備選定アルゴリズムの提案”電子情報通信学会技術報告，Ｖｏｌ．１０３，Ｎｏ．５７３，Ｊａｎ．２００４，ｐｐ．８５−９０
【非特許文献２】東野光徳，井上晃，宇野浩司“所内光媒体ルート探索アルゴリズム”電子情報通信学会ソサエティ大会，Ｓｅｐ．２００２，ｐｐ．４６５
【非特許文献３】小笠原志朗，田山健一，山村哲哉“選定高速化のための光アクセス設備グループ化手法”電子情報通信学会ソサエティ大会，Ｓｅｐ．２００５，ｐｐ．３９２
【発明の開示】
【発明が解決しようとする課題】
【００２１】
多数の配線要素が設置され、またその中に未接続のものが含まれる場合、非特許文献１の方法では以下のような問題がある。
【００２２】
・制約充足問題の各変数の取り得る値は配線要素であり、制約条件を満たす配線要素の組合せを求めるためには、膨大な配線要素の組合せの中から制約条件を満たす組合せを探索しなければならず、多くの計算リソース（時間および記憶領域）が必要になる（課題１）。
【００２３】
・接続条件と特性条件を満たす配線要素の組合せは一般的に多数存在し、その中には互いに似た組合せが多数含まれる（図３参照）。これにより以下の問題が生じる（課題２）。なお、似た配線要素の組合せとは、ある配線要素の組合せに対して、その組合せに含まれる配線要素を、それぞれ同じ配線設備に含まれる別の配線要素に置き換えた組合せのことを指す。
【００２４】
◇制約充足問題として接続条件と特性条件を満たす配線要素の組合せを求めて選定者に提示し、その中から選定者が明示的および暗黙的な評価値の優れたものを選択する場合
制約充足問題の解は配線要素の組合せとして表現されるため、似た組合せは別の組合せであり、別の解となる。その結果、配線要素が多数ある場合には解の数が膨大になる。
【００２５】
−全ての解を求める場合
＊全ての解を求めるのに多大な時間がかかる。
【００２６】
＊選定者が解の全体を把握することは困難であり、評価値の優れた解を選択できない。
【００２７】
−全ての解を求めず、その一部のみを求める場合
＊得られる解には、似た組合せが含まれる一方で、全く異なる配線設備に含まれる配線要素の組合せで含まれないものがある。似た組合せでは配線要素の利用効率や施工コストなどの評価値も同程度であるのに比べ、似ていない組合せでは評価値が大きく変わる可能性が高いにも関わらず、得られる解に含まれないため評価されず、評価値の優れた解を選択できない。
【００２８】
◇制約充足問題として接続条件と特性条件を満たし、かつ明示的な評価尺度の観点から優れた配線要素の組合せを求めて選定者に提示する場合
−解の評価を行う評価値を、接続条件と特性条件を満たす配線要素の組合せを探索する最中にも計算できる場合
＊有効に探索範囲の枝刈を行える場合には、接続条件と特性条件を満たす解の数が膨大になることに起因する問題は生じない。
【００２９】
−解の評価を行う評価値を、接続条件と特性条件を満たす配線要素の組合せを探索する最中には計算できない場合
＊接続条件と特性条件を満たす配線要素の組合せを求めた上で評価値を計算する必要があるため、それら条件を満たす解の数が膨大になることに起因する上記問題に直面する。
【００３０】
実際の選定では、明示的な評価尺度だけではなく暗黙的な評価尺度も考慮する必要がある。従って、明示的な評価尺度の観点から優れた配線要素の組合せを求めて選定者に提示するように選定装置を作成したとしても、選定装置の利用時には、選定装置の作成時に組み込まれなかった暗黙的な評価尺度の観点から優れた配線要素の組合せも選択できることが求められる。その場合には、明示的な評価尺度の観点から最適な組合せ以外の組合せも選定者に提示する必要があり、上記の場合と同じ問題に直面する。
【００３１】
課題１、２を解決するために、接続条件と特性条件を満たす配線要素の組合せの数が絞り込まれるような条件を選定者が組合せの探索前に与えるようにするとともに、そのことを前提とした方法で組合せを求めることが考えられる。例えば図４のように配線要素が設置されている場合には、クラスタ１，４または５の配線要素を指定するような条件を選定前に選定者が必ず与えるようにすれば、条件を満たす配線要素の組合せの数を少なくすることができ、またそれに伴って組合せの探索に必要な計算リソースも削減できる。
【００３２】
しかし、このような解決方法は選定者によって与えられる条件および組合せを求める方法に強く依存するため、以下の問題を引き起こす（課題３）。
【００３３】
・ユーザが探索前に与えるべき条件および組合せを求める方法を、対象とする配線設備の設置形態ごとに考案し、用いる必要がある。
【００３４】
・選定方法が仮定している、ユーザが選定前に与えるべき条件を、実際の選定を行う際に常に指定できるとは限らない。その条件を指定せず、代わりに他の条件を用いて選定する場合には、組合せの数を少なくする効果が得られない。
【００３５】
非特許文献２や特許文献１の方法のように、まず第１段階として、複数の配線要素を含む配線設備に対して、収容関係にあるか否かを接続条件に関する組合せ可否判定基準として配線設備の組合せを求め、選択した後、第２段階として選択された組合せを構成する配線設備に含まれる配線要素に対してのみ配線要素の組合せを求めることで、上記課題１、２を解決できる。また、第１段階では配線要素をまとめて扱い、第２段階では配線要素の一部のみを探索対象とすることで組合せの数を減らしているため、その効果は選定者によって与えられる条件や組合せを求める方法に依存せず、課題３も解決できる。しかし以下のような問題がある。
【００３６】
・第２段階で配線要素を対象として接続条件と特性条件を満たす配線要素の組合せを求めたときに、それらの条件を満たす配線要素の組合せが存在しない場合がある、という非健全性の問題が生じる（課題４：図５参照）。このような、条件を満たす配線要素の組合せが最終的に存在しない配線設備の組合せに対して、接続条件と特性条件を満たす配線要素の組合せを求めようとすることは計算リソースの無駄であり、配線設備の組合せを求める段階で排除すべきである。
【００３７】
・接続条件と特性条件を満たす配線要素の組合せが存在する場合には、第２段階で求まる組合せは全て似たものであり、施工コスト等の評価値も同じ組合せが多数存在する。しかし評価値が異なる組合せも存在するため、結局、それら全ての組合せを求めて評価値を計算しており、余計な計算リソースを使用している（課題５）。
【００３８】
課題１〜５を解決するための方針が非特許文献３で提案されている。それによると、課題１、２を解決するため、選定前に配線要素を配線要素グループに分類しておく。そして選定時にはまず、配線要素グループの単位で接続条件と特性条件を満たす組合せを求める。その組合せの中から選定者が評価値の優れた組合せを選択した後、選択された配線要素グループに含まれる配線要素を対象として、接続条件と特性条件を満たす配線要素の組合せを求める。また、第１段階では配線要素をまとめて扱い、第２段階では配線要素の一部のみを探索対象とすることで組合せの数を減らしているため、その効果は選定者によって与えられる条件や組合せを求める方法に依存せず、課題３も解決できる。さらに非特許文献３では、非特許文献２や特許文献１の方法で生じる得る非健全性の問題（課題４）を解決するとともに、実際は条件を満たす配線要素の組合せを含む配線要素グループの組合せに対して条件を満たさないと判定してしまい、いつまでたってもその配線要素の組合せを選べず、配線要素を有効に利用できないという、非完全性の問題（課題６：図６参照）を生じないための、配線要素グループの分類基準および接続条件に関する組合せ可否判定基準を示している。しかし以下のような問題がある。
【００３９】
・分類基準を満たすように配線要素をグループに分類する方法が明らかにされていない（課題７）。
【００４０】
・配線要素間の接続状態が変化した際には分類を更新する必要があるが、更新方法についても明らかにされていない（課題８）。
【００４１】
本発明は、以下の課題を同時に解決するものである。
【００４２】
・探索の対象となる配線要素が多数存在し、条件を満たす配線要素の組合せを求めるのに多くの計算リソースが必要となる課題（課題１）。
【００４３】
・条件を満たす、似た配線要素の組合せが多数存在することで生じる課題（課題２）。
【００４４】
・課題１、２の解決のために選定者が与える条件を仮定し、それに基づいて組合せを求めるようにした場合に生じる課題（課題３）。
【００４５】
・課題１〜３の解決のために配線設備の組合せを求める際に生じる、非健全性と非完全性の課題（課題４、６）。
【００４６】
・課題１〜３の解決のために配線設備の組合せを求める際に生じる、評価値計算に使用される無駄な計算リソースの課題（課題５）。
【００４７】
・課題１〜６を解決するための、配線要素の配線要素グループへの分類方法、配線要素グループの更新方法、および配線要素グループの組合せ可否判定方法の具体的な内容が不明なため、経路探索での利用が困難（課題７，８）。
【課題を解決するための手段】
【００４８】
本発明では、条件を満たす配線要素の組合せを探索する際の探索量を小さくすることで必要な計算リソースを減らし、また条件を満たす配線要素の組合せが膨大な数となるのを防ぐとともに、これら効果を選定前に与える条件や組合せを求める方法によらずに得られるようにするため、配線要素を配線要素グループに分類し、分類して得られる配線要素グループに対して条件を満たす組合せを求め、その中から選択し、その選択された組合せを構成する等価配線要素グループに含まれる配線要素に対して、条件を満たす組合せを求めることを特徴とする。
【００４９】
また、本発明では、条件を満たす配線要素グループの組合せの探索において健全性と完全性を保証するため、配線要素を配線要素グループに分類するときの基準として、全ての配線要素を等価配線要素グループに分類し、また、条件を満たす配線要素グループの組合せを求めるときに、接続条件に関する組合せ可否判定基準として適合性を利用することを特徴とする。
【００５０】
また、本発明では、全ての配線要素を等価配線要素グループに分類するため、等価配線要素グループであるための条件のうち局所的に判断できる条件を満たすように配線要素を配線要素グループに分類し、その後、全ての配線要素グループが等価配線要素グループになるまで再帰的に配線要素グループを分割することを特徴とする。
【００５１】
また、本発明では、配線要素グループ同士の組合せ可否を判定するために、配線要素を配線要素グループに分類した際に、各配線要素グループに対してそれぞれ接続可能な配線要素グループを保存しておき、それを利用して適合性を調べ、組合せ可否を判定することを特徴とする。
【００５２】
また、本発明では、配線要素の設置状況または接続状態が変更されたときに、各配線要素グループが等価配線要素グループであり続けられるようにするため、設置状況または接続状態が変更された配線要素、およびその配線要素と接続済経路によって到達可能な配線要素を元の配線要素グループから除去し、除去された配線要素のみを使って新たな等価配線要素グループに分類することを特徴とする。
【００５３】
さらにまた、本発明では、等価配線要素グループの数を最小にしておくため、除去された配線要素のみを含む新たな等価配線要素グループで構成される接続済ネットワークと、既存の等価配線要素グループで構成される接続済ネットワークとを比較し、同型である場合には両方の接続済ネットワークを構成する等価配線要素グループで対応付けられるものをそれぞれ合成することを特徴とする。
【発明の効果】
【００５４】
配線要素を配線要素グループに分類し、条件を満たす配線要素グループの組合せを求めた後に、選定者が選択した配線要素グループ、あるいは評価値の優れた組合せを構成する配線要素グループに含まれる配線要素に対して、条件を満たす配線要素の組合せを求めることで、以下の効果がある。
【００５５】
・以下の効果により、条件を満たす配線要素の組合せの探索にかかる計算リソースを低減できる（課題１の解決）。
【００５６】
−配線要素の数に比べると、配線要素グループの数は少ないため、その組合せは非常に少ない。そのため、全ての配線要素に対して条件を満たす組合せを求める探索に比べると、全ての配線要素グループに対して条件を満たす組合せを求める探索では、探索量を小さくすることができる。
【００５７】
−全ての配線要素に対して条件を満たす組合せを求める探索に比べると、選択された配線要素グループの組合せを構成する配線要素グループに含まれる配線要素に対して条件を満たす組合せを求める探索では、対象とする配線要素の数を少なくできるため、探索量を小さくすることができる。
【００５８】
・配線要素の組合せを探索する前に、条件を満たす配線要素グループの組合せに対して、選定者が選択する、あるいは評価値の計算に基づき選択することで、条件を満たす配線要素の組合せが膨大になることで発生する問題を解決できる（課題２の解決）。
【００５９】
また、第１段階では配線要素をまとめて扱い、また第２段階では配線要素の一部のみを探索対象とすることで組合せの数を減らしているため、組合せの数を減らすのに選定者によって与えられる条件を仮定し、それに合わせた方法で組合せを求める場合に発生する問題を解決できる（課題３の解決）。
【００６０】
同時に、配線要素の配線要素グループへの分類の基準として、全ての配線要素を等価配線要素グループに分類し、また配線要素グループ同士の接続条件に関する組合せ可否判定基準として、配線要素グループの適合性を用いることにより、以下の効果がある。
【００６１】
・配線要素グループの組合せが条件を満たすならば、その組合せを構成する配線要素グループに含まれる配線要素に関して、条件を満たす組合せが存在することが保証される。そのため、条件を満たす配線要素の組合せを含まない配線要素グループの組合せに対して、条件を満たす配線要素の組合せを探索してしまう、という無駄な探索を省くことができる。これにより探索にかかる計算リソースを短縮できる。あるいは選定装置を使用する人が、配線要素の組合せを得られずに何度も配線要素グループの組合せを選択し直さなければならない、という無駄な操作をなくすことができる（課題４の解決）。
【００６２】
・配線要素の組合せが条件を満たすならば、それら配線要素を含む配線要素グループの組合せも条件を満たすことが保証される。そのため、ある配線要素の組合せが本当は条件を満たすのに、その配線要素を含む配線要素グループの組合せが、条件を満たす配線要素グループの組合せの中に存在せず、いつまでたってもその配線要素の組合せを使用できない、ということを避けられ、配線要素を有効に利用することができる（課題６の解決）。
【００６３】
・同じ等価配線要素グループに含まれる配線要素はどれも、接続状態とともに形状、特性、品質が同じである。従って、配線要素グループの組合せに対する評価値は、その組合せを構成する配線要素グループに含まれる配線要素の組合せに対する評価値と一致する。そのため、配線要素の組合せを全て求め、それぞれに対して評価値を計算する必要がなくなり、計算リソースを低減できる（課題５の解決）。
【００６４】
また、配線要素の等価配線要素グループへの分類方法により、上記効果を得られるように、配線要素をグループに分類することが可能となる（課題７の解決）。
【００６５】
さらに、配線要素の設置状況または接続状態が変更されたときに配線要素の配線要素グループへの分類を更新する方法の、以下の性質により、少ない計算リソースで更新を行うことができる（課題８の解決）。
【００６６】
・配線要素の設置状況または接続状態が変更されたときに、影響のある配線要素グループを特定して更新することで、配線要素の配線要素グループへの分類を最初からやり直す必要がない。また、更新に必要な情報は、更新前の配線要素グループの一部に関する情報と、設置状況または接続状態が変更された配線要素、およびその配線要素と接続済経路によって到達可能な配線要素に関する情報のみであり、それ以外の配線要素グループ、配線要素に関する情報を必要としない。
【００６７】
・配線要素グループは等価配線要素グループであり、それに含まれる配線要素の下部側、上部側の接続状態が一致するため、配線要素グループの下部側と上部側の接続状態を「未接続」または「接続済」のいずれかに決定することができる。そのため、配線要素グループの合成可否を判断する際に、配線要素の接続状態を考慮せずに配線要素グループに分類した場合には、接続可能な経路によって到達できる配線要素グループのネットワークの比較をしなければならないのに対し、等価配線要素グループの接続済ネットワークのみを比較すればよい。そのため比較範囲が小さい。また、等価配線要素グループの接続済ネットワークの構造は、２個の木構造をそれぞれの木のルートで接続したものであり、また木構造の同型性判定は、築山修治“アルゴリズムとデータ構造”コロナ社，Ｍａｒ．２００３，ｐｐ．５６−５９（公知文献）に示されている方法などより容易に行うことができる。
【発明を実施するための最良の形態】
【００６８】
〔発明方法の概要〕
本発明は、配線要素の管理における以下のフェーズにおいて用いられる。
【００６９】
・初期化フェーズ
選定前に、配線設備と配線要素の設置状況および接続状態を記憶装置に記録した後、配線要素を配線要素グループに初めて分類する段階。
【００７０】
・選定フェーズ
経路を構成する配線要素の選定（探索）を行う段階。
【００７１】
・更新フェーズ
配線要素同士を接続する、接続を解放する、あるいは配線要素を追加・削除するなど、配線要素の設置状況または接続状態が変更された後、配線要素の配線要素グループへの分類を更新する段階。
【００７２】
初期化フェーズ、選定フェーズ、更新フェーズの関係を図７に示す。
【００７３】
図８は本発明方法を実施する装置のハードウェア構成の概要、ここでは周知のコンピュータを用いた場合の例を示すもので、図中、１は入力部、２は出力部、３は配線要素データベース、４は配線要素グループデータベース、５はコンピュータ（本体）である。
【００７４】
入力部１は、周知のキーボードやマウスなどからなり、選定者から入力される各種の情報、具体的には、初期化フェーズにおける配線要素の配線要素グループへの分類依頼、選定フェーズにおける所定の選定条件（接続条件、特性条件、評価尺度に関する情報の全部または一部）や所定の選定条件を満たす配線要素グループの組合せの探索結果の中から選択した組合せ、更新フェーズにおける設置状況または接続状態が変更された配線要素に関する情報をコンピュータ５へ渡す。
【００７５】
出力部２は、周知の表示装置などからなり、コンピュータ５から出力される情報、具体定期には、選定フェーズにおける所定の選定条件を満たす配線要素グループの組合せの探索結果や所定の選定条件を満たす配線要素の組合せの探索結果を選定者に対して提示（表示）する。
【００７６】
配線要素データベース３は、配線設備に関する情報と配線要素の配線設備に対する設置状況およびその接続状態に関する情報を保持する。配線要素グループデータベース４は、配線要素を配線要素グループに分類した結果に関する情報を保持する。
【００７７】
コンピュータ５は、ＣＰＵ、メモリ等を備えた周知のものであり、初期化フェーズ、選定フェーズおよび更新フェーズにそれぞれ対応する、後述のフローチャートに示される手順を備えたプログラムに従って前記各部を制御し、本発明方法を実行する。
【００７８】
《初期化フェーズ》
初期化フェーズにおいては、選定を行う前に配線要素を「等価配線要素グループ」という、同じ配線要素グループに含まれる配線要素がどれも以下の条件を全て満たしているような配線要素グループ（以下、記号ｇなどで表す）に分類する。
（１）同じ配線設備に含まれる。
（２）配線要素の下部側について、「接続済」であるか「未接続」であるかの接続状態が同じ。
（３）配線要素の上部側について、「接続済」であるか「未接続」であるかの接続状態が同じ。
（４）配線要素の下部側と接続できる配線要素グループの集合が同じ。
（５）配線要素の上部側と接続できる配線要素グループの集合が同じ。
【００７９】
なお、分類基準の詳細については〔発明方法の詳細〕の《用語定義》および《配線要素の分類基準と接続条件に関する組合せ可否判断基準》にて後述する。
【００８０】
図９は本発明の配線要素の配線要素グループへの分類方法（初期化フェーズ）を示すフローチャートであり、以下、これに沿って本発明の配線要素グループの分類方法における処理の流れについて説明する。
【００８１】
入力部１から配線要素の配線要素グループへの分類依頼が入力されると、コンピュータ５は配線要素データベース３に保持された全ての配線要素に関する情報を配線要素の集合Ｅとして、該配線要素の集合Ｅから一つの配線要素ｅを取り出し（読み出し）、配線要素ｅに対して上記条件（１），（２），（３）を満たす配線要素グループｇを、メモリ内の作成済み配線要素グループの中から探索する（ｓ１）。
【００８２】
初期状態では、メモリ内に作成済み配線要素グループが１つも存在せず、当然、条件を満たす配線要素グループｇもメモリ内に存在しないため、コンピュータ５は、その配線設備並びに下部側および上部側の接続状態を、配線要素ｅの配線設備並びに下部側および上部側の接続状態そのままとした配線要素グループｇを作成してメモリ内に記録・保持する（ｓ２）とともに、当該配線要素グループｇを更新リストＧupdateに追加する（ｓ３）。なお、更新リストＧupdateはコンピュータ５のメモリ内に一時的に作成・保持されるリストである。
【００８３】
さらに、コンピュータ５は、メモリ上において配線要素グループｇに含まれる配線要素として配線要素ｅを追加・記録する（ｓ４）。
【００８４】
以下、コンピュータ５は、配線要素の集合Ｅが空になるまで前記同様の動作を繰り返すが、上記条件（１），（２），（３）を満たす配線要素グループｇがメモリ内に存在する場合は、単に、メモリ上において当該配線要素グループｇに含まれる配線要素として配線要素ｅを追加・記録する（ｓ４）。
【００８５】
コンピュータ５は、配線要素の集合Ｅが空になると、更新リストＧupdate内の配線要素グループを上記条件（４），（５）も満たすように分割する。具体的には、更新リストＧupdateから一つの配線要素グループｇを取り出し、該配線要素グループｇ内の配線要素について下部側と接続可能な配線要素グループの集合と、上部側と接続可能な配線要素グループの集合とに応じて分類し、必要に応じて配線要素グループｇを分割、即ち下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである配線要素のみからなる等価配線要素グループに分割するとともに、分割後の配線要素グループｇをメモリ内に記録・保持する（ｓ５）。
【００８６】
また、この際、コンピュータ５は、分割前の配線要素グループｇの下部側が「接続済」であれば該配線要素グループｇの下部側と接続済の配線要素グループを全て更新リストＧupdateに追加し（ｓ６）、分割前の配線要素グループｇの上部側が「接続済」であれば該配線要素グループｇの上部側と接続済の配線要素グループを全て更新リストＧupdateに追加した（ｓ７）（図１０参照）上で、当該配線要素グループｇをメモリ内から削除する（ｓ８）。
【００８７】
以下、コンピュータ５は、更新リストＧupdateが空になるまで前記同様の動作を繰り返すが、ｓ５で配線要素グループｇが分割されない場合は何もしない。
【００８８】
これにより、接続されている配線要素グループ同士で配線要素グループの分割が伝播し、全ての配線要素グループが等価配線要素グループになるまで再帰的に配線要素グループが分割される。また、接続できるが接続されていない配線要素グループ間では配線要素グループの分割は伝播せず、上記手順は収束する。
【００８９】
コンピュータ５は、更新リストＧupdateが空になると、削除されずにメモリ内に残っている全ての配線要素グループｇについて、条件（４），（５）を満たす過程で求まる、配線要素グループｇの下部側と接続できる配線要素グループの集合および上部側と接続できる配線要素グループの集合に関する情報を、選定フェーズにおいて組合せ可否を判定するための情報として、配線要素ｅの配線要素グループｇへの分類結果に関する情報、即ち配線要素グループｇに含まれる配線要素、下部側および上部側の接続状態に関する情報とともに、配線要素グループデータベース４に保存（登録）する（ｓ９）。
【００９０】
配線要素グループを等価配線要素グループに分類する過程の一例を図１１に示す。
【００９１】
なお、前記説明では、作成済み配線要素グループをコンピュータ５のメモリ内に記録・保持するとしたが、配線要素グループデータベース４（の所定のエリア内）に一時的に記録・保持するようにしてもよい。また、配線要素グループの分類方法の詳細については〔発明方法の詳細〕の《配線要素の分類方法》にて後述する。
【００９２】
《選定フェーズ》
図１２は本発明の経路探索（選定）方法を示すフローチャートであり、以下、これに沿って本発明の経路探索方法における処理の流れについて説明する。
【００９３】
入力部１から所定の選定条件、即ち接続条件と特性条件が入力される（ｓ１１）と、コンピュータ５は、当該条件を満たし、かつ評価値の優れた配線要素グループの組合せを配線要素データベース３および配線要素グループデータベース４を参照して求め、その結果を出力部２に出力（表示）する（ｓ１２）。
【００９４】
このような組合せを求める方法については、単純な木探索による方法や制約充足問題に帰着する方法などがあるが、本発明では特に限定しない。また、条件を満たす組合せを求めるとき、どのような方法を用いたとしても、配線要素グループ同士が組合せ可能か否かを判定する必要がある。例えば、非特許文献２や特許文献１の方法においてケーブルや架などの配線設備の組合せを求める際には、接続条件の組合せ可否を、ケーブルが架に収容されているかによって判定していた。
【００９５】
本発明では、配線要素グループｇiと配線要素グループｇjが以下のいずれかを満たすとき、「配線要素グループｇiの下部側と配線要素グループｇjの上部側は適合している」といい、このときに限り組合せ可能であると判定する。
【００９６】
・配線要素グループｇiに含まれる全ての配線要素の下部側と配線要素グループｇjに含まれる全ての配線要素の上部側の接続状態が共に「未接続」であり、配線要素グループｇiに含まれるどの配線要素も配線要素グループｇjに含まれる全ての配線要素と接続でき、かつ配線要素グループｇjに含まれるどの配線要素も配線要素グループｇiに含まれる全ての配線要素と接続できる。
【００９７】
・配線要素グループｇiに含まれる全ての配線要素の下部側と配線要素グループｇjに含まれる全ての配線要素の上部側の接続状態が共に「接続済」であり、配線要素グループｇiに含まれるどの配線要素も配線要素グループｇjに含まれる配線要素のどれかと接続され、かつ配線要素グループｇjに含まれるどの配線要素も配線要素グループｇiに含まれる配線要素のどれかと接続されている。
【００９８】
このように、配線要素を全て等価配線要素グループに分類し、またこの配線要素グループ間の適合性に基づいた組合せ可否判定基準を用いることで、健全性と完全性が保証される。詳細な条件については〔発明方法の詳細〕の《用語定義》および《配線要素の分類基準と接続条件に関する組合せ可否判定基準》にて後述する。
【００９９】
但し、２個の配線要素グループに対して、接続条件に関する組合せ可否判定基準に従って判定を行うときには、配線要素グループ間の適合性を直接調べるのではなく、初期化フェーズまたは更新フェーズにおいて配線要素グループデータベース４に登録しておいた、一方の配線要素グループの上部側または下部側と接続できる配線要素グループの集合に他方の配線要素グループが含まれるか否かを調べ、判定結果を得る。
【０１００】
具体的には、一の配線要素グループの下部側と他の配線要素グループの上部側との組合せ可否を、配線要素グループデータベース４から一の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベース４から他の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定し、また、一の配線要素グループの上部側と他の配線要素グループの下部側との組合せ可否を、配線要素グループデータベース４から一の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベース４から他の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定する。なお、詳細な方法については〔発明方法の詳細〕の《接続条件に関する組合せ可否判定方法》にて後述する。
【０１０１】
配線要素グループに含まれる配線要素は形状や特性、接続状態が同じであるため、特性条件に関する組合せ可否判定や評価値の最適化は、配線要素の組合せを求めるときと同じ方法をとる。
【０１０２】
コンピュータ５は、前記求められ出力部２に表示された配線要素グループの組合せのうち、選定者から入力部１を介して選択された組合せ、あるいは評価値の優れた組合せ（ｓ１３）を構成する配線要素グループに含まれる配線要素に対して、接続条件と特性条件を満たす配線要素の組合せを配線要素データベース３および配線要素グループデータベース４を参照して求め、その結果を出力部２に表示する（ｓ１４）。なお、配線要素の組合せを求める方法は、対象とする配線要素が絞り込まれている点を除けば、従来の方法と同じである。
【０１０３】
コンピュータ５は、前述した選定結果を否定する指示が選定者から入力部１を介して入力されるとｓ１３，ｓ１４を繰り返し、承認する指示が入力されると処理を終了する。
【０１０４】
《更新フェーズ》
配線要素の配線要素グループへの分類は、配線要素の設置状況と接続状態に基づいて行われるため、これらが更新（変更）されると配線要素グループも更新する必要がある。
【０１０５】
図１３は本発明の配線要素グループの更新方法を示すフローチャートであり、以下、これに沿って本発明の配線要素グループの更新方法における処理の流れについて説明する。
【０１０６】
まず、入力部１から設置状況または接続状態が変更された配線要素に関する情報が入力されると、コンピュータ５は配線要素の設置状況または接続状態の変更後にも各配線要素グループが等価配線要素グループであり続けられるようにするため、設置状況または接続状態が変更された配線要素に関する情報で配線要素データベース３を更新するとともに、当該設置状況または接続状態が変更された配線要素と接続済経路によって到達可能な配線要素を配線要素データベース３を参照して抽出し、これらの配線要素、即ち設置状況または接続状態が変更された配線要素および抽出した配線要素を配線要素グループデータベース４に登録された配線要素グループから削除する（ｓ２１）。
【０１０７】
次に、コンピュータ５は、前記削除した配線要素に対して《初期化フェーズ》の場合と同様の処理により新たな等価配線要素グループに分類し、配線要素グループデータベース４に登録する（ｓ２２）。
【０１０８】
その後、コンピュータ５は等価配線要素グループの数を最小にしておくため、合成できる等価配線要素グループを配線要素グループデータベース４を参照して抽出し（ｓ２３）、合成できる等価配線要素グループが存在すればそれらを合成し、配線要素グループデータベース４を更新し（ｓ２４）、なければそのまま処理を終了する。このため、既存の等価配線要素グループで互いに接続されているものによって構成されるネットワーク（等価配線要素グループの接続済ネットワーク）Ｎ(p)と、新しく作られた等価配線要素グループの接続済ネットワークＮ(q)とを比較する。Ｎ(p)とＮ(q)とが同型である、つまり以下の条件を満たすとき、対応付けられるＮ(p)の等価配線要素グループｇ(p)とＮ(q)の等価配線要素グループｇ(q)とをそれぞれ合成可能であると判定する。
【０１０９】
・Ｎ(p)とＮ(q)のグラフ構造が同じ。
【０１１０】
・上の条件が成り立つとき、対応付けられるＮ(p)の等価配線要素グループｇ(p)とＮ(q)の等価配線要素グループｇ(q)が、同じ配線設備に含まれる。
【０１１１】
配線要素グループの更新過程の一例を図１４に示す。
【０１１２】
等価配線要素グループを配線要素の分類基準とすることにより、他の分類基準を用いた場合に比べ、配線要素グループを合成できるか否かの判定を容易に行うことができる。
【０１１３】
なお、更新方法の詳細については〔発明方法の詳細〕の《配線要素グループの更新方法》にて後述する。
【０１１４】
〔発明装置の構成〕
図１５は初期化フェーズにおいて配線要素を配線要素グループに分類し、選定フェーズにおいて条件を満たす配線要素グループの組合せを求めた後、配線要素の組合せを求め、また更新フェーズにおいて配線要素グループを更新する本発明装置の構成を示すもので、前記同様な入力部１、出力部２、配線要素データベース３および配線要素グループデータベース４とともに、配線要素グループの分類および更新を行う更新部６、並びに経路選定を行う選定部７からなる。
【０１１５】
更新部６は、さらに配線要素グループ管理部６１と、配線要素分類部６２と、配線要素データベース更新部６３と、等価配線要素グループの接続済ネットワーク比較部６４とからなる。
【０１１６】
配線要素グループ管理部６１は、入力部１から配線要素の配線要素グループへの分類依頼を受け取り、配線要素データベース３から全ての配線要素に関する情報を取得して配線要素分類部６２へ渡す。また、配線要素分類部６２から受け取った各等価配線要素グループに含まれる配線要素、下部側および上部側の接続状態、下部側と接続可能な配線要素グループの集合および上部側と接続可能な配線要素グループの集合に関する情報を配線要素グループデータベース４に登録する。また、配線要素データベース更新部６３より設置状況または接続状態が変更された配線要素に関する情報を受け取り、その配線要素およびその配線要素と接続済経路によって到達可能な配線要素を配線要素データベース３を参照して抽出し、これらの配線要素を配線要素グループデータベース４に登録された配線要素グループから削除するともに、それらに関する情報を配線要素分類部６２へ渡す。また、配線要素分類部６２から受け取った新しく作成された等価配線要素グループに関する情報を配線要素グループデータベース４に登録するとともに等価配線要素グループの接続済ネットワーク比較部６４へ渡す。また、等価配線要素グループの接続済ネットワーク比較部６４から受け取った情報に基づき、同型の既存の等価配線要素グループの接続済ネットワークと新たな等価配線要素グループの接続済ネットワークとの等価配線要素グループ同士を合成し、配線要素グループデータベース４を更新する。
【０１１７】
配線要素分類部６２は、配線要素グループ管理部６１から受け取った全ての配線要素について、同じ配線設備に含まれ、かつ下部側および上部側の接続状態が同じである配線要素のみからなる配線要素グループに分類し、更新リストに追加し、更新リストから配線要素グループを取り出し、当該配線要素グループ内の配線要素について下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである配線要素のみからなる等価配線要素グループに分割し、分割された元の配線要素グループと下部側または上部側で接続されている配線要素グループを更新リストに追加し、これを更新リストが空になるまで繰り返し、その結果を配線要素グループ管理部６１へ渡す。また、配線要素グループ管理部６１から受け取った削除した配線要素を、同じ配線設備に含まれ、下部側および上部側の接続状態が同じであり、下部側と接続可能な配線要素グループの集合が同じであり、かつ上部側と接続可能な配線要素グループの集合が同じである配線要素のみからなる新たな等価配線要素グループに分類し、その情報を配線要素グループ管理部６１へ渡す。
【０１１８】
配線要素データベース更新部６３は、入力部１から入力された設置状況または接続状態が変更された配線要素に関する情報で配線要素データベース３を更新するとともに、当該設置状況または接続状態が変更された配線要素に関する情報を配線要素グループ管理部６１へ渡す。
【０１１９】
等価配線要素グループの接続済ネットワーク比較部６４は、配線要素グループ管理部６１から受け取った新たな等価配線要素グループの接続済ネットワークと同型の既存の等価配線要素グループの接続済ネットワークを配線要素グループデータベース４を参照して抽出し、その情報を配線要素グループ管理部６１へ渡す。
【０１２０】
選定部７は、さらに選定条件保持部７１と、組合せ探索部７２と、組合せ対象データロード部７３と、配線要素グループ用組合せ可否判定部７４と、配線要素用組合せ可否判定部７５とからなる。
【０１２１】
選定条件保持部７１は、所定の選定条件、即ち接続条件、特性条件、評価尺度（条件）のうち、予め入力された、あまり変化しない条件に関する情報を保持する。
【０１２２】
組合せ探索部７２は、所定の選定条件のうち、変化し易い条件に関する情報を入力部１から受け取るとともにあまり変化しない条件に関する情報を選定条件保持部７１から受け取り、全ての配線要素グループに関する情報の取得を組合せ対象データロード部７３に依頼し、取得した配線要素グループの中から所定の選定条件を満たす配線要素グループの組合せを、配線要素グループ同士の組合せ可否の判定を配線要素グループ用組合せ可否判定部７４に依頼して求め、出力部２に出力（表示）し、求められた配線要素グループの組合せのうち、選定者から入力部１を介して選択された組合せあるいは評価値の優れた組合せを構成する配線要素グループに含まれる配線要素に関する情報の取得を組合せ対象データロード部７３に依頼し、取得した配線要素の中から所定の選定条件を満たす配線要素の組合せを、配線要素同士の組合せ可否の判定を配線要素用組合せ可否判定部７５に依頼して求め、出力部２に出力（表示）する。
【０１２３】
組合せ対象データロード部７３は、組合せ探索部７２からの依頼に基づき、配線要素グループデータベース４または配線要素データベース３から配線要素グループまたは配線要素に関する情報を取得し、組合せ探索部７２へ返却する。
【０１２４】
配線要素グループ用組合せ可否判定部７４は、組合せ探索部７２から依頼された配線要素グループ同士の組合せ可否を、配線要素グループデータベース４を参照して判定、具体的には、一の配線要素グループの下部側と他の配線要素グループの上部側との組合せ可否を、配線要素グループデータベース４から（初期化フェーズまたは更新フェーズにおいて登録しておいた）一の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベース４から（初期化フェーズまたは更新フェーズにおいて登録しておいた）他の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定し、また、一の配線要素グループの上部側と他の配線要素グループの下部側との組合せ可否を、配線要素グループデータベース４から（初期化フェーズまたは更新フェーズにおいて登録しておいた）一の配線要素グループにおける上部側と接続可能な配線要素グループの集合を読み出し、当該集合に他の配線要素グループが含まれているかどうかより若しくは配線要素グループデータベース４から（初期化フェーズまたは更新フェーズにおいて登録しておいた）他の配線要素グループにおける下部側と接続可能な配線要素グループの集合を読み出し、当該集合に一の配線要素グループが含まれているかどうかより判定し、結果を組合せ探索部７２へ返却する。
【０１２５】
配線要素用組合せ可否判定部７５は、組合せ探索部７２から依頼された配線要素同士の組合せ可否を、配線要素データベース３を参照して判定し、結果を組合せ探索部へ返却する。
【０１２６】
〔発明方法の詳細〕
《用語定義》
本発明で使用する用語の定義について説明する。
【０１２７】
〈接続の定義〉
◇配線要素同士の接続
［定義１］−接続済−
配線要素ｅiの下部側と配線要素ｅjの上部側が接続されているとき、「ｅiの下部側とｅjの上部側は接続済である」という。またｅjを「ｅiの（下部側）接続先」、ｅiを「ｅjの（上部側）接続先」という。
【０１２８】
［定義２］−接続可能−
配線要素ｅiの下部側と配線要素ｅjの上部側が既に接続されているかによらず、接続できるとき、「ｅiの下部側とｅjの上部側は接続可能である」という。
【０１２９】
［定義３］−到達可能−
配線要素ｅiの下部側と配線要素ｅjの上部側が接続済、あるいはｅiの上部側とｅjの下部側が接続済であるとき、「ｅiとｅjは接続済経路によって到達可能」という。またｅiの下部側と配線要素ｅkの上部側が接続済、あるいはｅiの上部側とｅkの下部側が接続済で、ｅkとｅjが接続済経路によって到達可能である場合にも、「ｅiとｅjは接続済経路によって到達可能」という。
【０１３０】
◇配線要素と配線要素グループの接続
［定義４］−接続済−
配線要素ｅiと配線要素グループｇjに関して、ｅiの下部側と上部側で接続済の配線要素がｇjに１個以上含まれるとき、「配線要素ｅiの下部側と配線要素グループｇjの上部側は接続済である」という。同様に、ｅiの上部側と下部側で接続済の配線要素がｇjに１個以上含まれるとき、「配線要素グループｇjの下部側と配線要素ｅiの上部側は接続済である」という。図１６参照。
【０１３１】
［定義５］−強接続可能−
配線要素ｅiと配線要素グループｇjに関して、ｇjに含まれる全ての配線要素の上部側がｅiの下部側と接続可能であるとき、「配線要素ｅiの下部側と配線要素グループｇjの上部側は強接続可能である」という。同様に、配線要素ｅiと配線要素グループｇjに関して、ｇjに含まれる全ての配線要素の下部側がｅiの上部側と接続可能であるとき、「配線要素グループｇjの下部側と配線要素ｅiの上部側は強接続可能である」という。図１７参照。
【０１３２】
◇配線要素グループ同士の接続
［定義６］−接続済−
配線要素グループｇiと配線要素グループｇjに関して、ｇiに含まれる任意の配線要素ｅiの下部側がｇjの上部側と接続済であり、かつｇjに含まれる任意の配線要素ｅjの上部側がｇiの下部側と接続可能であるとき、「配線要素グループｇiの下部側と配線要素グループｇjの上部側は接続済である」という。図１８参照。
【０１３３】
［定義７］−強接続可能−
配線要素グループｇiと配線要素グループｇjに関して、ｇiに含まれる任意の配線要素の下部側がｇjの上部側と強接続可能であるとき、「配線要素グループｇiの下部側と配線要素グループｇjの上部側は強接続可能である」という。図１９参照。
【０１３４】
［定義８］−到達可能−
配線要素グループｇiの下部側と配線要素グループｇjの上部側が接続済、あるいはｇiの上部側とｇjの下部側が接続済であるとき、「ｇiとｇjは接続済経路によって到達可能」という。またｇiの下部側と配線要素グループｇkの上部側が接続済、あるいはｇiの上部側とｇkの下部側が接続済で、ｇkとｇjが接続済経路によって到達可能である場合にも、「ｇiとｇjは接続済経路によって到達可能」という。
【０１３５】
◇配線設備同士の関係
［定義９］
配線設備ｆiに含まれるある配線要素ｅiの下部側と、配線設備ｆjに含まれるある配線要素ｅjの上部側が接続可能であるとき、「配線設備ｆjが配線設備ｆiの下部側に設置されている」あるいは「配線設備ｆiが配線設備ｆjの上部側に設置されている」という。
【０１３６】
〈接続状態の定義〉
［定義１０］
配線要素ｅの上部側、下部側のそれぞれに対して、接続状態ｓをそれぞれstatusU(e)，statusL(e)で表し、以下の値をとるものとする。
【０１３７】
・接続済
ｅの上部側（下部側）が他の配線要素の下部側（上部側）と接続されているとき。
【０１３８】
・未接続
ｅの上部側（下部側）が他の配線要素の下部側（上部側）と接続されていないとき。
【０１３９】
［定義１１］
配線要素グループｇの上部側、下部側のそれぞれに対して、接続状態ｓをそれぞれstatusU(g)，statusL(g)で表し、以下の値をとるものとする。
【０１４０】
・接続済
ｇに含まれるどの配線要素の上部側（下部側）も他の配線要素の下部側（上部側）と接続されているとき。
【０１４１】
・未接続
ｇに含まれるどの配線要素の上部側（下部側）も他の配線要素の下部側（上部側）と接続されていないとき。
【０１４２】
・不定
上記以外。
【０１４３】
〈等価配線要素グループと適合性の定義〉
◇配線要素の分類基準
［定義１２］−局所的等価配線要素グループ−
配線要素グループｇが以下の条件を全て満たすとき、「ｇは局所的等価配線要素グループである」という。
【０１４４】
(i) ｇに含まれる配線要素が全て同じ設備に含まれる。
【０１４５】
(ii)ｇに含まれる配線要素の下部側の接続状態が全て同じである。
【０１４６】
(iii) ｇに含まれる配線要素の上部側の接続状態が全て同じである。
【０１４７】
［定義１３］−等価配線要素グループ−
局所的等価配線要素グループｇが以下の条件を全て満たすとき、「ｇは等価配線要素グループである」という。
【０１４８】
(iv)ｇの下部側について
・接続状態が「接続済」の場合
ｇに含まれる配線要素の下部側と上部側で接続済の配線要素グループの集合が全て同じである。
【０１４９】
・接続状態が「未接続」の場合
ｇに含まれる配線要素の下部側と上部側で強接続可能な配線要素グループの集合が全て同じである。
【０１５０】
ｇに含まれる配線要素の下部側全てに共通する、接続済または強接続可能な配線要素グループの集合を、「ｇの下部側配線要素グループ集合」といい、Ｇ*L（ｇ）で表す。
【０１５１】
(v) ｇの上部側について
・接続状態が「接続済」の場合
ｇに含まれる配線要素の上部側と下部側で接続済の配線要素グループの集合が全て同じである。
【０１５２】
・接続状態が「未接続」の場合
ｇに含まれる配線要素の上部側と下部側で強接続可能な配線要素グループの集合が全て同じである。
【０１５３】
ｇに含まれる配線要素の上部側全てに共通する、接続済または強接続可能な配線要素グループの集合を、「ｇの上部側配線要素グループ集合」といい、Ｇ*U（ｇ）で表す。
【０１５４】
◇配線要素グループの適合性
［定義１４］−適合−
配線要素グループｇiと配線要素グループｇjについて、ｇiの下部側とｇjの上部側の接続状態が共に「接続済」であり、ｇiの下部側とｇjの上部側が接続済であるか、あるいはｇiの下部側とｇjの上部側の接続状態が共に「未接続」であり、ｇiの下部側とｇjの上部側が強接続可能である場合、「ｇiの下部側とｇjの上部側は適合する」という。
【０１５５】
〈等価配線要素グループの接続済ネットワークと同型の定義〉
◇等価配線要素グループの定義
［定義１５］
等価配線要素グループの集合Ｇが以下の条件を満たすとき、Ｇを「等価配線要素グループの接続済ネットワーク」といい、Ｎで表す。
（ａ）Ｇに含まれる任意の異なる等価配線要素グループｇi，ｇjに関して、ｇiとｇjが接続済経路によって到達可能である。
（ｂ）Ｇに含まれる任意の等価配線要素グループｇiとＧに含まれない任意の等価配線要素グループｇkに関して、ｇiとｇkが接続済で到達可能ではない。
【０１５６】
◇等価配線要素グループの接続済ネットワークの同型の定義
［定義１６］
等価配線要素グループの接続済ネットワークＮ(p)，Ｎ(q)に関して｜Ｎ(p)｜≧｜Ｎ(q)｜とする。Ｎ(p)に含まれる等価配線要素グループとＮ(q)に含まれる等価配線要素グループを１対１に対応付ける方法を「Ｎ(p)からＮ(q)への対応付け」といい、σで表す。またσによってＮ(p)からＮ(q)へ対応付けたとき、Ｎ(p)の等価配線要素グループｇi(p)に対応付けられるＮ(q)の等価配線要素グループをｇσ(i)(q)で表す。
【０１５７】
但し、｜Ｎ(p)｜＞｜Ｎ(q)｜の場合、｜Ｎ(p)｜−｜Ｎ(q)｜個のダミーの等価配線要素グループをＮ(q)に追加して対応付けるものとする。なお、ダミーの等価配線要素グループは、どの設備の一部でもないとする。
【０１５８】
図２０参照。
【０１５９】
［定義１７］
等価配線要素グループの接続済ネットワークＮ(p)，Ｎ(q)に関して｜Ｎ(p)｜≧｜Ｎ(q)｜とする。Ｎ(p)に含まれる任意の等価配線要素グループｇi(p)に関して以下の条件を満たすようなＮ(p)からＮ(q)への対応付けσが存在するとき、「Ｎ(p)とＮ(q)はσによって同型である」といい、Ｎ(p)≒σＮ(q)で表す。
（Ａ）ｇi(p)とｇσ(i)(q)は同じ配線設備の一部である。
（Ｂ）ｇi(p)とｇσ(i)(q)の下部側の接続状態が一致する
（Ｃ）ｇi(p)とｇσ(i)(q)の下部側の接続状態が一致する。
（Ｄ）ｇi(p)の下部側について
・接続状態が「接続済」の場合
ｇi(p)とＮ(p)に含まれる任意の等価配線要素グループｇj(p)に関して、ｇi(p)の下部側とｇj(p)の上部側が接続済ならばｇσ(i)(q)の下部側とｇσ(j)(q)の上部側も接続済であり、その逆も成り立つ。
【０１６０】
・接続状態が「未接続」の場合
ｇi(p)の下部側と上部側で強接続可能な配線要素グループの集合と、ｇσ(i)(q)の下部側と上部側で強接続可能な配線要素グループの集合が一致する。
（Ｅ）ｇi(p)の上部側について
・接続状態が「接続済」の場合
ｇi(p)とＮ(p)に含まれる任意の等価配線要素グループｇj(p)に関して、ｇi(p)の上部側とｇj(q)の下部側が接続済ならばｇσ(i)(q)の上部側とｇσ(j)(q)の下部側も接続済であり、その逆も成り立つ。
【０１６１】
・接続状態が「未接続」の場合
ｇi(p)の上部側と下部側で強接続可能な配線要素グループの集合と、ｇσ(i)(q)の上部側と下部側で強接続可能な配線要素グループの集合が一致する。
【０１６２】
図２１参照。
【０１６３】
《記号の説明》
以下の《配線要素の分類方法》および《配線要素グループの更新方法》で使用する記号について、ここで説明する。
【０１６４】
・Ａ←Ｂ：ＡをＢで更新する。
【０１６５】
・Ａ∪Ｂ：ＡとＢの和集合。つまり、ＡまたはＢに含まれるものの集合。
【０１６６】
・Ａ＼Ｂ：ＡとＢの差集合。つまりＡに含まれＢに含まれないものの集合。
【０１６７】
《配線要素の分類基準と接続条件に関する組合せ可否判断基準》
配線要素を配線要素グループに分類する際には、全ての配線要素を等価配線要素グループに分類する。但し等価配線要素グループへの分類は１通りではない（図２２参照）。例えば全ての配線要素グループが配線要素を１個しか含まないように分類しても、これらの配線要素グループは等価配線要素グループになる。分類後に配線要素グループの組合せの数を少なくすることが、配線要素を分類する目的であるから、等価配線要素グループの数がなるべく少なくなるように分類する。
【０１６８】
また、配線要素グループの組合せを求める際には、配線要素グループ間の適合性に基づいて組合せ可否の判定を行う。
【０１６９】
配線要素グループ間の適合性に基づいて組合せ可否を判定し、配線要素グループの組合せを求めることで、健全性が保証される。また、等価配線要素グループとなるように配線要素を分類した上で、配線要素グループ間の適合性に基づいて組合せ可否を判定し、配線要素グループの組合せを求めることで、完全性が保証される。
【０１７０】
《配線要素グループの分類方法》
［ＳＴＥＰ１］
全ての配線要素を局所的等価配線要素グループに分類する。各局所的等価配線要素グループｇに対して、局所的等価配線要素グループの集合Ｇ*L（ｇ），Ｇ*U（ｇ）を用意し、空集合で初期化する。また更新が必要な局所的等価配線要素グループの集合Ｇupdateを用意し、空集合で初期化する。
【０１７１】
［ＳＴＥＰ２］
各局所的等価配線要素グループｇiに対して以下の操作を行う。
（１）Ｇ*L（ｇi）を暫定的に求める。
【０１７２】
・ｇiの下部側の接続状態が「接続済」の場合
ｇiを含むケーブルの下部側に設置されている配線設備の一部であり、上部側の接続状態が「接続済」の各局所的等価配線要素グループｇjに対して、Ｇ*L（ｇi）←Ｇ*L（ｇi）∪｛ｇj｝，Ｇ*U（ｇj）←Ｇ*U（ｇj）∪｛ｇi｝とする。またｇi，ｇjをＧupdateに追加する。
【０１７３】
・ｇiの下部側の接続状態が「未接続」の場合
ｇiを含むケーブルの下部側に設置されている配線設備の一部であり、上部側の接続状態が「未接続」の各局所的等価配線要素グループｇjに対して、Ｇ*L（ｇi）←Ｇ*L（ｇi）∪｛ｇj｝，Ｇ*U（ｇj）←Ｇ*U（ｇj）∪｛ｇi｝とする。
（２）Ｇ*U（ｇi）を暫定的に求める。
【０１７４】
・ｇiの上部側の接続状態が「接続済」の場合
ｇiを含むケーブルの上部側に設置されている配線設備の一部であり、下部側の接続状態が「接続済」の各局所的等価配線要素グループｇjに対して、Ｇ*U（ｇi）←Ｇ*U（ｇi）∪｛ｇj｝，Ｇ*L（ｇj）←Ｇ*L（ｇj）∪｛ｇi｝とする。またｇi，ｇjをＧupdateに追加する。
【０１７５】
・ｇiの上部側の接続状態が「未接続」の場合
ｇiを含むケーブルの上部側に設置されている配線設備の一部であり、下部側の接続状態が「未接続」の各局所的等価配線要素グループｇjに対して、Ｇ*U（ｇi）←Ｇ*U（ｇi）∪｛ｇj｝，Ｇ*L（ｇj）←Ｇ*L（ｇj）∪｛ｇi｝とする。
【０１７６】
［ＳＴＥＰ３］
Ｇupdateが空集合になるまでＧupdateに含まれる各局所的等価配線要素グループｇiに対して以下の操作を行い、ｇiを等価配線要素グループにする。
【０１７７】
・ｇiの下部側の接続状態が「接続済」、上部側の接続状態が「接続済」のとき
（１）Ｇupdate←Ｇupdate＼｛ｇi｝とする。
【０１７８】
（２）ｇiに含まれる各配線要素ｅiに対して、局所的等価配線要素グループの集合ＧfL（ｅi），ＧfU（ｅi）を用意し、空集合で初期化する。
【０１７９】
（３）ＧfL（ｅi），ＧfU（ｅi）を以下のようにして求める。
【０１８０】
Ｇ*L（ｇi）に含まれる各局所的等価配線要素グループｇjに対して、ｅiの下部側とｇjの上部側が接続済であれば、ＧfL（ｅi）←ＧfL（ｅi）∪｛ｇj｝とする。
【０１８１】
Ｇ*U（ｇi）に含まれる各局所的等価配線要素グループｇjに対して、ｅiの上部側とｇjの下部側が接続済であれば、ＧfU（ｅi）←ＧfU（ｅi）∪｛ｇj｝とする。
【０１８２】
（４）ｇiに含まれる全ての配線要素を等価配線要素グループに分類する。すなわち、ＧfL（ｅi）とＧfU（ｅi）が一致する配線要素同士を同じ等価配線要素グループに分類する。
【０１８３】
−ｇiに含まれる全ての配線要素が同じ等価配線要素グループに分類された場合、つまりｇiが等価配線要素グループであった場合
Ｇ*L（ｇi）とＧ*U（ｇi）に含まれる局所的等価配線要素グループに対して何もしない。
【０１８４】
−ｇiに含まれる全ての配線要素が複数の等価配線要素グループに分類された場合、つまりｇiが等価配線要素グループではなかった場合
これらの等価配線要素グループをｇi,kとする。またｇi,kに分類された任意の配線要素ｅi,kを使ってＧ*L（ｇi,k）←ＧfL（ｅi,k），Ｇ*U（ｇi,k）←ＧfU（ｅi,k）とする。
【０１８５】
（１）Ｇ*L（ｇi）に含まれる全ての局所的等価配線要素グループｇjに対して以下の操作を行う。
【０１８６】
Ｇ*U（ｇj）←Ｇ*U（ｇj）＼｛ｇi｝∪｛ｇi,k｜ｇj∈Ｇ*L（ｇi,k）｝
Ｇupdate←Ｇupdate∪｛ｇj｝
（２）Ｇ*U（ｇi）に含まれる全ての局所的等価配線要素グループｇｊに対して以下の操作を行う。
【０１８７】
Ｇ*L（ｇj）←Ｇ*L（ｇj）＼｛ｇi｝∪｛ｇi,k｜ｇj∈Ｇ*U（ｇi,k）｝
Ｇupdate←Ｇupdate∪｛ｇj｝
（３）ｇiを消去する。
【０１８８】
・ｇiの下部側の接続状態が「接続済」、上部側の接続状態が「未接続」のとき
（１）Ｇupdate←Ｇupdate＼｛ｇi｝とする。
【０１８９】
（２）ｇiに含まれる各配線要素ｅiに対して、局所的等価配線要素グループの集合ＧfL（ｅi）を用意し、空集合で初期化する。
【０１９０】
（３）ＧfL（ｅi）を以下のようにして求める。
【０１９１】
Ｇ*L（ｇi）に含まれる各局所的等価配線要素グループｇjに対して、ｅiの下部側とｇjの上部側が接続済であれば、ＧfL（ｅi）←ＧfL（ｅi）∪｛ｇj｝とする。
【０１９２】
（４）ｇiに含まれる全ての配線要素を等価配線要素グループに分類する。すなわち、ＧfL（ｅi）が一致する配線要素同士を同じ等価配線要素グループに分類する。
【０１９３】
−ｇiに含まれる全ての配線要素が同じ等価配線要素グループに分類された場合、つまりｇiが等価配線要素グループであった場合
Ｇ*L（ｇi）とＧ*U（ｇi）に含まれる局所的等価配線要素グループに対して何もしない。
【０１９４】
−ｇiに含まれる全ての配線要素が複数の等価配線要素グループに分類された場合、つまりｇiが等価配線要素グループではなかった場合
これらの等価配線要素グループをｇi,kとする。またｇi,kに分類された任意の配線要素ｅi,kを使ってＧ*L（ｇi,k）←ＧfL（ｅi,k）とする。さらにＧ*U（ｇi,k）←Ｇ*U（ｇi）とする。
【０１９５】
（１）Ｇ*L（ｇi）に含まれる全ての局所的等価配線要素グループｇjに対して以下の操作を行う。
【０１９６】
Ｇ*U（ｇj）←Ｇ*U（ｇj）＼｛ｇi｝∪｛ｇi,k｜ｇj∈Ｇ*L（ｇi,k）｝
Ｇupdate←Ｇupdate∪｛ｇj｝
（２）Ｇ*U（ｇi）に含まれる全ての局所的等価配線要素グループｇjに対して以下の操作を行う。
【０１９７】
Ｇ*L（ｇj）←Ｇ*L（ｇj）＼｛ｇi｝∪｛ｇi,1，ｇi,2，……，ｇi,k，……｝
（３）ｇiを消去する。
【０１９８】
・ｇiの下部側の接続状態が「未接続」、上部側の接続状態が「接続済」のとき
ｇiの下部側の接続状態が「接続済」、上部側の接続状態が「未接続」のときと上部側、下部側を入れ替えて同様の操作を行う。
【０１９９】
［ＳＴＥＰ４］
全ての等価配線要素グループｇに対して
・ｇに含まれる配線要素
・ｇの下部側の接続状態
・ｇの上部側の接続状態
・ｇの下部側配線要素グループ集合Ｇ*L（ｇ）
・ｇの上部側配線要素グループ集合Ｇ*U（ｇ）
を記録する。
【０２００】
《配線要素グループの組合せ可否判定方法》
等価配線要素グループｇの下部側と等価配線要素グループｇ’の上部側が適合しているとき、そのときに限ってｇの下部側とｇ’の上部側を組合せ可能と判定するが、ｇの下部側とｇ’の上部側の適合性は、適合性の定義に立ち返って調べなくても、Ｇ*L（ｇ）を使って判定できる。同様に、等価配線要素グループｇの上部側とｇ’の下部側が適合しているとき、そのときに限ってｇの上部側とｇ’の下部側を組合せ可能と判定するが、ｇの上部側とｇ’の下部側の適合性は、適合性の定義に立ち返って調べなくても、Ｇ*U（ｇ）を使って判定できる。つまり、以下の方法で組合せ可否を判断する。
【０２０１】
・ｇ’∈Ｇ*L（ｇ）のとき、そのときに限ってｇの下部側とｇ’の上部側は組合せ可能と判定する。
【０２０２】
・ｇ’∈Ｇ*U（ｇ）のとき、そのときに限ってｇの上部側とｇ’の下部側は組合せ可能と判定する。
【０２０３】
《配線要素グループの更新方法》
◇下部側または上部側の接続状態または接続先が変更される配線要素が発生したとき
［ＳＴＥＰ１］
下部側または上部側の接続状態または接続先が変更される配線要素の集合をＥ(q)changeとする。Ｅ(q)changeに含まれる配線要素のどれかと、接続済経路によって到達可能な配線要素を全て求め、それらの配線要素とＥ(q)changeに含まれる配線要素を等価配線要素グループから削除する。削除された配線要素の集合をＥ(q)とする。
【０２０４】
［ＳＴＥＰ２］
配線要素を削除した等価配線要素グループに対して以下の操作を行う。
【０２０５】
・配線要素を１個も持たない等価配線要素グループが発生しない場合
何も行わない。
【０２０６】
・配線要素を１個も持たない等価配線要素グループｇiが発生する場合
（１）ｇiの下部側と上部側で接続済または強接続可能な等価配線要素グループに対して変更を行う。
【０２０７】
−ｇiの下部側の接続状態が「接続済」の場合
何も行わない。
【０２０８】
−ｇiの下部側の接続状態が「未接続」の場合
ｇiからの配線要素の削除前にＧsL（ｇi）＝Ｇ*L（ｇi）に含まれていた各（等価）配線要素グループｇjに対してＧ*U（ｇj）←Ｇ*U（ｇj）＼｛ｇi｝とする。
【０２０９】
（２）ｇiの上部側と下部側で接続済または強接続可能な等価配線要素グループに対して変更を行う。
【０２１０】
−ｇiの上部側の接続状態が「接続済」の場合
何も行わない。
【０２１１】
−ｇiの上部側の接続状態が「未接続」の場合
ｇiからの配線要素の削除前にＧsU（ｇi）＝Ｇ*U（ｇi）に含まれていた各（等価）配線要素グループｇjに対してＧ*L（ｇj）←Ｇ*L（ｇj）＼｛ｇi｝とする。
【０２１２】
（３）ｇiを消去する。
【０２１３】
このとき消去されずに残った等価配線要素グループの集合をＧ(p)とする。
【０２１４】
［ＳＴＥＰ３］
Ｅ(q)changeに含まれる全ての配線要素について下部側または上部側の接続状態または接続先を変更する。
【０２１５】
［ＳＴＥＰ４］
Ｅ(q)に含まれる配線要素を、《配線要素の分類方法》で述べた手順に準じて等価配線要素グループに分類する。
【０２１６】
（１）Ｅ(q)に含まれる全ての配線要素を局所的等価配線要素グループに分類する。これらの局所的等価配線要素グループの集合をＧ(q)とする。Ｇ(q)に含まれる各局所的等価配線要素グループｇに対して、局所的等価配線要素グループの集合Ｇ*L（ｇ），Ｇ*U（ｇ）を用意し、空集合で初期化する。また更新が必要な局所的等価配線要素グループの集合Ｇupdateを用意し、空集合で初期化する。
【０２１７】
（２）ファイバを配線要素として含む、Ｇ(q)に含まれる各局所的要素グループｇi(q)に対して以下の操作を行う。
【０２１８】
・Ｇ*L（ｇi(q)）を暫定的に求める。
【０２１９】
−ｇi(q)の下部側の接続状態が「接続済」の場合
Ｇ(q)の中から、ｇi(q)を含むケーブルの下部側に設置されている配線設備の一部であり、上部側の接続状態が「接続済」の各局所的等価配線要素グループｇj(q)に対して、Ｇ*L（ｇi(q)）←Ｇ*L（ｇi(q)）∪｛ｇj(q)｝，Ｇ*U（ｇj(q)）←Ｇ*U（ｇj(q)）∪｛ｇi(q)｝とする。またｇi(q)，ｇj(q)をＧupdateに追加する。
【０２２０】
−ｇi(q)の下部側の接続状態が「未接続」の場合
全ての配線要素グループ、つまりＧ(p)∪Ｇ(q)の中から、ｇi(q)を含むケーブルの下部側に設置されている配線設備の一部であり、上部側の接続状態が「未接続」の各局所的等価配線要素グループｇj(q)に対して、Ｇ*L（ｇi(q)）←Ｇ*L（ｇi(q)）∪｛ｇj｝，Ｇ*U（ｇj）←Ｇ*U（ｇj）∪｛ｇi(q)｝とする。
【０２２１】
・Ｇ*U（ｇi(q)）を暫定的に求める。
【０２２２】
−ｇi(q)の上部側の接続状態が「接続済」の場合
Ｇ(q)の中から、ｇi(q)を含むケーブルの上部側に設置されている配線設備の一部であり、下部側の接続状態が「接続済」の各局所的等価配線要素グループｇj(q)に対して、Ｇ*U（ｇi(q)）←Ｇ*U（ｇi(q)）∪｛ｇj(q)｝，Ｇ*L（ｇj(q)）←Ｇ*L（ｇj(q)）∪｛ｇi(q)｝とする。またｇi(q)，ｇj(q)をＧupdateに追加する。
【０２２３】
−ｇi(q)の上部側の接続状態が「未接続」の場合
全ての配線要素グループ、つまりＧ(p)∪Ｇ(q)の中から、ｇi(q)を含むケーブルの上部側に設置されている配線設備の一部であり、下部側の接続状態が「未接続」の各局所的等価配線要素グループｇj(q)に対して、Ｇ*U（ｇi(q)）←Ｇ*U（ｇi(q)）∪｛ｇj｝，Ｇ*L（ｇj）←Ｇ*L（ｇj）∪｛ｇi(q)｝とする。
【０２２４】
（３）《配線要素の分類方法》で述べた方法の［ＳＴＥＰ３］を行う。
【０２２５】
Ｅ(q)に含まれる配線要素を等価配線要素グループに分類した結果得られる等価配線要素グループの集合を改めてＧ(q)とする。またＥ(q)changeに含まれる配線要素を含む等価配線要素グループの集合をＧ(q)changeとする。
【０２２６】
［ＳＴＥＰ５］
Ｇ(q)changeが空集合になるまでＧ(q)changeに含まれる各等価配線要素グループｇ(q)に対して以下の操作を行う。
【０２２７】
（１）ｇ(q)を含む等価配線要素グループの接続済ネットワークＮ(q)を求める。
【０２２８】
（２）Ｇ(q)change←Ｇ(q)change＼（Ｇ(q)change∩Ｎ(q)）とする。
【０２２９】
（３）Ｇ(p)に含まれ、またｇ(q)と同じ配線設備に含まれ、さらにｇ(q)と下部側と上部側の接続状態が同じ各等価配線要素グループｇ(p)に対して、ｇ(p)を含む等価配線要素グループの接続済ネットワークＮ(p)を求め、Ｎ(p)とＮ(q)が同型であるかどうかを判定する。
【０２３０】
・Ｎ(p)≒σＮ(q)の場合
（１）Ｎ(p)に含まれる各等価配線要素グループｇi(p)に対して、ｇi(p)←ｇi(p)∪ｇσ(i)(q)とする。
【０２３１】
（２）Ｇ(q)←Ｇ(q)＼Ｎ(q)とする。
【０２３２】
（３）Ｎ(q)に含まれる各等価配線要素グループｇi(q)に対して、以下の操作を行う。
【０２３３】
（１）ｇi(q)の下部側と上部側で接続済または強接続可能な等価配線要素グループに対して変更を行う。
【０２３４】
−ｇi(q)の下部側の接続状態が「接続済」の場合
何も行わない。
【０２３５】
−ｇi(q)の下部側の接続状態が「未接続」の場合
ＧL(s)（ｇi(q)）に含まれる各（等価）配線要素グループｇjに対してＧU(*)（ｇj）←ＧU(*)（ｇj）＼｛ｇi(q)｝とする。
【０２３６】
（２）ｇi(q)の上部側と下部側で接続済または強接続可能な等価配線要素グループに対して変更を行う。
【０２３７】
−ｇi(q)の上部側の接続状態が「接続済」の場合
何も行わない。
【０２３８】
−ｇi(q)の上部側の接続状態が「未接続」の場合
ＧU(s)（ｇi(q)）に含まれる各（等価）配線要素グループｇjに対してＧL(*)（ｇj）←ＧL(*)（ｇj）＼｛ｇi(q)｝とする。
【０２３９】
（３）ｇi(q)を消去する。
【０２４０】
・Ｎ(p)≠Ｎ(q)の場合
何も行わない。
【０２４１】
［ＳＴＥＰ６］
Ｇ(q)にはＧ(p)に含まれる等価配線要素グループと合成されなかった等価配線要素グループが残っている。Ｇ(p)←Ｇ(p)∪Ｇ(q)，Ｇ(q)←｛｝として、分離して考えていた等価配線要素グループの集合を１個にまとめる。
【０２４２】
☆補足
・［ＳＴＥＰ４］が完了した時点で全ての配線要素は等価配線要素グループに分類されているため、健全性と完全性を満たす。従って［ＳＴＥＰ５］以降を実行しなくても選定条件を満たす等価配線要素グループの組合せを求める上では問題ない。
【０２４３】
しかし、１個の等価配線要素グループにまとめられる配線要素が複数の等価配線要素グループに分割されている可能性がある。
【０２４４】
例えば、ｇiに含まれる未接続の配線要素ｅiの下部側を他の配線要素ｅjの上部側と接続すると、ｅiはｇiから削除される。その後、ｅiの下部側とｅjの上部側の接続を解除して元の状態に戻しても、［ＳＴＥＰ４］までの処理ではｅiはｇiに含まれないままである。
【０２４５】
最小性の観点から、これらの等価配線要素グループを合成して１個にするため、［ＳＴＥＰ５］を実行する。
【０２４６】
・Ｎ(p)≒σＮ(q)であるかどうかの判定は、グラフ構造の同型判定問題であり、一般にはＮＰ完全である。しかし等価配線要素グループの接続済ネットワークはそれ程大きくない。また等価配線要素グループの接続済ネットワークは２個の木構造をそれぞれのルートでつないだものとなるため、木構造の同型性判定方法（前述の公知文献参照）により容易に計算可能である。
【０２４７】
・等価配線要素グループの更新を行う際には、少しでも処理時間を短くするため、必要な部分のみデータベースから配線要素および配線要素グループに関するデータを読み込んで処理を行う。
【０２４８】
◇下部側と上部側の接続状態が「未接続」の配線要素を消去するとき
［ＳＴＥＰ１］
消去される配線要素全てを等価配線要素グループから消去する。
【０２４９】
［ＳＴＥＰ２］
配線要素を削除した等価配線要素グループに対して以下の操作を行う。
【０２５０】
・配線要素を１個も持たない等価配線要素グループが発生しない場合
何も行わない。
【０２５１】
・配線要素を１個も持たない等価配線要素グループｇiが発生する場合
（１）ｇiの下部側の接続状態が「未接続」なので消去された配線要素の削除前にＧsL（ｇi）＝Ｇ*L（ｇi）に含まれていた各（等価）配線要素グループｇjに対してＧ*U（ｇj）←Ｇ*U（ｇj）＼｛ｇi｝とする。
【０２５２】
（２）ｇiの上部側の接続状態が「未接続」なので消去された配線要素の削除前にＧsU（ｇi）＝Ｇ*U（ｇi）に含まれていた各（等価）配線要素グループｇjに対してＧ*L（ｇj）←Ｇ*L（ｇj）＼｛ｇi｝とする。
【０２５３】
（３）ｇiを消去する。
【０２５４】
◇下部側または上部側の接続状態が「接続済」の配線要素を消去するとき
［ＳＴＥＰ１］
消去される、下部側または上部側の接続状態が「接続済」の配線要素に対して、下部側または上部側の接続状態または接続先が変更される配線要素が発生したときの手順に従って下部側と上部側の接続状態を「未接続」に変更する。
【０２５５】
［ＳＴＥＰ２］
下部側と上部側の接続状態が「未接続」の配線要素を消去するときの手順に従って配線要素を消去する。
【０２５６】
◇配線要素を追加するとき
［ＳＴＥＰ１］
追加される配線要素の集合をＥ(q)changeとする。配線要素の追加後、他の配線要素と接続する場合には、Ｅ(q)changeに含まれる配線要素のどれかと、接続済経路によって到達可能になる配線要素を全て求め、それらの配線要素を等価配線要素グループから削除する。追加される配線要素と削除された配線要素の集合をＥ(q)とする。
【０２５７】
［ＳＴＥＰ２］
下部側または上部側の接続状態または接続先が変更される配線要素が発生したときの手順の［ＳＴＥＰ２］から［ＳＴＥＰ６］を実行する。
【図面の簡単な説明】
【０２５８】
【図１】配線要素とその組合せによる経路の例を示す説明図
【図２】対象内の経路および対象外の経路の例を示す説明図
【図３】接続条件と特性条件を満たす配線要素の似た組合せの例を示す説明図
【図４】条件の与え方による組合せの数の違いの例を示す説明図
【図５】配線要素グループに対する組合せの探索が健全でない例を示す説明図
【図６】配線要素グループに対する組合せの探索が完全でない例を示す説明図
【図７】本発明における初期化フェーズ、選定フェーズおよび更新フェーズの関係を示す説明図
【図８】本発明方法を実施する装置の概要を示すハードウェア構成図
【図９】本発明の配線要素の配線要素グループへの分類方法を示すフローチャート
【図１０】等価配線要素グループに分割する際の処理の様子を示す説明図
【図１１】等価配線要素グループへの分類過程の一例を示す説明図
【図１２】本発明の経路探索方法を示すフローチャート
【図１３】本発明の配線要素グループの更新方法を示すフローチャート
【図１４】配線要素グループの更新過程の一例を示す説明図
【図１５】本発明装置の実施の形態の一例を示す構成図
【図１６】接続済の配線要素と配線要素グループの関係を示す説明図
【図１７】強接続可能な配線要素と配線要素グループの関係を示す説明図
【図１８】接続済の配線要素グループの関係を示す説明図
【図１９】強接続可能な配線要素グループの関係を示す説明図
【図２０】等価配線要素グループの接続済ネットワークの対応付けを示す説明図
【図２１】等価配線要素グループの接続済ネットワークの同型の定義を示す説明図
【図２２】等価配線要素グループへの分類結果の多様性を示す説明図
【符号の説明】
【０２５９】
１：入力部、２：出力部、３：配線要素データベース、４：配線要素グループデータベース、５：コンピュータ、６：更新部、７：選定部、６１：配線要素グループ管理部、６２：配線要素分類部、６３：配線要素データベース更新部、６４：等価配線要素グループの接続済ネットワーク比較部、７１：選定条件保持部、７２：組合せ探索部、７３：組合せ対象データロード部、７４：配線要素グループ用組合せ可否判定部、７５：配線要素用組合せ可否判定部。
【図１】
0004737538.tif 000002
【図２】
0004737538.tif 000003
【図３】
0004737538.tif 000004
【図４】
0004737538.tif 000005
【図５】
0004737538.tif 000006
【図６】
0004737538.tif 000007
【図７】
0004737538.tif 000008
【図８】
0004737538.tif 000009
【図９】
0004737538.tif 000010
【図１０】
0004737538.tif 000011
【図１１】
0004737538.tif 000012
【図１２】
0004737538.tif 000013
【図１３】
0004737538.tif 000014
【図１４】
0004737538.tif 000015
【図１５】
0004737538.tif 000016
【図１６】
0004737538.tif 000017
【図１７】
0004737538.tif 000018
【図１８】
0004737538.tif 000019
【図１９】
0004737538.tif 000020
【図２０】
0004737538.tif 000021
【図２１】
0004737538.tif 000022
【図２２】
0004737538.tif 000023