JP2982017B2 - 自動配線処理方法 - Google Patents

Description

【発明の詳細な説明】 ＜産業上の利用分野＞ 本発明は、計算機を援用したプリント基板設計システ
ムにおける自動配線処理方法の改善に関するものであ
る。

＜従来の技術＞ 従来より計算機を援用してプリント基板の配線等を自
動的に行なうプリント基板設計システムがある。

＜発明が解決しようとする課題＞ この種のプリント基板設計システムにおいて用いられ
る自動配線アルゴリズムにはさまざまなものがあるが、
そのいずれもが部品を固定した上で、すなわち配置され
た部品位置は配線処理においては決して乗り越えられな
い障害物として（絶対不可侵の障害物として）扱われ、
部品を乗り越える配線とならないような経路を探索し、
遠回りの配線を選択する配線手法となっている。例え
ば、第６図（ａ）に示すように点Ａと点Ｂを結線する場
合、わずかな変更（部品の移動）をすれば同図（ｂ）に
示すように容易にＡ−Ｂ間を配線できるような場合で
も、部品１および部品２の位置を固定としているために
経路Ｐで示すような遠回りの経路を選択せざるを得ない
という問題があった。

専門家による手動配線設形においては、必要ならば適
宜部品の位置（配置）を変更しつつ配線しており、同図
（ｂ）のように部品の配置を変えＡ−Ｂ間を最短距離で
容易に配線することができる。このような配線手法が自
動配線システムの専門家に及ばない点の一つとなってい
る。

本発明の目的は、このような点に鑑みてなされたもの
で、配線処理の際、必要ならば部品配置の変更を考慮し
ながら配線し、しかもこのような処理が大幅な処理時間
の増大を招くことのないような自動配線処理方法を提供
することにある。

＜課題を解決するための手段＞ 第１図は本発明の自動配線処理方法の原理フローであ
り、次の手順により経路を求める。

配置された部品をペナルティを持った障害物として扱
い、すべての可能な経路を探索する。

探索された経路について経路の長さとペナルティ値の
積で定義されるコストの値が最も低い経路を選択し、そ
の経路が既配置部品を乗り越える場合には乗り越えがな
くなるように当該部品位置を移動する。

＜作用＞ 従来は配置された部品は決して乗り越えられない障害
物として扱われていたが、本発明ではこれをある定めら
れたペナルティを払えば乗り越えることが可能なものと
して扱う。

配線に際して、配置部品を乗り越える必要がなければ
通常の配線処理方法により配線を行うが、乗り越えなけ
ればひどく遠回りをするような配線の場合には遠回りの
度合とペナルティ値との関係に従い適宜乗り越える配線
処理を行なう。

次に、乗り越える配線に対しては、乗り越え部分（経
路と配置された部品の重複部分）が解消されるように当
該部品を移動する。

＜実施例＞ 以下図面を参照して本発明を詳細に説明する。第２図
は本発明の自動配線処理方法を実現するためのシステム
の構成を示すブロック構成図である。図において、１は
プリント基板上のすべての図形情報、すなち配置された
部品や既配線経路等のデータが格納された記憶装置であ
る。２は記憶装置１から情報を読み出す図形データ読み
出し処理部であり、配置された部品に対しては適当なペ
ナルティを付加する。３は最適経路探索処理部であり、
探索された可能な経路のうち、最もコストの低い経路を
見いだす処理を行なう。経路のコストは、経路の長さと
ペナルティ値の積で定義される値である。また、前記図
形データ読み出し処理部２で付加するペナルティ値は、
通常の場合は1.0、配置された部品についはこれよりも
大きい値に設定する。

上記経路の探索は例えば迷路法等により行なう。な
お、記憶装置１から図形情報の読み出しが必要になった
場合には、図形データ読み出し処理部２を利用する。

４は部品の移動による乗り越え解消処理部であり、最
適経路探索処理部３で求められた経路が配置された部品
と重複しているときは、部品を移動してこれを解決する
処理を行なう。なお、経路が既に配置された部品と重複
しているかどうかの判断を行なう際に必要となるデータ
は記憶装置１から直接読み出す。

このような構成における自動配線処理方法に係る動作
を第３図ないし第５図を参照して次に説明する。なお、
第３図および第４図は動作フロー、第５図は結線の様子
を説明するための説明図である。以下第５図に示すよう
に点ＡとＢを結線する場合を例をとって説明する。な
お、配線経路は幅４（隣接部品あるいは隣接パターンと
の間隔がある基準幅の４倍であること）を必要とするも
のとする。

まず、点ＡとＢの結線に関して、例えば迷路法を利用
してすべての可能な経路を探索する。その結果、第５図
（ｂ）に示すように２つの解、すなわち経路P1とP2が求
められる。

ここで、それぞれのコストを第４図のコスト計算フロ
ーに従って計算する。計算の結果は次の通りになる。

経路P1: （経路の長さが30）×（ペナルティは1.0） ＝30 経路P2: （経路の長さが10）×（ペナルティは初期値の２倍、2.
0）＝20 次に、第３図に示す処理により最もコストの低い経路
を選択し、経路P2の方が選ばれる。

ところで、この解２（経路P2）は配置部品２と交差し
ている（幅が４以下）。そこで、経路P2との重複がなく
なるまで部品２を右に移動する。その結果、第５図
（ｃ）に示すようになり、配線が完了する。

なお、上記実施例では部品のペナルティ値を２倍とし
たが、移動の容易なものには低い値を、移動が困難な部
品には高い値を与えるようにして、移動の難易度を含ん
だ配線を行なうようにすることもできる。例えば上記実
施例でペナルティ値を５とした場合は、配置変更のない
解１（経路P1）が選ばれる。

なお、部品配置の変更処理は、それが必要となって初
めて行なわれるものであり、処理に無駄がない。

また、本発明の方法では従来の処理に比べて部品を移
動する処理が新たに必要となるが、一般に配線問題にお
いては処理時間の大部分は探索処理にあり、それと比較
すれば部品の移動などの図形の変形処理は実行時間上ほ
とんど問題とならない時間である。

＜発明の効果＞ 以上詳細に説明したように、本発明によれば次のよう
な効果がある。

従来は不可能であった部品配置の変更を考慮した配線
が可能となる。

しかも、配置変更に対する優先度を表現することがで
き、見いだされた経路は配置と配線の両方を同時に考慮
した場合の最適の経路となる。

更に、実行速度にも大きな影響を与えない自動配線処
理方法である。

【図面の簡単な説明】

第１図は本発明の自動配線処理方法の原理フロー、第２
図は本発明を実施するためのシステム構成図、第３図お
よび第４図は動作フローを示す図、第５図および第６図
は結線の様子を示す説明図である。 １……記憶装置、２……図形データ読み出し処理部、３
……最適経路探索処理部、４……乗り越え解消処理部。

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】プリント基板の自動配線を行う自動配線処
   理方法であって、 プリント基板に配置された部品をペナルティを持った障
   害物として扱い、すべての可能な配線経路を探索する工
   程と、 前記探索された配線経路から経路の長さと前記ペナルテ
   ィの値の積で定義されるコストの値が最も低い経路を選
   択し、その経路が既配置の障害物を乗り越える場合には
   乗り越えがなくなるように当該障害物の位置を移動する
   工程 からなることを特徴とする自動配線処理方法。