JPH03231372A - 自動配線方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は自動配線方法に関し、特に電気系統のＣＡＤシ
ステムにおいて、プリント基板やハイブリッドＩＣ，Ｌ
ＳＩなどの配線レイアウトを求める自動配線方法に関す
る。

〔従来の技術〕

自動配線方法とは、プリント基板上の部品端子や外部接
続端子間の接続経路を、種々の与えられた条件のもとて
コンピュータにより探索するものであり、従来から種々
の手法が提案されている。

しかしながら、現状ではすべての必要な配線の経路を自
動配線で決定することは困難であり、一般には、自動配
線で残された未配線ネットを人手で探索し、既配線のい
くつかを取り外して再配線することが行われている。

従来から知られている最も基本的な自動配線方法に、最
短距離の経路を探索することを最優先させたメイズルー
タ（迷路法）がある。この手法は配線する領域を格子状
に分割し、その格子に各種の重みを加えて最適経路を決
定するものである。

そのアルゴリズムは、始点の格子から波を立て、それが
周囲に広がっていくように周りの格子の重みを決定しな
がら、終点の格子までのすべての経路をしらみつぶしに
探索していくものである。この手法は、経路があれば必
ず最短経路が発見できるが、探索に時間がかかりコンピ
ュータのメモリを多く必要とする。

これに対して、メイズルータのように総当たり的な試行
でなく、簡単な経路だけの試行を行う発見的手法も多く
提案されている。その代表的なものは線分探索法であり
、接続すべき両端からＸ。

Ｙ方向に順次線分を発生させ、始点からの線分と終点か
らの線分とが交わったとき、その交点から逆方向にたど
って経路を決定するもので、Ｘ方向とＹ方向の配線は、
スルーホールを介してプリント基板の表裏に配線される
。

〔発明が解決しようとする課題〕

上述した従来のメイズルータの手法は、配線経路があれ
ば必ずその経路を発見できるが、記憶容量と処理時間と
を多く必要とする欠点がある。更に、力ずくで経路を探
索するために配線パターンが不自然になりがちで、後続
の配線修正作業がかえってやりにくくなる局面が多い。

一方、発見的手法の線分探索法は、単純な線分を中心と
した探索で配線の端点情報の記憶のみでよく、記憶容量
と処理時間が少なくてすむ。しかし、単純な線分を基調
として経路探索を実行するため、実際の自動配線場面で
は配線経路を発見できない状況が多く、かなり整然とし
たビン配列の場合に限り有効であるという欠点がある。

本発明の目的は、従来の線分探索法と比較して経路発見
率が高く、メモリ使用が効率的で大きなメモリ容量を必
要としない自動配線方法を提供することである。

〔課題を解決するための手段〕

本発明の自動配線方法は、ターゲット点を通るターゲッ
トラインに向かってソース点から垂直に直線探索を行い
障害物を発見すると障害到達ポイントの座標を算出して
二分木ノードに記録する第１の手順と、前記障害到達ポ
イントから左または右に前記障害物を迂回するルートを
探索して迂回ポイントを検出し迂回実行済みを表示する
左または右の方向フラグを前記障害物に立てる第２の手
順と、前記迂回ポイントから前記ターゲットラインに向
かって垂直に直線探索を行い次の障害物または前記ター
ゲットラインに到達したとき対象到達ポイントの座標を
算出する第３の手順と、この対象到達ポイントに新たな
二分木ノードを追加し前記対象到達ポイントの座標およ
び既存の二分木ノードとの関係を記録する第４の手順と
、前記迂回ポイントを検出する過程で新たな障害に到達
した場合に既に作成された二分木ノードのデータをバッ
クトレースしてツリー構造を変更する第５の手順と、前
記対象到達ポイントを出発点として前記第２〜第５の手
順をすべての障害物の迂回探索を終了するまで再帰的に
繰り返し実行する第６の手順と、すべての障害物の迂回
探索を終了した場合ツリーのバックトレースにより最適
な経路を選択する第７の手順とを備えて構成されている
。

〔実施例〕

次に、本発明の実施例について、図面を参照して詳細に
説明する。

