JPH04676A - 最短経路決定方法及び最短経路決定システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、プリント基板、集積回路等の配線パターンを
決定する方法、及び配線パターンを決定するシステムに
係り、特に、信号遅延を配慮した配線パターンを計算機
により自動決定するために用いて好適な最短経路決定方
法、及び最短経路決定システムに関する。

〔従来の技術〕

近年、計算機の高性能化に伴い、それを構成するプリン
ト基板、集積回路等の実装設計においては、配線パター
ンによる信号遅延に対する考慮が重要な問題となり、斜
め４５°方向の配線パターン等を用いた最短配線による
配線設計が不可欠となってきた。

プリント基板等における配線設計自動化技法の中で、斜
め４５°方向の配線パターンを用いた最短経路決定方法
に関する従来技術としては、１９８６年　アイ・イー・
イー・イー　インターナショナル　コンファレンス　オ
ン　コンピュータ・ニーディト　デザイン　プロシーデ
インゲス、第２５０頁から第２５３頁（Ｐｒｏｃｅｅｄ
ｉｎｇｓ　１９８６ＩＥＥＥ　Ｉｎｔｅｒｎａｔｉｏｎ
ａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｐｕｔｅｒ
−Ａｉｄｅｄ　Ｄｅｓｉｇｎ　（Ｉ　ＣＣＡＤ　−８６
）　、　ｐ　ｐ　、　２５０＝２５３）において論じら
れている方法がある。

従来よりプリント基板等における配線設計においては、
配線方向が水平方向、垂直方向の２つの配線層のペア（
これを以下では「ペア層」と記す）を複数積層した層構
成をもつ基板が主に対象とされてきたが、第２図に示す
ように、上記方法においては、配線可能方向を水平方向
、垂直方向、斜め±４５’方向の４方向に拡張し、これ
らのうち斜め方向を含むいずれか２方向を各ペア層に割
当て、かつそれらのペア層のいずれかで斜め４５゜方向
を用いた最短経路による結線を実現できるような基板を
対象とすることができる。そして上記方法による配線経
路決定処理では、このようなプリント基板等を対象とし
て、まず、配線対象区間の始点と終点を結ぶ線分が水平
方向となす角度により最適なペア層を決定し、その後肢
ペア層において始点から終点に至る斜め４５°方向を用
いた最短なる経路の探索を線分探索法、迷路法等により
２層配線として行なうことを基本としている（以下この
方法を「２層配線方法」と呼ぶ）。

しかし、上記２層配線方法による最短経路決定方法では
、配線対象区間に対する配線方向を２方向に限定するも
のであり、所望の最短経路上に配線層のパターン等の経
路探索をするうえでの障害物が存在する場合、決められ
た２つの配線方向を用いることにより、かえって配線パ
ターンに迂回が生じることがある。さらに配線対象区間
の始点と終点を結ぶ線分が水平方向となす角度に対し、
斜め配線層を含んだすべてのペア層が必要であり、従来
の水平、垂直方向配線層のみによるペア層構成に比べ、
膨大な配線層数を要すという問題がある。

一方、上記２層配線方法に対し第３図に示すように、最
近本出願人らは特願昭６３−２６６０５６号の中で、配
線方向の異なる３層以上の配線層の組（以下ではこれを
「層群」と記す）に対する配線経路の決定方法について
検討した。これは、積層された層群のいずれかにおいて
、少なくとも３層以上の複数層を用いて配線対象区間の
始点から終点に至る経路の探索を迷路法により行なうも
ので、少なくとも３方向以上の配線方向を用いることに
よって、最短経路を得ることを目的にしている（以下こ
の方法を「迷路法による多層配線方法」と呼ぶ）。これ
によると、配線可能な複数の経路の中で経路長が最短と
なるものを必ず発見することができるので、配線方向を
３方向以上とすることにより前記２層配線方法によって
生じる可能性のある不必要な配線パターンの迂回が解消
されるという利点がある。さらに、前記２層配線方法に
対し、配線対象区間の始点、終点を結ぶ線分と水平方向
とのなす角度にかかわらず、特定の層群において大量の
配線区間を一括して処理できるので、少ない配線層数で
斜め方向を用いた最短経路決定が可能である。

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

