JPS6155780A - 経路探索システム - Google Patents
経路探索システムInfo
- Publication number
- JPS6155780A JPS6155780A JP59178720A JP17872084A JPS6155780A JP S6155780 A JPS6155780 A JP S6155780A JP 59178720 A JP59178720 A JP 59178720A JP 17872084 A JP17872084 A JP 17872084A JP S6155780 A JPS6155780 A JP S6155780A
- Authority
- JP
- Japan
- Prior art keywords
- point
- wiring
- route
- path
- detour
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
発明の目的
産業上の利用分野
本発明は、配線の自動設計等に使用される経路探索シス
テムに関するものである。
テムに関するものである。
従来の技術
最近、プリント配線の自動設計等に使用される経路探索
システムでは、素子の高速化に伴って。
システムでは、素子の高速化に伴って。
配線上の信号の伝播遅延時間も制御することが必要にな
りつつある。このため、始点と終点間の配線長を最小に
するという従来の機能に加えて、配線長を指定された値
に合致させるという機能も新たに必要になりつつある。
りつつある。このため、始点と終点間の配線長を最小に
するという従来の機能に加えて、配線長を指定された値
に合致させるという機能も新たに必要になりつつある。
発明が解決しようとする問題点
配線長を指定値に合致させること自体は、特に難しいわ
けではなく、最小配線長の経路を選択するという従来の
機能をそのまま利用して容易に実現できる。すなわち、
まず、最小配線長の経路を探索させ、この探索された経
路の配線長が指定値以下であれば、配線不成功と見做し
て次の最小配線長の経路を探索させるという手順を、指
定値に等しい配線長の経路が見つかるまで繰り返えさせ
ればよい。
けではなく、最小配線長の経路を選択するという従来の
機能をそのまま利用して容易に実現できる。すなわち、
まず、最小配線長の経路を探索させ、この探索された経
路の配線長が指定値以下であれば、配線不成功と見做し
て次の最小配線長の経路を探索させるという手順を、指
定値に等しい配線長の経路が見つかるまで繰り返えさせ
ればよい。
しかしがら、上記方式では、探索に長時間を要するとい
う問題がある。
う問題がある。
発明の構成
問題点を解決するための手段
上記従来技術の問題点を解決する本発明のシステムは、
空間内に離散して配列された点群の情報を記憶する点群
情報記憶手段と、これら点群の−。
空間内に離散して配列された点群の情報を記憶する点群
情報記憶手段と、これら点群の−。
部を通る経路の始終点データ及び経路長データを受ける
手段と、始終点データ及び経路長データに基づき、迂回
点を設定する手段と２点群情報記憶手段を参照しつつ、
上記始点から迂回点を経て終点に至る最短経路を探索す
る手段とを備えるように構成されている。
手段と、始終点データ及び経路長データに基づき、迂回
点を設定する手段と２点群情報記憶手段を参照しつつ、
上記始点から迂回点を経て終点に至る最短経路を探索す
る手段とを備えるように構成されている。
以下９本発明の作用を実施例によって詳細に説明する。
実施例
第１図は１本発明の一実施例の構成を示す機能ブロック
図である。
図である。
このシステムは、２次元空間内に＃散し・で配列された
配線格子点群の情報を記憶するメモリテーブル１を備え
ている。また、このシステムは２経路の始終点データと
経路長データを含む経路探索指定データを受ける配線制
御部２を備えている。
配線格子点群の情報を記憶するメモリテーブル１を備え
ている。また、このシステムは２経路の始終点データと
経路長データを含む経路探索指定データを受ける配線制
御部２を備えている。
さらに、このシステムは、上記始終点データと経路長デ
ータに基づき迂回点を設定する迂回制御部３と、メモリ
テーブル１を参照しつつ上記始点。
ータに基づき迂回点を設定する迂回制御部３と、メモリ
テーブル１を参照しつつ上記始点。
迂回点及び終点を通る最短経路を探索する経路探索部４
を備えている。
を備えている。
配線制御部２は、入力部から経路探索指定データを１個
ずつ受取る。１個の経路探索指定データは、第２図に示
すように、始終点対の識別番号。
ずつ受取る。１個の経路探索指定データは、第２図に示
すように、始終点対の識別番号。
始点の識別番号、終点の識別番号、始点、終点のＸ、
Ｘ座標、配線長指定の有無を示すフラグ及び配線長指定
が有る場合の指定配線長（Ｌ）から構成されている。配
線制御部２は、受取った１個の経路探索指定データをバ
ッファメモリ５に書込んだのち、制御を迂回制御部３に
渡す。
Ｘ座標、配線長指定の有無を示すフラグ及び配線長指定
が有る場合の指定配線長（Ｌ）から構成されている。配
線制御部２は、受取った１個の経路探索指定データをバ
ッファメモリ５に書込んだのち、制御を迂回制御部３に
渡す。
迂回制御部３は、バッファメモリ５に書込まれている経
路探索指定データ中の配線長指定の有無を示すフラグを
読取り、配線長の指定が無ければ。
路探索指定データ中の配線長指定の有無を示すフラグを
読取り、配線長の指定が無ければ。
直ちに経路探索部４にその旨を通知する。
上記通知を受けた経路探索部４は、バッファメモリ５に
書込まれている始点と終点間を接続する最短の配線経路
を探索する。この際、経路探索部４は、メモリテーブル
１に書込まれている配線格子点の情報を参照する。配線
格子点の情報は、第３図に示すように、配線格子点の識
別番号、その配線格子点のＸ、Ｘ座標及びその配線格子
点の状態から成っている。配線格子点の状態は、配線に
未だ使用されていないか既に使用されているかの使用状
況、あるいは素子の搭載箇所を確保するために使用が禁
止されている等の使用条件から成っている。
書込まれている始点と終点間を接続する最短の配線経路
を探索する。この際、経路探索部４は、メモリテーブル
１に書込まれている配線格子点の情報を参照する。配線
格子点の情報は、第３図に示すように、配線格子点の識
別番号、その配線格子点のＸ、Ｘ座標及びその配線格子
点の状態から成っている。配線格子点の状態は、配線に
未だ使用されていないか既に使用されているかの使用状
況、あるいは素子の搭載箇所を確保するために使用が禁
止されている等の使用条件から成っている。
経路探索部４は、経路の探索に成功すると、その経路を
バッファメモリ５に書込み、その旨を配線制御部２に通
知する。配線制？７１１２は、バッファメモリ５に書込
まれた経路を出力すると共に、この経路に基づきメモリ
テーブル１内の対応の配線格子点の使用状況を更新し９
次の経路探索指定データを続出す。新たに読出された経
路探索指定データに対して、上述したと全く同様の探索
動作が繰り返えされる。
バッファメモリ５に書込み、その旨を配線制御部２に通
知する。配線制？７１１２は、バッファメモリ５に書込
まれた経路を出力すると共に、この経路に基づきメモリ
テーブル１内の対応の配線格子点の使用状況を更新し９
次の経路探索指定データを続出す。新たに読出された経
路探索指定データに対して、上述したと全く同様の探索
動作が繰り返えされる。
迂回制御部３は、バッファメモリ５に書込まれている経
路探索指定データ中の配線長指定の有無を示すフラグを
読取り、配線長の指定が有る場合には、迂回点の設定処
理を開始する。この迂回点の設定処理を、第４図のフロ
ーチャートと、第５図及び第６図の概念図を参照しなが
ら説明する。
路探索指定データ中の配線長指定の有無を示すフラグを
読取り、配線長の指定が有る場合には、迂回点の設定処
理を開始する。この迂回点の設定処理を、第４図のフロ
ーチャートと、第５図及び第６図の概念図を参照しなが
ら説明する。
迂回制御部３は、第４図のステップ１０において、始終
点間Ｐｉ、Ｐ２ （第５図、第６図）のＸ座標の差分の
絶対値 ΔＸ＝ＩＸ１−Ｘ２１゜Ｘ座標の差分の絶対値
ΔＹ＝ｌＹ１−Ｙ２１及び最短距離 Ｌｏ＝Δχ＋Δ
Ｙ を算定する。迂回制御部３は３次めステップ１１に
おいて、上記ΔＸとΔＹの大小関係を判定する。迂回制
御部３の制御は、ΔＸ≧ΔＹであればステップ１２に移
行し、ΔＸくΔＹであればステップ１５に移行する。
点間Ｐｉ、Ｐ２ （第５図、第６図）のＸ座標の差分の
絶対値 ΔＸ＝ＩＸ１−Ｘ２１゜Ｘ座標の差分の絶対値
ΔＹ＝ｌＹ１−Ｙ２１及び最短距離 Ｌｏ＝Δχ＋Δ
Ｙ を算定する。迂回制御部３は３次めステップ１１に
おいて、上記ΔＸとΔＹの大小関係を判定する。迂回制
御部３の制御は、ΔＸ≧ΔＹであればステップ１２に移
行し、ΔＸくΔＹであればステップ１５に移行する。
ΔＸ≧ΔＹの条件は、第５図に示すように、始点Ｐ１と
終点Ｐ２が、その最短経路とＸ軸のなす角を４５度以下
とするような横長の位置関係にあることを意味している
。一方、ΔＸくΔＹの条件は、第６図に示すように、始
点Ｐ１と終点Ｐ２が縦長の位置関係にあることを意味し
ている。第５図と第６図において、最短経路は巨視的な
直線で示しであるが、微視的には９等間隔の基盤目状に
配列された配線格子点を連ねる階段状の経路である。従
って、上記最短経路の長さ、すなわち始終点間の最短距
離の実際の長さは、ΔＸ＋ΔＹ （＝Ｌｏ）で与えられ
る。
終点Ｐ２が、その最短経路とＸ軸のなす角を４５度以下
とするような横長の位置関係にあることを意味している
。一方、ΔＸくΔＹの条件は、第６図に示すように、始
点Ｐ１と終点Ｐ２が縦長の位置関係にあることを意味し
ている。第５図と第６図において、最短経路は巨視的な
直線で示しであるが、微視的には９等間隔の基盤目状に
配列された配線格子点を連ねる階段状の経路である。従
って、上記最短経路の長さ、すなわち始終点間の最短距
離の実際の長さは、ΔＸ＋ΔＹ （＝Ｌｏ）で与えられ
る。
始終点が、第５図に示すような横長の位置関係にある場
合、ステップ１２において。
合、ステップ１２において。
δｙ＝（Ｌ−Ｔ、ｏ）／２
が算定される。但し、Ｌは経路探索指定データによって
指定されている配線長である。
指定されている配線長である。
次のステップ１３において、Ｘ座標が（Ｙ２＋δｙ）で
かつＸ座標がＸｌとＸ２の間に存在するような線分ＡＡ
’ と、Ｘ座標が（Ｙｌ−δｙ）でかつＸ座標がＸｌと
Ｘ２の間に存在するような線分ＢＢ’が選択される。始
点Ｐ１から、上記各線分上の任意の配線格子点ａまたは
ｂを経由して終点Ｐ２に至る経路の最短距離は、配線格
子点ａ。
かつＸ座標がＸｌとＸ２の間に存在するような線分ＡＡ
’ と、Ｘ座標が（Ｙｌ−δｙ）でかつＸ座標がＸｌと
Ｘ２の間に存在するような線分ＢＢ’が選択される。始
点Ｐ１から、上記各線分上の任意の配線格子点ａまたは
ｂを経由して終点Ｐ２に至る経路の最短距離は、配線格
子点ａ。
ｂの選択方法に無関係に全て上記指定配線長しに等しく
なる。以下、上記の線分ＡＡ’ 、ＢＢ’を迂回用線分
と称する。
なる。以下、上記の線分ＡＡ’ 、ＢＢ’を迂回用線分
と称する。
迂回制御部３は１次のステップ１４に進み、メモリテー
ブル１の内容を参照しながら、迂回用線分ＡＡ’ 、Ｂ
Ｂ’上の全ての空き格子点（未使用格子点）を迂回点と
して選択し、迂回点の設定動作を終了する。
ブル１の内容を参照しながら、迂回用線分ＡＡ’ 、Ｂ
Ｂ’上の全ての空き格子点（未使用格子点）を迂回点と
して選択し、迂回点の設定動作を終了する。
これに対して、迂回制御部３は、始終点が第６図に示す
ような縦長の位置関係にあることをステップ１１で判定
した場合には、ステップ１５に進み。
ような縦長の位置関係にあることをステップ１１で判定
した場合には、ステップ１５に進み。
δｘ＝（Ｌ−１，０）／２
を算定する。
迂回制御部３は１次のステップ１６において。
Ｘ座標が（ＸＩ−δＸ）でかつＸ座標がＹｌとＹ２の間
に存在するような線分ＣＣ° と２ Ｘ座標が（Ｘ２＋
δＸ）でかつＸ座標がＹｌとＹ２の間に存在するような
線分ＤＤ’を選択する。始点Ｐ１から、上記各線分上の
任意の配線格子点Ｃまたはｄを経由して終点Ｐ２に至る
経路の最短距離は。
に存在するような線分ＣＣ° と２ Ｘ座標が（Ｘ２＋
δＸ）でかつＸ座標がＹｌとＹ２の間に存在するような
線分ＤＤ’を選択する。始点Ｐ１から、上記各線分上の
任意の配線格子点Ｃまたはｄを経由して終点Ｐ２に至る
経路の最短距離は。
配線格子点ｃ、ｄの選択方法に無関係に全て上記指定長
しに等しくなる。これらの線分ＣＧ’ 、ＤＤｏ も、
線分ＡＡ’ 、ＢＢ’ と同様迂回用線分であり５次の
ステップ１７において、これら迂回用線分上の全ての空
き格子点が迂回点として選択される。
しに等しくなる。これらの線分ＣＧ’ 、ＤＤｏ も、
線分ＡＡ’ 、ＢＢ’ と同様迂回用線分であり５次の
ステップ１７において、これら迂回用線分上の全ての空
き格子点が迂回点として選択される。
迂回制御部３は、ステップ１４または１７で設定した全
ての迂回点を、ステップ１８においてパンツアメモリ５
に書込み、その旨を経路探索部に通知して迂回点設定処
理を終了する。
ての迂回点を、ステップ１８においてパンツアメモリ５
に書込み、その旨を経路探索部に通知して迂回点設定処
理を終了する。
上記通知を受けた経路探索部４は、バッファメモリ５に
設定されている始終点データと迂回点データに凸づき、
メモリテーブル１の内容を参照しつつ、始点から、迂回
制御部３で設定された１または複数の迂回点のうちの一
つを通り、終点に至る最短の経路を探索する。
設定されている始終点データと迂回点データに凸づき、
メモリテーブル１の内容を参照しつつ、始点から、迂回
制御部３で設定された１または複数の迂回点のうちの一
つを通り、終点に至る最短の経路を探索する。
以上、２次元空間内に格子状に配列された点群を連ねる
ように、配線経路を設定する一例を説明したが、これら
の点群は、一般には円筒座標等信の適宜な座標系のもと
に配列されていてもよく。
ように、配線経路を設定する一例を説明したが、これら
の点群は、一般には円筒座標等信の適宜な座標系のもと
に配列されていてもよく。
また、３次元空間内に想定された直角座標９円筒座標１
球座標等適宜な座標系のもとに配列されていてもよい。
球座標等適宜な座標系のもとに配列されていてもよい。
発明の効果
以上詳細に説明したように２本発明の経路探索システム
は、指定された配線長を実現するための１または複数の
迂回点を設定したのちこの迂回点を通る最短の経路を探
索する構成であり、またこのような迂回点の設定に要す
る時間は経路探索に要する時間よりも究めて短いので、
経路探索のみの繰り返し゛によって指定された配線長の
経路を設定する方式に比べ、経路探索時間を大幅に短縮
できるという効果を奏する。
は、指定された配線長を実現するための１または複数の
迂回点を設定したのちこの迂回点を通る最短の経路を探
索する構成であり、またこのような迂回点の設定に要す
る時間は経路探索に要する時間よりも究めて短いので、
経路探索のみの繰り返し゛によって指定された配線長の
経路を設定する方式に比べ、経路探索時間を大幅に短縮
できるという効果を奏する。
第１図は本発明の一実施例の構成う示す機能ブロック図
、第２図は配線制御部２に入力される経路探索指定デー
タの構成の一例を示す概念図、第３図は第１図のメモリ
テーブル１内に蓄積される点群情報の構成の一例を示す
概念図、第４図は第１図の迂回制御部３の処理の一例を
説明するフローチャート、第５図、第６図は迂回制御部
３の処理を説明するための概念図である。 １・・配線格子点の情報を蓄積するメモリテーブル、２
・・経路探索指定データを受取る配線制御部、３・・迂
回点を設定する迂回制御部、４・・経路探索部。 笑２ｔ！ｇＩ 尊 ３Ｆ！！Ｊ ＄４ｙ！Ｊ 算 ５ｙｎ ｐｔ、（ｉｔ、Ｙｌン
、第２図は配線制御部２に入力される経路探索指定デー
タの構成の一例を示す概念図、第３図は第１図のメモリ
テーブル１内に蓄積される点群情報の構成の一例を示す
概念図、第４図は第１図の迂回制御部３の処理の一例を
説明するフローチャート、第５図、第６図は迂回制御部
３の処理を説明するための概念図である。 １・・配線格子点の情報を蓄積するメモリテーブル、２
・・経路探索指定データを受取る配線制御部、３・・迂
回点を設定する迂回制御部、４・・経路探索部。 笑２ｔ！ｇＩ 尊 ３Ｆ！！Ｊ ＄４ｙ！Ｊ 算 ５ｙｎ ｐｔ、（ｉｔ、Ｙｌン
Claims (1)
- 【特許請求の範囲】 空間内に離散して配列された点群の情報を記憶する点群
情報記憶手段と、 前記点群の一部を通るように探索される経路の始点及び
終点を指定する始終点データ並びに該経路の長さを指定
する経路長データを含む経路探索指定データを受ける手
段と、 前記経路探索指定データに基づき、前記経路長データに
合致するような長さの経路となるように、前記始点及び
終点間の最短経路に対する迂回点を設定する手段と、 前記点群情報記憶手段を参照しつつ、前記始点から迂回
点を経て終点に至る最短経路を探索する手段とを備えた
ことを特徴とする経路探索システム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59178720A JPS6155780A (ja) | 1984-08-28 | 1984-08-28 | 経路探索システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59178720A JPS6155780A (ja) | 1984-08-28 | 1984-08-28 | 経路探索システム |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS6155780A true JPS6155780A (ja) | 1986-03-20 |
Family
ID=16053386
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59178720A Pending JPS6155780A (ja) | 1984-08-28 | 1984-08-28 | 経路探索システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS6155780A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6467685A (en) * | 1987-09-09 | 1989-03-14 | Hitachi Ltd | Wiring method for wiring length designation |
-
1984
- 1984-08-28 JP JP59178720A patent/JPS6155780A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6467685A (en) * | 1987-09-09 | 1989-03-14 | Hitachi Ltd | Wiring method for wiring length designation |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN107228677B (zh) | 偏航识别方法和装置 | |
| EP2565583B1 (en) | Navigation device, method of outputting a map, and method of generating a database | |
| CN113280824A (zh) | 高精度地图与标准地图关联方法及设备 | |
| EP0612023B1 (en) | Net diagram routing method | |
| CN112631338B (zh) | 一种航线规划方法、装置、计算机设备及存储介质 | |
| WO2020005636A1 (en) | Indoor location-based service | |
| KR102050535B1 (ko) | 다양한 배관 굴곡 각도에 따른 3차원 모델링 정보에서의 배관 연결 방법 및 장치 | |
| JP2022517195A (ja) | 画像処理方法並びにその、装置、電子機器及びコンピュータプログラム | |
| KR20230145197A (ko) | 공간 관계 결정 방법, 장치, 컴퓨터 기기 및 저장 매체 | |
| CN109902038B (zh) | 一种PCIe总线地址空间分配方法及装置 | |
| CN106775481B (zh) | 数据读取方法及设备 | |
| CN112999658B (zh) | 用于游戏三维空间飞行的寻路方法、装置及介质 | |
| JPS63265312A (ja) | 移動経路探索方法 | |
| CN118999604A (zh) | 平行道路识别方法、装置、设备、存储介质及程序产品 | |
| JPS59189471A (ja) | 配線経路探索システム | |
| JP2801208B2 (ja) | 位相数学的なネットワークをメモリに記憶させる方法、並びに該ネットワーク内の２−セルを見出す方法及びデバイス | |
| CN114298404A (zh) | 路段及路线生成方法、装置、设备和计算机可读存储介质 | |
| CN116758138B (zh) | 一种道路中心线确定方法、装置、设备和存储介质 | |
| CN113269833B (zh) | 电气末端定位方法、装置、设备及存储介质 | |
| CN110971287B (zh) | 信源通信方法、装置、系统及设备 | |
| JPH07109627B2 (ja) | 閉領域自動認識装置 | |
| JPS63265310A (ja) | 移動経路探索方法 | |
| CN121902749A (zh) | 电路版图中走线的边缘线段移动方法、装置、介质及设备 | |
| CN111104700A (zh) | 过街天桥三维建模的方法、装置、设备及可读存储介质 | |
| JPH02146681A (ja) | 等高線抽出方式 |