第１図は本発明の一実施例のＳＰＤ形式で示したフロー
チャートである。

第１図に示した自動配線方法は、ソース点からターゲッ
ト点を通るターゲットラインへの垂直線を探索し最初の
障害物を検出して二分木ノードを設定する第１の手順Ｓ
１と、障害物を迂回して迂回ポイントを算出する第２の
手順Ｓ２と、迂回ポイントからターゲットラインへの垂
直線を探索し次の障害物を検出する第３の手順Ｓ３と、
新しいノードを現存の二分木ノードに追加する第４の手
順Ｓ４と、迂回の過程で障害物を発見した場合にバック
トレースにてツリー構造を変更する第５の手順Ｓ５と、
第２の手順Ｓ２から第５の手順Ｓ５までの各手順を再帰
的に繰り返す第６の手順Ｓ６と、バックトレースにより
最適経路を決定する第７の手順Ｓ７とを含んで構成され
ている。

第２図は本実施例の動作を説明するためのプリント基板
の一例のレイアウト図、第３図は本実施例により横築さ
れる二分木ノードのデータ構造図である。以下に第２図
および第３図を参照しながら第１図に従ってその動作を
詳細に説明する。

第２図において、ソース点１からターゲット点２を通る
ターゲットライン３に向かう垂直線に沿い探索を行う。

この垂直線上で障害物４を検出すると、この障害到達ポ
イント５の座標ｘ２．ｙ、を算出し、これを第３図に示
す二分木ノード１５の障害到達ポイント座標２０に記録
する（Ｓｌ）。

ここで、障害物を迂回探索する再帰呼び出しメインルー
チンＳ６を呼び出して迂回探索に入る。

まず、障害物４の左側迂回探索を行い左側迂回ポイント
６の座標を算出し、その値を一時記憶すると同時に、障
害物４の情報に左側迂回を実施したことを表す方向フラ
グを追記する（Ｓ２）。次に、この左側迂回ポイント６
を新しいソース点としてターゲットライン３への垂直線
を探索し、次の障害物７を検出すると障害到達ポイント
８の座標Ｘ８．Ｙ８を算出する（Ｓ３）。ここで、ツリ
ー構造に新しい二分木ノード１６を追加し、障害到達ポ
イント８の座標Ｘ８．Ｙ８を二分木ノード１６に記録す
ると共に、新しい二分木ノード１６と既存の二分木ノー
ド１５との間を関係付けるバックトレースポインタ２３
．左迂回ポインタ２１にそれぞれポインタＮ　１５＋　
Ｎ　１６を記録する（Ｓ４）。

次に、再び再帰呼び出しメインルーチンＳ６が呼び出さ
れ、障害物７の左側迂回ポイント９が検出される（Ｓ２
）。更にターゲットライン３への垂直線の探索が行われ
、ターゲットライン３に到達すると（Ｓ３）、二分木ノ
ード１７が追加されターゲットライン到達ポイント１０
の座標Ｘｌｏ。

ＹｌｏとポインタＮ１６とが記録される（Ｓ４）。更に
ポインタＮ１７が二分木ノード１６に記録されて左側迂
回探索を終了し右側迂回探索に入る。

右側迂回探索は、まず障害到達ポイント８から右側迂回
ポイント１１を検出して障害物７に右側迂回の方向フラ
グを立て、ターゲットライン３への垂直線を探索する。

ターゲットライン３に到達すると、二分木ノード１８が
作成され、ターゲットライン到達ポイント１２の座標ｘ
ｔ２．ｙｌ□と各ポインタＮ、６．Ｎ、、とがそれぞれ
記録される。

次に、障害到達ポイント５から障害物４の右側迂回探索
を実行し、右側迂回ポイント１３を算出して垂直探索を
行い、障害物７を検出すると二分木ノード１９が作成さ
れ、障害到達ポイント１４の座標Ｘ１４．Ｙ１４とポイ
ンタＮ１５が記録され、二分木ノード１５の右迂回ポイ
ンタ２２にはポインタＮ１９が記録される。しかし、障
害物７には既に左右の方向フラグが立っているので、こ
れ以上の探索は必要ないと判断され、二分木ノード１つ
にはポインタＮ　１７．　Ｎ　１ｇが記録され、二分木
ノード１７．１８にはポインタＮ１９が追加されすべて
の迂回探索を終了する。このように迂回方向フラグを使
用することで、無駄な多重探索を回避することが可能で
ある。

