JPH04260965A - ２点間の径路探索方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概要〕 ２点間の径路を迷路法を用いて行う径路探索方法に関し
、 重みを加味した迷路法によるラベル付けにおいて、ラベ
ルを付ける回数を少なくすることによりラベル付けに費
やす時間を短縮することを目的とし、 出発地点と目的地点との間の通行可能な最適径路を探索
する迷路法を用いた２点間の径路探索方法において、ラ
ベル付け中の位置から前記目的地点までのマンハッタン
距離とその位置のラベル付けした値との和を求め、この
和と前記目的地点のラベル値とを比較し前記和が前記目
的地点のラベル値より小さい時のみラベル付けを続ける
よう構成する。

〔産業上の利用分野〕

本発明は、２点間の径路を迷路法を用いて行う２点間の
径路探索方法に関する。

プリント基板上やＬＳＩ等の集積回路上の配線処理を計
算機を用いて自動設計を行う際に、２つの配線端子間の
径路を迷路法を用いて探索することが行われている。迷
路法は、格子展開法（ｇｒｉｄｅｘｐａｎｓｉｏｎ）と
も呼ばれ、ネットワーク理論や、オペレーションズ・リ
サーチの分野でよく知られている最短径路を求めるため
の算法を応用したものの総称であり、レイアウト方式の
標準化を、前提とした格子グラフの上で径路を求める算
法である。

この迷路法による算法を２端子間の配線径路を例にとり
第２図を用いて説明する。

迷路法では第２図（ａ）に示すように端子を表す２点Ａ
、Ｂが格子上に載るように、対象とする配線を行う平面
を格子状に分割し、端子対を構成する２点間の径路とな
る出発地点から目的地点までの格子上に、進んでゆく径
路の長さを示すラベルを付け、（ｂ）に示すようにラベ
ルが目的地点に到達するとラベル付けを終了する。これ
を前進探索という。なお網点で示す範囲は障害物を示し
、径路設定禁止範囲を示す。次に目的地点を起点とし自
分より１つだけラベル値の少ない格子点（少なくとも１
つは存在する）の１つを選ぶという操作を出発地点に戻
るまで繰り返し、これにより径路を認識する。これを後
退探索という。第２図において、数字を丸で囲んだ格子
に隣接する格子には、数字を丸で囲んだ格子のラベルに
１を加えた値が次のステップでラベル付けされる。（ａ
）はラベル付けが始まってから３ステップ目のラベルの
様子を示している、（ｂ）は目的地点にラベルが到達し
て全てのラベル付けが終了した後、後退探索を行い径路
が求まった様子を示す。

〔従来の技術〕

この迷路法は径路が存在すれば、必ずこれを発見し、ま
た得られる径路は最短であるという性質を持つ。しかし
、配線上の観点からは最短径路を見つけることよりも、
それ以降の配線を行うときに困難が最も少なくなるよう
な径路を得ることが重要となってくる。このため、困難
度を表す重みを加味したラベル付け法が用いられる。

第３図は重みを加味した迷路法を説明する図である。同
図中数字を丸で囲んだ格子に隣接する格子には、数字を
丸で囲んだ格子のラベルにそれぞれの格子における重み
を加えた値が次のステップでラベル付けされる。（ａ）
はラベル付けする時にそれぞれの格子に加えられる重み
を示す。（ｂ）は６ステップ目のラベル付けの状態を示
す。このとき縦線群で示した格子のラベル値１７は、こ
の上方にあるラベル値１５に重み２を加えて得られたも
のであるが、次のステップで左側にある丸付き１４に重
み２を加えた１６の値の方が小さいので、この１６に書
き換えられる。（ｃ）は目的地点にラベルが最初に到達
した様子を示したもので、この時、丸付１８、丸付１９
のラベル値は目的地点のラベル値よりも値が小さく、こ
れらのラベルの値の影響により、目的地点のラベル値が
この時の値２２よりも小さくなる可能性があるので、以
降もラベル付けが続行される、全ての書き換わったラベ
ル埴が目的地点のラベル値よりも大きな値になるまで続
行される。（ｄ）は後退探索により決まった最終径路を
示す。

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

このように重みを加味したラベル付けでは、一旦、ラベ
ルが付いた格子のラベル値が書き換えられることがあり
、目的地点にラベル値が付いた後もこのラベル値よりも
小さなラベル値が付く可能性があるため、ラベル付けが
続行される。

迷路法の配線処理におけるラベリングの占める処理時間
の割合は７０〜８０％にも及ぶ。また、重みを加味した
ラベル付けはラベル書き換えが起こることと、目的地点
にラベル値が付いた後も処理を続行する必要があるため
、配線処理においては、ラベル付けに大部分の時間が費
やされる。