しかし、上記迷路法による多層配線方法は、上記２層配
線方法の問題点を解消するものの、大規模なプリント基
板、集積回路等に対する配慮がされておらず、大量の配
線区間に対し高速に配線経路決定を行えないという問題
があった。

本発明の目的は、前述した従来技術の問題点を解決し、
大規模なプリント基板、集積回路等に対する最短なる配
線経路を高速かつ少ない配線層数で決定し得る方法及び
システムを提供することである。

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

上記目的は、上記迷路法による多層配線方法において、
始点から終点に至る経路の探索を迷路法のかわりに、３
方向以上の配線方向を用いた経路探索可能な拡張された
線分探索法を用い、さらに配線経路の冗長な迂回を高精
度に制御可能な手段を与えることにより達成される。

以下第４図、第１図に示す例を用いて上記説明を補足す
る。第４図、第１図は、少なくとも３層以上の配線層を
同時に用いて決定する配線パターン決定システムにおい
て、上記本発明により少なくとも３方向以上の配線方向
を用いて最短なる配線経路の決定処理を行った１例とし
て、第３図に記した４層の配線層、４方向の配線方向を
用いた配線経路決定処理のようすを示す。

本例ではまず、配線対象となる少なくとも３層以上の複
数の配線層に対し、配線可能な領域を。

それぞれ固有の方向として定義付けられた配線方向に沿
った線分データとして作成しく第４図（Ａ　１））、各
配線層に隣接する配線層への層変更探索可能領域を格子
状データとして作成する（第４図（Ａ２））。

始点Ａから終点Ｂに至る配線経路の探索は、上記線分デ
ータを用いた一次元探索による仮線分の発生、仮線分上
の格子点から上記格子状データを用いた層変更探索を繰
り返すことにより、実行することができる。第４図（Ｂ
ｚ）　、　（Ｂｘ）はこのようすを示す。まず始点Ａか
ら各配線層に対し、上記各配線層に沿った線分データを
用いてレベル１の仮線分を発生する０次に該仮線分上の
複数の格子点位置Ｖｌ、ｖ２より、上記格子状データを
用いて層変更探索を行った後、仮中継穴を発生する。そ
の後肢中継穴から各配線層に対し、上記線分データを用
いてレベル２の仮線分を発生する。以下同様の処理を終
点Ｂに仮線分が到達するまで繰り返す。このように本発
明では、少なくとも３方向以上の配線方向を用いた線分
探索法として実行可能であり、迷路法を用いた経路探索
と比較し格段に高速に処理が可能となる。

しかし上記線分探索法の処理によると、層変更回数最小
すなわち経路の折れ曲がり回数最小なる経路は発見する
ものの、斜め配線を用いたさらに配線長の短い経路を見
逃す可能性がある。そこで本発明ではさらに、より短い
配線経路を発見するために、始点Ａから到達した複数の
格子点に対し、該複数の格子点から終点Ｂへ向かう一次
元探索において、経路が迂回する方向への探索範囲を制
限する。第１図（Ａｘ）　、　　（Ａｘ）はこのための
前処理例を示す。すなわちまず、配線対象となる領域を
終点Ｂを通る４本の直線により分割した部分領域Ｒｘ、
Ｒｚ、・・・Ｒ８を作成しく第１図（Ａｘ））。

各部分領域に対し、４つの配線層における任意の格子点
からの一次元探索の探索方向に、単位格子当りの迂回量
を定義する。この迂回量は基本的に終点Ｂに近づくほど
小さく、遠ざかるほど大きくなるものである。第１図（
Ａ２）はこのうち、部分領域Ｒ１，Ｒ２での各探索方向
に対する単位格子当りの迂回量の例を示している。第１
図（Ｂｌ）。