すべての障害物に対する左右の迂回探索を終了すると、
バックトレースにより最適経路を選択決定する（Ｓ７）
。

なお、第２図には示されていないが、障害物を迂回して
迂回ポイントを検出する過程で新たな障害物に到達した
場合には、既に作成された二分木ノードの位置を、その
障害物を避けて迂回ポイントが検出できるところまで戻
すようにツリー構造を変更する（Ｓ５）。

二分木のデータ構造には、左側迂回のための左迂回ポイ
ンタ２１と、右側迂回のための右迂回ポインタ２２及び
バックトレースのためのバックトレースポインタ２３が
与えられてツリーを構成している。更に、障害到達ポイ
ント座標２０に各座標値が格納されている。この記憶手
法により、つの二分木ノードで二つの線分を表現するこ
とが可能であるので、通常の約半分のメモリ容量で済み
メモリの使用効率もよくなる。

〔発明の効果〕

以上詳細に説明したように、本発明の自動配線方法は、
直線性の高い探索を実行するのでメイズルータのような
不自然な経路を発生することがなく、障害物の検出に応
じて柔軟に迂回しながら経路探索を実行するので従来の
発見的手法にはみられない高い経路発見率が得られる。

又、経路探索の領域幅を設定してその中に存在する経路
を二分木ノードのデータ構造で網羅するので、最適な経
路決定がしやすく、二分木ノードのデータ構造が一つの
二分木ノートで二つの線分を表現できるので記憶容量を
従来の半分にできる効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例のＳＰＤ形式によるフローチ
ャート、第２図は本発明を適用するレイアウト図、第３
図は本発明が使用する二分木データ構造の例を示す説明
図である。 １・・・・・・ソース点、２・・・・・・ターゲット点
、３・・・・・・ターゲットライン、４，７・・・・・
・障害物、５，８゜１４・・・・・［Ｆ到達ポイント、
６，９・・・用左側迂回ポイント、１０．１２・・・・
・・ターゲットライン到達ポイント、１１．１３・・・
・・・右側迂回ポイント、１５〜１つ・・・・・・二分
木ノード、２ｏ・・・・・・障害到達ポイント座標、２
１・・・・・・左迂回ポインタ、２２・・・・・・右迂
回ポインタ、２３・・−・・・バックトレースポインタ
。

Claims (1)

【特許請求の範囲】
1. 　ターゲット点を通るターゲットラインに向かつてソー
   ス点から垂直に直線探索を行い障害物を発見すると障害
   到達ポイントの座標を算出して二分木ノードに記録する
   第１の手順と、前記障害到達ポイントから左または右に
   前記障害物を迂回するルートを探索して迂回ポイントを
   検出し迂回実行済みを表示する左または右の方向フラグ
   を前記障害物に立てる第２の手順と、前記迂回ポイント
   から前記ターゲットラインに向かって垂直に直線探索を
   行い次の障害物または前記ターゲットラインに到達した
   とき対象到達ポイントの座標を算出する第３の手順と、
   この対象到達ポイントに新たな二分木ノードを追加し前
   記対象到達ポイントの座標および既存の二分木ノードと
   の関係を記録する第４の手順と、前記迂回ポイントを検
   出する過程で新たな障害に到達した場合に既に作成され
   た二分木ノードのデータをバックトレースしてツリー構
   造を変更する第５の手順と、前記対象到達ポイントを出
   発点として前記第２〜第５の手順をすべての障害物の迂
   回探索を終了するまで再帰的に繰り返し実行する第６の
   手順と、すべての障害物の迂回探索を終了した場合ツリ
   ーのバックトレースにより最適な経路を選択する第７の
   手順とを備えたことを特徴とする自動配線方法。