本発明は、上述の問題点に鑑みてなされたもので、重み
を加味したラベル付けにおいて、ラベルを付ける回数を
少なくすることによりラベル付けに費やす時間を少なく
する２点間の径路探索方法を提供することを目的とする
。

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

上記目的を達成するため、本発明は現在ラベル付けをし
ている格子点がラベル付けを続行すれば最適径路となり
得るか否かをチェックし、無駄なラベル付けを排除する
ようにしたもので、本発明の２点間の径路探索方法は、
迷路法を用いて径路探索中、現在ラベル付け中の格子点
の位置から目的値までの最短径路であるマンハッタン距
離と現在の格子点のラベル値との和を求め、この和と目
的地点のラベル値を比較し、この和の方が目的地点のラ
ベル値より小さい時のみ、その現在ラベル付け中の格子
点のラベル付けを続行し、同じ値か大きい時はその格子
点のラベル付けを中止するようにしたものである。

目的地点にまだラベル付けが到着していないときは、そ
の目的地点のラベル値を予想されるラベル値より大きな
値、例えば、無限大の値としておく。

また、目的地点にラベル付けが到達しない時は、迷路法
によりラベル付けを行い、ラベル付けが到達した後に前
記和と目的地点のラベル値との比較を開始するようにす
る。

また、径路探索開始前に径路となる可能性のある格子点
のマンハッタン距離を計算しておく。

また、マンハッタン距離の計算は、迷路法によるラベル
付けが目的地点に到達した時点で、その時点においてラ
ベル付け中の格子点についてのみ行う。

〔作用〕

上記構成により、現在ラベル付けをしている格子点を経
由して目的地点に到る径路の目的地点でのラベル値を考
えると、このラベル付けしている格子点から目的地点ま
での最短距離はマンハッタン距離で与えられる。重み付
けが全て１であれば目的地点のラベル値は現在ラベルを
付けている格子のラベル値と目的地点までのマンハッタ
ン距離の和となる。しかし、重み付けが１以上の場合、
この格子点を経由した径路の目的地点のラベル値はこの
和より大きくなる。これにより、この和が目的地点のラ
ベル値より小さければ、ラベル付けを続行する意味があ
るが、等しいか大きくなれば、その径路は最適のもので
なくなるのでラベル付けを続行する意味がない。このよ
うに意味のない径路のラベル付けを中止することにより
、ラベル付けの回数を少なくし、ラベル付けに費やす時
間を短縮することが可能となる。

また、目的地点にラベル付けが達しない時は、目的地点
のラベル値を予想されるラベル値より、大きな値、例え
ば、無限大の値としておき、ラベル付けが到達したら、
そのラベル値とすれば、ラベル付けが到達しない期間も
前記和との比較が行える。

また、ラベルが到達するまでは、前記和と目的地点のラ
ベル値との比較を行わず、到達以降に行うことにより、
無駄な比較処理を行う必要がなくなる。

また、径路探索前に、径路となる可能性のある格子点の
目的地点までのマンハッタン距離を計算しておくことに
より、以降の前記和を求める処理が容易に行えるように
なる。

また、このマンハッタン距離を目的地点にラベル付けが
到達したときに、その時点でラベル付け中の格子点のみ
に対して算出することにより、マンハッタン距離の計算
時間を短縮することができる。

〔実施例〕

以下、本発明の実施例を図面を参照して説明する。まず
、本発明の理解を容易にするため数式を用いて説明する
。

１つの格子から隣接する格子に付けられるラベルの増加
分は重みを考えなければ（又は重みをｌとすれば）ｌが
最小となる。従って、ラベル値がＣである格子から目的
地点までの最短距離であるマンハッタン距離（つまりマ
ンハッタン街のように格子状に区画されたところで、Ａ
区画からＢ区画までの最短距離を、各区画をＸ、Ｙ座標
で表し、Σ（Ｘ＋Ｙ）をＡ区画からＢ区画に到る径路と
した場合、Σ（Ｘ＋Ｙ）の最小値をいう）をＬ、この格
子に付けられるラベルが目的地点に到達したときに付け
られるラベル値をＶとすると次式が成り立つ。

次に、目的地点の現在のラベル値をＴとする。

（このＴはまだラベル付けが目的地点に到達していない
ときには、初期値として∞とする。）このとき、 が成り立てば、（１）式との関係から となり、この格子を経由した径路によって目的地点のラ
ベルは書き換わらないことになる。すなわち、この格子
からラベルを伝えても、径路探索後に得られる径路には
影響しないことがわかる。このように（２）式を用いれ
ば、格子にラベル付けを続行するか否かの判定を行うこ
とができ、（２）式が成り立つ格子のラベル付けは行わ
ない。

第１図は本発明の実施例のラベル付けを示す図である。