（Ｂｚ）　、（Ｂａ）は、上記前処理により作成された
各探索方向に対する迂回量をもとに、各配線層において
定義した探索方向への一次元探索の範囲を制限した配線
処理例を示す。経路探索ではまずレベル１の一次元探索
として、始点Ａからの各配線層での仮線分の発生処理を
、上記各探索方向に対する単位格子あたりの迂回量をも
とにして、あらかじめ定義した経路の総迂回量上限値を
超えない範囲で行う（第１図（Ｂ１））。そしてレベル
１探索によって到達した任意の格子点上から、始点Ａか
ら該格子点までの総迂回量を算出し、同様に総迂回量が
上記上限値を越えない範囲で、層変更探索の後レベル２
の一次元探索を同様に行う（第１図（Ｂ２））。以下同
様の処理を繰り返すことにより、この例ではレベル３ま
での探索で、配線経路の迂回が一定の上限値で抑止され
た経路を発見することができる（第１図（Ｂ８））。ま
たこの場合、上記あらかじめ定義した経路の総迂回量上
限値を小さくすることにより、所望の精度で最短経路を
得ることができる。

〔作用〕

上記手段を用いた最短経路決定方法では、少なくとも３
層以上の配線層、少なくとも３方向以上の配線方向を用
いた拡張された線分探索法による経路探索手段を与える
ので、高速にかつ少ない配線層数で配線経路の決定が可
能である。

さらに上記手段を用いた最短経路決定方法では。

線分探索法における終点へ向かう一次元探索による仮線
分の発生範囲に一定の制限を加える手段を与えるので、
高精度に最短経路を決定することができる。

〔実施例〕

（１）第１の実施例 以下１本発明の一実施例を第５図から第９図までの図面
を用いて説明する。

第５図は本発明に係る配線パターン決定システムの構成
を示すブロック図、第６図は該配線パターン決定システ
ム内に設けた最短経路決定処理制御部、５０５の処理手
順を示すフローチャート、第７図、第８図はそれぞれ該
配線パターン決定システム内に設けた線分探索法による
経路探索部５１０において参照更新する配線可能領域デ
ータ格納テーブル５１２、層変更探索可能領域データ格
納テーブル５１３の記述内容および上記処理部５１０に
おいて行う５１２，５１３に対する参照更新内容を示す
図、第９図は上記処理部５１０において作成する仮線分
データ格納テーブル５１５の記述内容を示す図である。

第５図において、コンピュータ５０１は、プリント基板
、集積回路等の配線層の構成、各配線層における配線方
向等を定義した基板情報ファイル５０２、配線対象区間
を格納したネット情報ファイル５０３．配線前のパター
ン情報を格納したパターン情報ファイル５０４から情報
を読み込んだ後、該情報にもとづいて配線経路決定処理
を行い、得られた配線パターンを再度パターン情報ファ
イル５０４に出力するという最短経路決定処理プログラ
ムを有する。また第５図において、コンピュータ５０１
内最短経路決定処理プログラムにおける最短経路決定処
理制御部５０５は、上記基板情報ファイル５０２．ネッ
ト情報ファイル５０３゜パターン情報ファイル５０４か
ら情報を読み込む入力処理部５０６と、各配線層におけ
る配線可能領域を線分データとして定義された配線可能
領域データ格納テーブル５１２に情報を作成する配線可
能領域作成部５０７と、格子状データとして定義された
層変更探索可能領域データ格納テーブル５１３に情報を
作成する層変更探索可能領域作成部５０８と、第１図（
Ａｔ）　＊　　（Ａｚ）　ニ示すごとく部分領域での各
探索方向に対する単位格子あたり迂回量、及び配線対象
区間に対する経路の総迂回量上限値を格納する迂回制御
データ格納テーブル５１４を作成する迂回制御情報作成
部５０９と、上記データ格納テーブル５１２，５１３，
５１４をもとに線分探索法により最短経路の探索を行い
仮線分データ格納テーブル５１５に情報を作成する線分
探索法による経路探索部５１０と、上記仮線分データ格
納テーブル５１５をもとに発見した最短経路を配線パタ
ーンとしてパターン情報ファイル５０４に出力する出力
処理部５１１を起動する。

以下第６図を用いて、上記最短経路決定処理制御部５０
５の処理手順を説明する。第６図において、まず入力処
理部５０６を起動することにより入力処理を行い（６０
１）、次に入力情報をもとに配線可能領域データ、層変
更探索可能領域データを初期作成しく６０２，６０３）
、次いで同じく入力情報をもとに経路探索に先立って迂
回制御データを初期作成する（６０４）。その後ステッ
プ６０５において配線対象となる未配線区間に対し、配
線可能領域データ格納テーブル５１２２層変更探索可能
領域データ格納テーブル５１３．迂回制御データ格納テ
ーブル５１４を参照しつつ、線分探索法により仮線分を
発生していく。ここで得られた仮線分は逐次、仮線分デ
ータ格納テーブル５１５に作成する。以上の処理の後、
該配線区間に対し上記データ格納テーブル５１５に作成
された結果より、配線経路を編集し、配線パターンとし
てパターン情報ファイルに出力する（６０６）。

その後まだ未配線の配線区間が存在するかどうか判定し
く６０７）、もし存在すれば配線可能領域データ、層変
更探索可能領域データを上記配線パターンにより更新し
く６０２，６０３）、該未配線区間に対し同様にステッ
プ６０４，６０５゜６０６の処理を行う。そしてこの操
作を繰り返した後、すべての配線区間に対し経路探索を
終了したならば、全体処理を終了する。

線分探索法による経路探索（６０５）では上述のように
、データ格納テーブル５１２，５１３゜５１４を参照し
なからデータ格納テーブル５１５を作成していくが、同
時に経路探索に伴い５１２゜５１３では探索済の配線領
域に関する情報を更新しなから処理を行う。次に第７図
、第８図を用いて５１２，５１３におけるデータの記述
内容および６０５の処理における５１２，５１３に対す
る参照更新内容について説明する。第７図、第８図にお
いて、（Ａｘ）　、（Ａｚ）はそれぞれ配線前、レベル
２の経路探索終了時の配線状態の例を示し。

（Ａ２）において、ｓｌは垂直方向配線層、Ｂ２゜Ｂ５
は斜め４５°方向配線層において発生した仮線分を示す
。第７図において、（Ｂｚ）　、（Ｂ２）はそれぞれ（
Ａｒ）　、（Ａ２）に対応した配線可能領域データの状
態を示している。また（Ｃ１）　、　（Ｃ２）はこの配
線可能領域データの記述項目及び（Ｂｌ）。

（Ｂｚ）に対応した記述内容を示している。経路探索で
はこれらの線分データに対し、すべての記述項目すなわ
ち始点側Ｘｓ’／座標、終点側Ｘ＋’Ｊ座標及びすでに
探索したかどうかの判定フラグ（探索済フラグ）を参照
し、さらに迂回制御データ格納テーブル５１４で規定さ
れる探索の範囲内において、適当な線分データの全部な
いしは一部を用いて仮線分を発生する。その後肢線分デ
ータの一部を仮線分として用いた場合、該線分データを
複数の線分データに分割する。さらに、該仮線分に対応
した線分データに対する探索済フラグを未探索の状態か
ら探索済の状態に更新する。図の例では、配線前の線分
データＱ１．Ｑｚが未探索の状態であることを確認した
後、仮線分８２，５１５を発生したようすを示している
が、この場合線分データＱ１の一部を用いて発生した仮
線分ｓ５に対しては、線分Ｑ１を線分Ｌ１．Ｌａｗ　Ｌ
＋に分割している。また線分Ｑ２および分割した線分Ｌ
８に対する探索済フラグを未探索の状態（０）から探索
済の状態（１）に更新している。このように経路探索で
は、配線可能領域データを参照し一次元探索を行うとと
もに、一次元探索により発生した仮線分により配線可能
領域データを更新することにより処理を行う。また第８
図において、（Ｂ　１）　。