同図（ａ）はラベル付開始に先立って各格子の目的地点
までのマンハッタン距離を算出した結果を表す。（ａ）
において太線で囲った９とラベル付けされた格子が出発
地点を示し、太線で囲った０とラベル付けされた格子は
目的地点を示す。また、網点で示す格子は障害物を示し
、これらの格子は径路となることが禁止されることを示
す。なお重み付けは第３図（ａ）に示すものを用いる。

（ｂ）は目的地点にラベル付けが到達するまでの従来の
重み付けを加味した迷路法を用いてラベリングした状態
を示し、目的地点にラベル付けが到達したステップ９の
状態を示す。丸で囲まれたラベル値を有する格子に隣接
する格子が次のステップでラベル付けされる対象となる
。（ｃ）は目的地点にラベル付けが到達した状態を示す
。目的地点にラベル付けが到達した後は、現在ラベル付
けを続行する格子は現在のラベル値とこの格子から目的
地点までのマンハッタン距離を加えた値Ｖを計算し、こ
のＶと目的地点のラベル値Ｔとを比較し、ＶがＴより値
が小さい時にのみその格子にラベルを付け、以降のラベ
ル付けを続行する。（ｃ）において斜線を付けた格子の
数値はＶがＴより小さい時に付けられる予定の、現在の
ラベル値に目的地点までのマンハッタン距離を加えた値
を示す。これらの値、２６、２７は目的地点の値２２よ
り大きいので、ラベル付けされず、以降のラベル付け作
業も中止される。（ｄ）はラベル付けが終了し、目的地
点より最も小さなラベル値のある格子を通って出発地点
まで戻る後退探索（またはバックトレースともいう）を
行い径路を決定した状態を示す。

なお、（ａ）のマンハッタン距離の計算は（ｃ）のマン
ハッタン距離の値が（３）式の計算に必要となった時点
で、必要とする格子についてのみ行うことにより、この
計算時間を短縮することができる。

また、本実施例では目的地点にラベル付けがされた後か
ら現在点のラベル値とマンハッタン距離の和をとる計算
を行うが、この方法だと常に目的地点にラベルが到達し
たか否かを判定しなければならない。この到達判定を排
除するためには、目的地点にラベル付けが到達するまで
は、目的地点のラベル値を予想されるラベル値より大き
な値、例えば無限大の値を入れ、到達した後は、その到
達時のラベル値に切り換えるようにすればよい。

しかしこのようにすると（ａ）に示すようにラベル付け
する前に径路となると予想される格子全てのマンハッタ
ン距離の計算が必要となる。故に状況応じて上述した方
法を適切に組み合わせて使用することが望ましい。

〔発明の効果〕

以上の説明から明らかなように、本発明は、現在ラベル
付け中の格子において、その位置のラベル値とその格子
から目的地点までのマンハッタン距離の和と、目的地点
のラベル値を比較し、その和が目的地点のラベル値より
小さい時のみラベル付けを続行することにより、無駄な
ラベル付け処理を排除しラベル付け処理時間を短縮する
ことができる。

【図面の簡単な説明】

第１図は本発明の実施例のラベル付け方法を示す図、第
２図は迷路法によるラベル付けの方法を示す図、第３図
は重み付けを加味した迷路法によるラベル付け方法を示
す図である。

Claims (5)

【特許請求の範囲】
1. 【請求項１】出発地点と目的地点との間の通行可能な最
   適 径路を探索する迷路法を用いた２点間の径路探索方法に
   おいて、ラベル付け中の位置から前記目的地点までのマ
   ンハッタン距離とこの位置のラベル付けした値との和を
   求め、この和と前記目的地点のラベル値とを比較し前記
   和が前記目的地点のラベル値より小さい時のみラベル付
   けを続けることを特徴とする２点間の経路探索方法。
2. 【請求項２】前記目的地点にラベル付けが達しないとき
   は 前記目的地点のラベル値を予想される値よりも大きな値
   に設定しておくことを特徴とする請求項１記載の２点間
   の径路探索方法。
3. 【請求項３】前記和と前記目的地点のラベル値との比較
   は、 前記目的地点にラベル付けが達した以降に行うようにし
   たことを特徴とする請求項記載の２点間の径路探索方法
4. 【請求項４】前記出発地点より前記目的地点までの径路
   と なる可能性のある地点から前記目的地点までのマンハッ
   タン距離を径路探索前に求めておくことを特徴とする請
   求項１〜３のいずれかに記載の２点点間の径路探索方法
   。
5. 【請求項５】前記目的地点に最初にラベル付けが達した
   時、 その時点でラベリング中の各地点からの前記目的地点ま
   でのマンハッタン距離を求めるようにしたことを特徴と
   する請求項３記載の２点間の径路探索方法。