（Ｂ２）はそれぞれ（ＡＸ）　、（ＡＸ）に対応した層
変更探索可能領域データの状態を示している。また（Ｃ
１）　、（Ｃ２）はこの層変更探索可能領域データの記
述項目及び（Ｂｚ）　、（Ｂｚ）に対応した記述内容を
示している。経路探索ではこれらの格子状データの記述
項目（ｘ＋ｙ座標、探索済フラグ）を参照し、任意の格
子点位置からの層変更探索が可能かどうかを判定した上
で、層変更探索を行い、その後肢格子点位置に対応した
格子状データの探索済フラグを探索済みの状態に更新す
る。図の例では、レベル１の探索において発生した仮線
分上の格子点位置ｖ２に対し、該格子点位置が未探索の
状態であることを確認した上で、層変更探索を行ったよ
うすを示している。この場合格子点位置Ｖ２を未探索の
状態（０）から探索済の状態（１）に更新している。こ
のように経路探索では、層変更探索可能領域データを参
照し、任意の格子点位置からの層変更探索を行うととも
に、該格子点位置の層変更探索可能領域データを更新す
ることにより処理を行う。

線分探索法による経路探索（６０５）では上述のような
仮線分を順次発生し、これにより仮線分データ格納テー
ブル５１５を作成するが、出力処理（６０６）では、該
テーブル５１５をもとに配線経路を編集した後、配線パ
ターンとしてパターン情報ファイル５０４に出力する。

最後に、この配線経路の編集を可能とする該テーブル５
１５の記述内容について、第９図を用いて説明する。第
９図（Ａ）は、始点Ａから終点Ｂに至る経路探索が終了
した時点の仮線分の状態の例を示している。

ここで、ｓｉ、　ｓｚ、　Ｓａｔ　８番はレベル１の、
Ｂ５゜Ｂ６はレベル２の、Ｂ７はレベル３の仮線分を示
している。また第９図（Ｂ）は、仮線分データ格納デー
タ５１５の記述項目及び上記（Ａ）で示す状態での記述
内容を示している。本テーブルでは、レベルｉの仮線分
に対し、該仮線分が派生した元の仮線分を示すパ親仮線
分へのポインタ”、及び該仮線分が派生した元の仮線分
上の格子点位置を示す“派生元の格子点位置”を記述項
目としてもっている。なお、レベル１の仮線分に対する
″親板線分へのポインタ”は”ｎｕｌｌ”であり、６派
生元の格子点位置″は始点Ａである。本例では、レベル
１の仮線分ｓｘ、ｓｚ、ＳＲｔ　ｓａに対する″親板線
分へのポインタ”は”　ｎ　ｕ　１１”派生元の格子点
位置″は始点Ａである。また、レベル２の仮線分８５１
５８に対する″親板線分へのポインタ″はｓｌ、″派生
元の格子点位置″はｖｌであり、レベル３の仮線分ｓ７
に対する″親板線分へのポインタ′″はＢ５、″派生元
の格子点位置″はｖ２である。出力処理における配線経
路の編集は、終点Ｂに到達した仮線分から上記″派生元
の格子点位置″を参照しなから、かつ上記パ親仮線分へ
のポインタ″を参照することによる始点Ａに至る仮線分
をトレースしなから、行うことができる。本例ではまず
、仮線分ｓ７により配線経路を構成するラインＢ−ｖｚ
、中継穴ｖ２を得る。次に５７に対する″親板線分への
ポインタ″を参照することで３５を得、仮線分ｓ６によ
りラインＶ２　　Ｖｌ、中継穴ｖ１を得る。最後にＢ５
に対する″親板線分へのポインタ″を参照することでＳ
！を得、仮線分ｓ１によりラインｖ　１−Ａ　を得るこ
とができる。

以上、本発明による最短経路決定方法の一実施例を説明
したが１本実施例によれば、少なくとも３層以上の配線
層を用いた拡張された線分探索法による経路探索手段を
実現できるので、迷路法に比へ高速に処理が可能である
とともに、２層配線に比べ少ない配線層数で配線経路の
決定が可能である。さらに、任意の格子点からの仮線分
発生処理において経路の迂回量を正確に制御できるので
、所望の許容迂回量以内で高精度に配線経路を実現でき
る。

（２）第２の実施例 （１）で述べた実施例での線分探索法による経路探索部
（第５図中、５１０）において、始点から発生した複数
の仮線分に対し、該複数の仮線分上の複数の格子点から
の次レベルの仮線分発生処理を、該始点から該複数の格
子点までの複数の仮の経路に対する総迂回量の小さい順
に行うという制御機能を追加する。このようすを第１０
図に示す。

本実施例によれば、総迂回量の最も小さい格子点から順
に探索を行うので、与えられた許容迂回量を満たす経路
の中で迂回量最小のものを発見することができる。

（３）第３の実施例 （１）で述べた実施例での線分探索法による経路探索部
（第５図中、５１ｏ）において、始点から終点への配線
経路を発見できなかった場合、迂回制御情報作成部（第
５図中、５ｏ９）で与えた始点から終点への配線経路に
対する総迂回量上限値を大きくした後、経路探索を続行
するという制御機能を追加する。このようすを第１１図
に示す。

本実施例によれば、総迂回量上限値の設定値を徐々に緩
和することにより、配線率を向上できるという効果があ
る。

〔発明の効果〕

本発明によれば、斜め配線方向配線層を用いかつ少なく
とも３層以上の配線層を用いて配線パターンの決定を行
うシステムにおいて、少ない配線層数でかつ高速に配線
パターンの決定ができるという効果がある。さらに、配
線パターンの冗長な迂回を回避し、許容迂回制限長以内
で高精度に配線パターンの決定ができるという効果があ
る。

【図面の簡単な説明】

第１図は、本発明の最短経路決定方法に係る線分探索法
による経路探索における、配線経路迂回の制御方法を説
明する図、第２図は、従来技術である２層配線方法によ
り、最短経路決定を行う方法を説明する図、第３図は、
迷路法による多層配線方法により、最短経路決定を行う
方法を説明する図、第４図は、本発明の最短経路決定方
法に係る線分探索法による経路探索における、多層配線
の原理を説明する図、第５図は１本発明の第１の実施例
に係る配線パターン決定システムの構成を示すブロック
図、第６図は、第５図記載の最短経路決定処理制御部５
０５の処理手順を示すフローチャート、第７図は、第５
図記載の配線可能領域データ格納テーブル５１２を説明
する図、第８図は、第５図記載の層変更探索可能領域デ
ータ格納テーブル５１３を説明する図、第９図は、第５
図記載の仮線分データ格納テーブル５１５を説明する図
、第１０図は、本発明の第２の実施例を示す図、第１１
図は、本発明の第３の実施例を示す図である。 Ａ・・・配線対象区間の始点、Ｂ・・・配線対象区間の
終点、８１，８２．−・Ｓ＠−＝−仮線分、Ｖｌｔ　Ｖ
Ｚ＊　ｖ３゜■４・・・格子点、Ｐ・・・ピン（貫通ス
ルーホール）、第 図 （Ａ１） レベル３の探索 第 図 く層構成〉 く配線方向〉 く配線バターノリ 第 図 第 図 （Ａ＋） かうの−仄冗渾冨 第 図 第 図 第 ア 図 （Ａ２） （Ｃ＋） 第 図 （Ａ＋） （Ａ２） （Ｂ＋） （Ｂ２） （Ｃ１） （Ｃ１） 第１０図 ■〜■： 探索順序 第 図 （Ａ） （Ｂ） 第１１ 図 迂回量抑止上限値：小 迂回量抑止上限値二大

Claims (1)

1. 【特許請求の範囲】 １、プリント基板、集積回路等における配線対象区間を
   接続するための配線パターンを、少なくとも３層以上の
   配線層を同時に用いて決定する配線パターンの最短経路
   決定方法において、 （ａ）上記各配線層に対し、少なくとも３方向以上の配
   線方向をそれぞれ固有の方向として定義し、該各配線層
   における配線可能領域を、上記固有の方向に展開した線
   分データとして、各配線層毎に作成し、 （ｂ）上記各配線層における隣接する配線層への層変更
   探索可能領域を、格子状データとして作成し、 （ｃ）上記配線対象区間の始点から終点に至る配線経路
   の探索を、上記配線可能領域を用いた任意の格子点から
   の一次元探索、及び上記層変更可能領域を用いた該任意
   の格子点からの層変更探索を繰り返し行なうという線分
   探索法により実行し、 （ｄ）上記終点を通る上記各配線層に固有の方向の直線
   すべてにより各配線対象領域を複数の部分領域に分割し
   、該各部分領域に対し各配線層における任意の格子点か
   らの上記一次元探索の探索方向に単位格子当りの迂回量
   を与え、 （ｅ）上記始点から終点に至る経路の総迂回量に上限値
   を与え、上記任意の格子点から上記終点に向かう上記一
   次元探索において、該総迂回量の上限値及び上記単位格
   子当りの迂回量に従って、探索の範囲を制限する、 ことを有することを特徴とする最短経路決定方法。 ２、請求項第１項記載の最短経路決定方法において、 （ｆ）上記始点から経路探索により到達した複数の格子
   点に対し、該始点から該複数の格子点に至る経路の総迂
   回量を算出し、該総迂回量の大小に従って該複数の格子
   点からの上記終点への探索順序に優先順位を与える、 ことを特徴とする最短経路決定方法。 ３、請求項第１項記載の最短経路決定方法において、 （ｇ）上記始点から終点に至る経路の総迂回量に対し与
   える上限値を徐々に大きくし、任意の格子点からの上記
   一次元探索の範囲を徐々に拡張する、 ことを特徴とする最短経路決定方法。 ４、プリント基板、集積回路等における配線対象区間を
   接続するための配線パターンを、少なくとも３層以上の
   配線層を同時に用いて決定する配線パターンの最短経路
   決定システムにおいて、（ａ）上記各配線層に対し、少
   なくとも３方向以上の配線方向をそれぞれ固有の方向と
   して定義し、該各配線層における配線可能領域を、上記
   固有の方向に展開した線分データとして、各配線層毎に
   作成する手段、 （ｂ）上記各配線層における隣接する配線層への層変更
   探索可能領域を、格子状データとして作成する手段、 （ｃ）上記配線対象区間の始点から終点に至る配線経路
   の探索を、上記配線可能領域を用いた任意の格子点から
   の一次元探索、及び上記層変更可能領域を用いた該任意
   の格子点からの層変更探索を繰り返し行なうという線分
   探索法により実行する手段、 （ｄ）上記終点を通る上記各配線層に固有の方向の直線
   すべてにより各配線対象領域を複数の部分領域に分割し
   、該各部分領域に対し各配線層における任意の格子点か
   らの上記一次元探索の探索方向に単位格子当りの迂回量
   を与える手段、 （ｅ）上記始点から終点に至る経路の総迂回量に上限値
   を与え、上記任意の格子点から上記終点に向かう上記一
   次元探索において、該総迂回量の上限値及び上記単位格
   子当りの迂回量に従って、探索の範囲を制限する手段、 を有することを特徴とする最短経路決定システム。