(57)【特許請求の範囲】
【請求項１】
直方体である空間分割対象を、３陵を構成するＸ軸，Ｙ軸，Ｚ軸の何れかに垂直な平面により複数の直方体要素に分割して当該空間分割対象の特徴に応じた最適な分割レイアウトを抽出するレイアウト抽出方法であって、
分割面は、
（ｉ）全て矩形であり、
（ｉｉ）相互に交差せず、
（ｉｉｉ）任意の分割面の各辺を通り分割面に垂直で、かつ前記空間分割対象の面外面または他の直方体要素の分割面とＴ字をなす、
ように選ばれる直方体分割であり、
直方体要素の分割面と、それに隣接する分割された直方体領域（部屋と呼ぶ）との相対位置関係のみに着目し、
直方体である空間分割対象の右方向をＸ方向、奥方向をＹ方向、下方向をＺ方向とすると、部屋ｒの右下奥頂点と同一点上に頂点があり、任意の部屋ｒの１つの面を含む分割画が存存するとき、その分割面を部屋ｒの主壁とし、
各部屋の名前をその部屋の部屋番号に書き換え、
全体直方体の左面に部屋ｒ1，ｒ2，・・・，ｒm（ただし、ｒ1＜ｒ2＜・・・＜ｒm）が隣接するとき、
Ｏ（ＷX）＝Ｘrm・・・Ｘr2Ｘr1と表示し、同様に、Ｏ（ＷY）、Ｏ（ＷZ）も同様に表示し、
部屋ｉの主壁ＷiがＸ軸に垂直で、部屋ｒ1，ｒ2，・・・，ｒm（ただし、ｒ1＜ｒ2＜・・・＜ｒm）の左面がＷに含まれるとき、Ｏ（ｉ）＝ｉＸrm・・・Ｘr2Ｘr1と表示し、主壁ＷiがＹ軸に垂直であるとき、Ｚ軸に垂直なときも同様に表示し、
Ｏ（ｎ）＝ｎと表示するとき、
Ｏ＝Ｏ（ＷX）Ｏ（ＷY）Ｏ（ＷZ）Ｏ（１）Ｏ（２）・・・Ｏ（ｎ−１）Ｏ（ｎ）で表される記号列は直方体分割を表し、
部屋数ｎの直方体分割において最も左上手前になる順に各部屋に１〜ｎの部屋番号を一意的に決め、１，２，・・・，ｎをこの順で含み、Ｘ1，Ｘ2，・・・，Ｘn，Ｙ1，Ｙ2，・・・，Ｙn，Ｚ1，Ｚ2，・・・，Ｚnを含む記号列Ｐについて、
コンピュータが、Ｐの１より前の記号列をＰ（０），ｉとｉ＋１の間（ｉを含む）の記号列をＰ（ｉ）としたとき、記号列の直方体分割をデコードするアルゴリズムにより、前記記号列が
条件１．Ｐ（０）はＸ，Ｙ，Ｚの記号列の連結である：
条件２．任意の１≦ｉ＜ｎに対してＰ（ｉ）はｉとＸ，Ｙ，Ｚの何れかのみの記号列である：
条件３．Ｐは（Ｘi，ｉ）の順序対の下で括弧対応を満たす。（Ｙi，ｉ），（Ｚi，ｉ）についても同様である：
条件４．任意の１≦ｉ＜ｎに対してＰ（ｉ）＝ＸrmＸrm-1・・・Ｘr1であるならば、任意のｒｍ＜ａ≦ｎに対して、以下の（１）、（２）の何れかを満たす：
（１）Ｐ（ｒ1），・・・，Ｐ（ｒm-1）はＹa、Ｚaの何れも含まない：
（２）Ｐ（ｒm），・・・，Ｐ（ａ−１）はＸaを含む：
Ｐ（ｉ）がＹ，Ｚの記号列である場合も同様である：
４条件をみたす場合に、前記（i）〜（iii）を満たす直方体分割であると判定することを特徴とする直方体のレイアウト抽出方法。
【請求項２】
前記直方体要素がＬＳＩであり、前記対象が前記ＬＳＩを構成する回路モジュールであることを特徴とする請求項１に記載のレイアウト抽出方法。
【請求項３】
直方体である空間分割対象を、当該空間分割対象の特徴に応じて最適な分割レイアウトを抽出するためのレイアウト抽出装置であって、空間座標上でＸＹＺ軸に沿って置かれている直方体を分割面（Ｘ軸，Ｙ軸，Ｚ軸のいずれかに垂直な平面）によって複数の直方体領域に分割することを直方体分割と定義し、分割された直方体領域を部屋と定義し、
前記空間分割対象を、
分割面が、
（ｉ）全て矩形であり、
（ｉｉ）相互に交差せず、
（ｉｉｉ）任意の分割面の各辺を通り分割面に垂直で、かつ前記空間分割対象の面外面または他の直方体要素の分割面とＴ字をなすように、
選ばれた直方体分割を抽出するため、前記レイアウト抽出装置は、
オペレータが直方体である空間対象を直方体分割した記号列、および記憶手段に記憶された直方体分割に対する変更指令、の入力を行う入力手段と
前記直方体分割の記号列、および、演算手段から出力される直方体分割の記号列、を記憶する記憶手段と、
直方体分割に関する複数のアルゴリズムからなるプログラムを記憶したメモリ手段と、
マイクロプロセッサを備え、前記入力手段からの入力指示により、前記メモリ手段に記憶してあるプログラムを選択して演算処理を行い、前記記憶手段に出力する演算手段と、
を少なくとも備え、
前記記憶手段は、
直方体である空間分割対象の右方向をＸ方向、奥方向をＹ方向、下方向をＺ方向と定義し、部屋ｒの右下奥頂点と同一点上に頂点があり、任意の部屋ｒの１つの面を含む分割画が存存するとき、その分割面を部屋ｒの主壁と定義し、
各部屋の名前をその部屋の部屋番号に書き換え、
全体直方体の左面に部屋ｒ1，ｒ2，・・・，ｒm（ただし、ｒ1＜ｒ2＜・・・＜ｒm）が隣接するとき、
Ｏ（ＷX）＝Ｘrm・・・Ｘr2Ｘr1と定義し、同様に、Ｏ（ＷY）、Ｏ（ＷZ）も同様に定義し、
部屋ｉの主壁ＷiがＸ軸に垂直で、部屋ｒ1，ｒ2，・・・，ｒm（ただし、ｒ1＜ｒ2＜・・・＜ｒm）の左面がＷに含まれるとき、Ｏ（ｉ）＝ｉＸrm・・・Ｘr2Ｘr1と定義し、主壁ＷiがＹ軸に垂直であるとき、Ｚ軸に垂直なときも同様に定義し、
Ｏ（ｎ）＝ｎと定義し、
入力された記号列がＯ（ＷX）Ｏ（ＷY）Ｏ（ＷZ）Ｏ（１）Ｏ（２）・・・Ｏ（ｎ−１）Ｏ（ｎ）で定義された配列の記号列で表示された直方体分割に名前を付け記憶し、
また、前記演算装置より出力される、前記配列に従う記号列である直方体分割に名前を付け記憶する、
記憶手段であり、
前記メモリ手段は、前記入力手段より入力された記号列の直方体分割の分割面が（ｉ）全て矩形であり、（ｉｉ）相互に交差せず、（ｉｉｉ）任意の分割面の各辺を通り分割面に垂直で、かつ前記空間分割対象の面外面または他の直方体要素の分割面とＴ字をなす、直方体分割であることを検証するための複数のアルゴリズムを含むプログラムを記憶しているメモリー手段であり、
前記入力手段より、部屋数ｎで最も左上手前になる順に各部屋に１〜ｎの部屋番号を一意的に決め、１，２，・・・，ｎをこの順で含み、Ｘ1，Ｘ2，・・・，Ｘn，Ｙ1，Ｙ2，・・・，Ｙn，Ｚ1，Ｚ2，・・・，Ｚnを含む記号列Ｐを入力し、この記号列が前記(i)〜(iii)を満足する直方体分割をどうかを調べる指令を入力したとき、
前記演算手段は、前記入力された記号列と、前記Ｐの１より前の記号列をＰ（０），ｉとｉ＋１の間（ｉを含む）の記号列をＰ（ｉ）を演算し、前記メモリ手段に記憶された、デコードアルゴリズムからなるプログラムを使用し、
条件１．Ｐ（０）はＸ，Ｙ，Ｚの記号列の連結である：
条件２．任意の１≦ｉ＜ｎに対してＰ（ｉ）はｉとＸ，Ｙ，Ｚの何れかのみの記号列である：
条件３．Ｐは（Ｘi，ｉ）の順序対の下で括弧対応を満たし、（Ｙi，ｉ），（Ｚi，ｉ）についても順序対の下で括弧対応を満たす：
条件４．任意の１≦ｉ＜ｎに対してＰ（ｉ）＝ＸrmＸrm-1・・・Ｘr1であるならば、任意のｒｍ＜ａ≦ｎに対して、以下の（１）、（２）の何れかを満たす：
（１）Ｐ（ｒ1），・・・，Ｐ（ｒm-1）はＹa、Ｚaの何れも含まない：
（２）Ｐ（ｒm），・・・，Ｐ（ａ−１）はＸaを含む：
Ｐ（ｉ）がＹ，Ｚの記号列である場合も同様に（１），（２）の何れかを満たす：
上記４条件をみたしている場合は、記号列Ｐは上記(i)〜(iii)の条件を満たす直方体分割であると判定し、前記記号列Ｐを前記記憶手段に出力し、
前記入力手段より前記記憶手段に記憶している、直方体分割の記号列を指定して、任意に分割数を変更または、直方体要素のサイズを変更する指令が入力された場合、
前記演算手段は、前記入力手段の入力を受け、指定された記号列を前記記憶手段より読込み、前記指令より、前記メモリ手段に記憶されている前記指令に対応するアルゴリズムを利用したプログラムを使用して、前記指令後の直方体分割の記号列が、前記４条件を満たす記号列であるかどうかを判断し、該記号列が満たした場合は、該記号列を前記記憶装置に出力する、
ことを特徴とする直方体のレイアウト抽出装置。
【請求項４】
前記直方体要素がＬＳＩであり、前記対象が前記ＬＳＩを構成する回路モジュールであることを特徴とする請求項３に記載のレイアウト抽出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、三次元領域を直方体分割により分割する３Ｄフロアプランの表現技術に関すし、具体的には直方体である空間分割対象を、３陵を構成するＸ軸，Ｙ軸，Ｚ軸の何れかに垂直な平面により複数の直方体要素に分割して当該空間分活対象の特徴に応じた最適な分割レイアウトを抽出するレイアウト抽出方法およびレイアウト抽出装置に関する。
【背景技術】
【０００２】
たとえばＶＬＳＩレイアウト設計においては、チップを表す矩形を水平方向及び垂直方向の分割線により、多数の矩形領域（部屋）に分割し、各々の部屋にモジュールを割り当てて配置することが行われる。
矩形分割の表現方法のうち、Ｑ−Ｓｅｑｅｎｃｅとして知られている方法（Ｓａｋａｎｕｓｈｉ  ｅｔ．ａｌ．；”Ｔｈｅ  Ｑｕａｒｔｅｒ  Ｓｔａｔｅ  Ｓｅｑｕｅｎｃｅ（Ｑ−Ｓｅｑｕｅｎｃｅ）ｔｏ  Ｒｅｐｒｅｓｅｎｔ  Ｆｌｏｏｒｐｌａｎ，”ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  ＣＡＳ−１；ｖｏｌ５０，Ｎｏ３，ｐｐ３７６−３８６，２００３．）では、各部屋の分割に安部順（Ａｂｅ  Ｏｒｄｅｒｉｎｇ：阿部道雄，”正方形の内部を総て異なる有限個の正方形で隙間なく一重に覆う問題に就いて”日本数学物理学会会報  Ｖｏｌ．４，Ｎｏ．４  ｐｐ．３５９−３６６  １９３０年１２月）と呼ばれる矩形分割方法が採用されている。
安部の表現方法によれば、あらゆる矩形分割を、順番を一意に決めて表現することができる。また、矩形分割に対応するＱ−ＳｅｑｕｅｎｃｅをＳＡ法と呼ばれる方法で探索することにより実用時間内に矩形分割を得ることができる。
ところで、近年、ＭＣＭや回路素子自体を三次元に集積した複数の能動層をもつ三次元ＶＬＳＩの開発が注目されている。そのレイアウト設計のために「複数の直方体を互いに重なり合うことなく最も体積の小さい直方体内に配置せよ」という三次元パッキング問題の研究が行われている（［１］Ｈ．Ｙａｍａｚａｋｉ，Ｋ．Ｓａｋａｎｕｓｈｉ．Ｓ．Ｎａｋａｔａｋｅ，ａｎｄ  Ｙ．Ｋａｊｉｔａｎｉ：”Ｔｈｅ  ３Ｄ−Ｐａｃｋｉｎｇ  ｂｙ  Ｍｅｔａ  Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅ  ａｎｄ  Ｐａｃｋｉｎｇ  Ｈｅｕｒｉｓｔｉｃｓ，”信学論，ｖｏｌ．Ｅ８３−Ａ，ｐｐ．６３９−６４５，２０００．［２］Ｐ．Ｈ．Ｙｕｈ，Ｃ．Ｌ．Ｙｏｕｎｇ，Ｙ．Ｗ．Ｃｈａｎｇ，ａｎｄ  Ｈ．Ｌ．Ｃｈｅｎ，”Ｔｅｍｐｏｒａｌ  Ｆｌｏｏｒｐｌａｎｎｉｎｇ  Ｕｓｉｎｇ  ３Ｄ−ＳｕｂＴＣＧ，”Ｐｒｏｃ．ＡＳＰ−ＤＡＣ，ｐｐ．７２５−７３０，２００４．［３］川井英教，藤吉邦洋：”木構造データを用いた直方体パッキング表現手法，”第１８回回路とシステム軽井沢ワークショップ，ｐｐ．１９９−２０４，２００５．［４］山岸弘和，二宮洋，浅井秀樹：”三次元フロアプランのためのパッキング表現手法，”第１８回回路とシステム軽井沢ワークショップ，ｐｐ．２０５−２１０，２００５．［５］小平行秀，児玉親亮，藤吉邦洋，高橋篤司：”計算資源割り当てスケジューリングのための直方体パッキング表現手法の検討，”第１８回回路とシステム軽井沢ワークショップ，ｐｐ．２１１−２１６，２００５．参照）。
しかし、三次元パッキング問題では配線領域のことが考慮されておらず、パッキングに基づいたモジュールの配置では無秩序に配線が結ばれ、配線が長くなったりＶＬＳＩの性能が悪くなったりしてしまう。
そこで、二次元のＶＬＳＩ設計において矩形分別を求めたように、三次元ＶＬＳＩレイアウト設計においても、直方体を平面（分割面）によって小直方体領域に分割した『直方体分割』を求め、その分割面を配線領域として秩序だった配線をすることが考えられる。
これまでの、直方体分割の研究は、スライスと呼ばれる構造についてのみ行われてきた。スライス構造の直方体分割とは、直方体を矩形分割面で２つの小直方体に分割する操作を再帰的に行うことで得られる直方体分割であり、スライス構造の矩形分割と同様に木を用いて表現可能である（Ｌ．Ｃｈｅｎｇ，Ｌ．Ｄｅｎｇ，ａｎｄ  Ｄ．Ｆ．Ｗｏｎｇ：”Ｆｌｏｏｒｐｌａｎ  Ｄｅｓｉｇｎ  ｆｏｒ  ３Ｄ−ＩＣｓ，”Ｔｈｅ  １２ｔｈ  Ｗｏｒｋｓｈｏｐ  ｏｎ  ＳＡＳＩＭＩ，ｐｐ．３９５−４０１，２００４）。しかし、スライス構造だけでは、あまりにも表現できる直方体分割が少なく、利便性に欠ける。そこで、より多くの直方体分割に対応可能な表現方法の開発が求められてきた。
しかし、一般構造の直方体分割は、様々な形状の分割面による複雑な分割を含み（太田秀則、ｅｔ  ａｌ．”直方体分割の部屋数について，”第１８回回路とシステム軽井沢ワークショップ，ｐｐ．６０７−６１２，２００５．参照）、これを表現するのは非常に困難である。
そのため、直方体分割の分割面の形状を矩形に限定した直方体分割を考える。分割面の形状を矩形に限定した直方体分割構造は明らかにすべてのスライス構造を含む。また、任意の矩形分割において、部屋に一意に順序をつけることができたように、この構造である任意の直方体分割においても一意に順序をつけることができる。
本発明は矩形分割の表現方法であるＯ−Ｓｅｑｕｅｎｃｅを提案する。
本発明では、コードがＯ−Ｓｅｑｕｅｎｃｅであるための必要十分を明らかにする。そして、ＳＡ法等を用いて、探索を行えるように、任意のＯ−Ｓｅｑｕｅｎｃｅから任意のＯ−Ｓｅｑｕｅｎｃｅに到達可能である隣接解の生成手法を提案する。
本発明の目的は、直方体である空間分割対象を、３陵を構成するＸ軸，Ｙ軸，Ｚ軸の何れかに垂直な平面により複数の直方体要素に分割して当該空間分活対象の特徴に応じた最適な分割レイアウトを抽出するレイアウト抽出方法およびレイアウト抽出装置を提供することにある。
【発明の開示】
【課題を解決するための手段】
【０００３】
本発明のレイアウト抽出方法は（１）〜（２）を要旨とする。
（１）直方体である空間分割対象を、３陵を構成するＸ軸，Ｙ軸，Ｚ軸の何れかに垂直な平面により複数の直方体要素に分割して当該空間分割対象の特徴に応じた最適な分割レイアウトを抽出するレイアウト抽出方法であって、
分割面は、
（ｉ）全て矩形であり、
（ｉｉ）相互に交差せず、
（ｉｉｉ）任意の分割面の各辺を通り分割面に垂直で、かつ前記空間分割対象の面外面または他の直方体要素の分割面とＴ字をなす、
ように選ばれる直方体分割であり、
直方体要素の分割面と、それに隣接する分割された直方体領域（部屋と呼ぶ）との相対位置関係のみに着目し、
直方体である空間分割対象の右方向をＸ方向、奥方向をＹ方向、下方向をＺ方向とすると、部屋ｒの右下奥頂点と同一点上に頂点があり、任意の部屋ｒの１つの面を含む分割画が存存するとき、その分割面を部屋ｒの主壁とし、
各部屋の名前をその部屋の部屋番号に書き換え、
全体直方体の左面に部屋ｒ1，ｒ2，・・・，ｒm（ただし、ｒ1＜ｒ2＜・・・＜ｒm）が隣接するとき、
Ｏ（ＷX）＝Ｘrm・・・Ｘr2Ｘr1と表示し、同様に、Ｏ（ＷY）、Ｏ（ＷZ）も同様に表示し、
部屋ｉの主壁ＷiがＸ軸に垂直で、部屋ｒ1，ｒ2，・・・，ｒm（ただし、ｒ1＜ｒ2＜・・・＜ｒm）の左面がＷに含まれるとき、Ｏ（ｉ）＝ｉＸrm・・・Ｘr2Ｘr1と表示し、主壁ＷiがＹ軸に垂直であるとき、Ｚ軸に垂直なときも同様に表示し、
Ｏ（ｎ）＝ｎと表示するとき、
Ｏ＝Ｏ（ＷX）Ｏ（ＷY）Ｏ（ＷZ）Ｏ（１）Ｏ（２）・・・Ｏ（ｎ−１）Ｏ（ｎ）で表される記号列は直方体分割を表し、
部屋数ｎの直方体分割において最も左上手前になる順に各部屋に１〜ｎの部屋番号を一意的に決め、１，２，・・・，ｎをこの順で含み、Ｘ1，Ｘ2，・・・，Ｘn，Ｙ1，Ｙ2，・・・，Ｙn，Ｚ1，Ｚ2，・・・，Ｚnを含む記号列Ｐについて、
コンピュータが、Ｐの１より前の記号列をＰ（０），ｉとｉ＋１の間（ｉを含む）の記号列をＰ（ｉ）としたとき、記号列の直方体分割をデコードするアルゴリズムにより、前記記号列が
条件１．Ｐ（０）はＸ，Ｙ，Ｚの記号列の連結である：
条件２．任意の１≦ｉ＜ｎに対してＰ（ｉ）はｉとＸ，Ｙ，Ｚの何れかのみの記号列である：
条件３．Ｐは（Ｘi，ｉ）の順序対の下で括弧対応を満たす。（Ｙi，ｉ），（Ｚi，ｉ）についても同様である：
条件４．任意の１≦ｉ＜ｎに対してＰ（ｉ）＝ＸrmＸrm-1・・・Ｘr1であるならば、任意のｒｍ＜ａ≦ｎに対して、以下の（１）、（２）の何れかを満たす：
（１）Ｐ（ｒ1），・・・，Ｐ（ｒm-1）はＹa、Ｚaの何れも含まない：
（２）Ｐ（ｒm），・・・，Ｐ（ａ−１）はＸaを含む：
Ｐ（ｉ）がＹ，Ｚの記号列である場合も同様である： 
４条件をみたす場合に、前記（i）〜（iii）を満たす直方体分割であると判定することを特徴とする直方体のレイアウト抽出方法。
（２）前記直方体要素がＬＳＩであり、前記対象が前記ＬＳＩを構成する回路モジュールであることを特徴とする請求項１に記載のレイアウト抽出方法。
本発明のレイアウト抽出装置は（３）〜（４）を要旨とする。
（３）直方体である空間分割対象を、当該空間分割対象の特徴に応じて最適な分割レイアウトを抽出するためのレイアウト抽出装置であって、空間座標上でＸＹＺ軸に沿って置かれている直方体を分割面（Ｘ軸，Ｙ軸，Ｚ軸のいずれかに垂直な平面）によって複数の直方体領域に分割することを直方体分割と定義し、分割された直方体領域を部屋と定義し、
前記空間分割対象を、
分割面が、
（ｉ）全て矩形であり、
（ｉｉ）相互に交差せず、
（ｉｉｉ）任意の分割面の各辺を通り分割面に垂直で、かつ前記空間分割対象の面外面または他の直方体要素の分割面とＴ字をなすように、  
選ばれた直方体分割を抽出するため、前記レイアウト抽出装置は、
オペレータが直方体である空間対象を直方体分割した記号列、および記憶手段に記憶された直方体分割に対する変更指令、の入力を行う入力手段と
前記直方体分割の記号列、および、演算手段から出力される直方体分割の記号列、を記憶する記憶手段と、
直方体分割に関する複数のアルゴリズムからなるプログラムを記憶したメモリ手段と、
マイクロプロセッサを備え、前記入力手段からの入力指示により、前記メモリ手段に記憶してあるプログラムを選択して演算処理を行い、前記記憶手段に出力する演算手段と、
を少なくとも備え、
前記記憶手段は、
直方体である空間分割対象の右方向をＸ方向、奥方向をＹ方向、下方向をＺ方向と定義し、部屋ｒの右下奥頂点と同一点上に頂点があり、任意の部屋ｒの１つの面を含む分割画が存存するとき、その分割面を部屋ｒの主壁と定義し、
各部屋の名前をその部屋の部屋番号に書き換え、
全体直方体の左面に部屋ｒ1，ｒ2，・・・，ｒm（ただし、ｒ1＜ｒ2＜・・・＜ｒm）が隣接するとき、
Ｏ（ＷX）＝Ｘrm・・・Ｘr2Ｘr1と定義し、同様に、Ｏ（ＷY）、Ｏ（ＷZ）も同様に定義し、
部屋ｉの主壁ＷiがＸ軸に垂直で、部屋ｒ1，ｒ2，・・・，ｒm（ただし、ｒ1＜ｒ2＜・・・＜ｒm）の左面がＷに含まれるとき、Ｏ（ｉ）＝ｉＸrm・・・Ｘr2Ｘr1と定義し、主壁ＷiがＹ軸に垂直であるとき、Ｚ軸に垂直なときも同様に定義し、
Ｏ（ｎ）＝ｎと定義し、
入力された記号列がＯ（ＷX）Ｏ（ＷY）Ｏ（ＷZ）Ｏ（１）Ｏ（２）・・・Ｏ（ｎ−１）Ｏ（ｎ）で定義された配列の記号列で表示された直方体分割に名前を付け記憶し、
また、前記演算装置より出力される、前記配列に従う記号列である直方体分割に名前を付け記憶する、
記憶手段であり、
前記メモリ手段は、前記入力手段より入力された記号列の直方体分割の分割面が（ｉ）全て矩形であり、（ｉｉ）相互に交差せず、（ｉｉｉ）任意の分割面の各辺を通り分割面に垂直で、かつ前記空間分割対象の面外面または他の直方体要素の分割面とＴ字をなす、直方体分割であることを検証するための複数のアルゴリズムを含むプログラムを記憶しているメモリー手段であり、
前記入力手段より、部屋数ｎで最も左上手前になる順に各部屋に１〜ｎの部屋番号を一意的に決め、１，２，・・・，ｎをこの順で含み、Ｘ1，Ｘ2，・・・，Ｘn，Ｙ1，Ｙ2，・・・，Ｙn，Ｚ1，Ｚ2，・・・，Ｚnを含む記号列Ｐを入力し、この記号列が前記(i)〜(iii)を満足する直方体分割をどうかを調べる指令を入力したとき、
前記演算手段は、前記入力された記号列と、前記Ｐの１より前の記号列をＰ（０），ｉとｉ＋１の間（ｉを含む）の記号列をＰ（ｉ）を演算し、前記メモリ手段に記憶された、デコードアルゴリズムからなるプログラムを使用し、
条件１．Ｐ（０）はＸ，Ｙ，Ｚの記号列の連結である：
条件２．任意の１≦ｉ＜ｎに対してＰ（ｉ）はｉとＸ，Ｙ，Ｚの何れかのみの記号列である：
条件３．Ｐは（Ｘi，ｉ）の順序対の下で括弧対応を満たし、（Ｙi，ｉ），（Ｚi，ｉ）についても順序対の下で括弧対応を満たす：
条件４．任意の１≦ｉ＜ｎに対してＰ（ｉ）＝ＸrmＸrm-1・・・Ｘr1であるならば、任意のｒｍ＜ａ≦ｎに対して、以下の（１）、（２）の何れかを満たす：
（１）Ｐ（ｒ1），・・・，Ｐ（ｒm-1）はＹa、Ｚaの何れも含まない：
（２）Ｐ（ｒm），・・・，Ｐ（ａ−１）はＸaを含む：
Ｐ（ｉ）がＹ，Ｚの記号列である場合も同様に（１），（２）の何れかを満たす： 
上記４条件をみたしている場合は、記号列Ｐは上記(i)〜(iii)の条件を満たす直方体分割であると判定し、前記記号列Ｐを前記記憶手段に出力し、
前記入力手段より前記記憶手段に記憶している、直方体分割の記号列を指定して、任意に分割数を変更または、直方体要素のサイズを変更する指令が入力された場合、
前記演算手段は、前記入力手段の入力を受け、指定された記号列を前記記憶手段より読込み、前記指令より、前記メモリ手段に記憶されている前記指令に対応するアルゴリズムを利用したプログラムを使用して、前記指令後の直方体分割の記号列が、前記４条件を満たす記号列であるかどうかを判断し、該記号列が満たした場合は、該記号列を前記記憶装置に出力する、
ことを特徴とする直方体のレイアウト抽出装置。
（４）前記直方体要素がＬＳＩであり、前記対象が前記ＬＳＩを構成する回路モジュールであることを特徴とする請求項３に記載のレイアウト抽出装置。
【図面の簡単な説明】
【０００４】
図１は本発明のレイアウト抽出装置を示す説明図である。
図２（Ａ）は６つの部屋に分割された矩形分割の例を示す図、（Ｂ）は（Ａ）の矩形分割の最も左上にある部屋を消去した状態を示す図、（Ｃ）は矩形分割後の全体矩形を示す図、（Ｄ）は部屋数の矩形分割において最も左上になる順に各部屋に部屋番号を一意に決めた様子を示す図である。
図３はＱ−シーケンスにおける括弧対応の一例を示す図である。
図４（Ａ），（Ｂ）は本発明で扱う直方体分割の例を示す図である。
図５（Ａ）は４つの部屋（部屋番号１〜４）を示す図であり、（Ｂ）〜（Ｅ）は部屋を順次消去したときの様子を示す図である。
図６はＯ−Ｓｅｑｕｅｎｃｅにおける括弧対応の一例を示す図である。
図７（Ａ）は直方体分割の例を示す図、（Ｂ）は（Ａ）の直方体分割に部屋を挿入した例を示す図である。
図８は部屋を削除（消去）したときのＯ−Ｓｅｑｕｅｎｃｅの説明図である。
図９は部屋を削除（消去）したときのＯ−Ｓｅｑｕｅｎｃｅの処理過程である説明図である。
図１０（Ａ），（Ｂ），（Ｃ）は直方体分割のＯ−Ｓｅｑｕｅｎｃｅの説明図である。
図１１（Ａ），（Ｂ），（Ｃ）は直方体分割の例を示す図である。
図１２はＱ−Ｓｅｑｕｅｃｎｃｅに対応する矩形分割を示す図である。
図１３はＱ−Ｓｅｑｕｅｃｎｃｅにおける挿入の操作を示す図である。
図１４は実施例で使用する直方体分割の部屋を示す図である。
図１５は図１４の直方体分割の部屋の右面が含まれる壁を捜すときこのアルゴリズムの動作の説明図である。
図１６は図１４の直方体分割の部屋の主壁に右面が含まれる部屋を探すときのアルゴリズムの説明図である。
図１７は図１４の直方体分割の部屋の主壁に右面が隣接する部屋を捜すときのアルゴリズムの説明図である。
【発明を実施するための最良の形態】
【０００５】
《１》
図１は本発明のレイアウト抽出装置を示す説明図である。図１では、レイアウト抽出装置１は、直方体である空間分割対象を、当該空間分活対象の特徴に応じて最適な分割レイアウトを抽出するためのものであって、コンピュータにより構成することができる。
レイアウト抽出装置１は、前記空間分割対象の情報を格納する記憶装置を内蔵しており、任意に分割数を適宜変更したり直方体要素のサイズを変更したりできる。本発明では、レイアウト抽出装置１は、分割はＯ−Ｓｅｑｕｅｎｃｅと称される分割手順（あるいは分解手順）を実行することができる。
レイアウト抽出装置１は、分割面が（ｉ）全て矩形であり、（ｉｉ）相互に交差せず、（ｉｉｉ）任意の分割面の各辺を通り分割面に垂直で、かつ前記空間分割対象の面外面または他の直方体要素の分割面とＴ字をなし、３陵を構成するＸ軸，Ｙ軸，２軸の何れかに垂直な平面により複数の直方体要素に分割するプログラム（Ｏ−Ｓｅｑｕｅｎｃｅ実行プログラム）を搭載している。このＯ−Ｓｅｑｕｅｎｃｅは後述するように文字列から構成されている。レイアウト抽出装置１のプロセッサ１１は、メモリ１２に格納されたＯ−Ｓｅｑｕｅｎｃｅ実行プログラムを実行して空間分割対象を分割等して、当該空間分割対象に搭載される回路モジュール等と比較することができる。図１ではＯ−Ｓｅｑｕｅｎｃｅ処理に必要なデータは記憶装置１３に記憶されている。
《２》
従来技術としてのＱ−Ｓｅｑｕｅｎｃｅを説明する。矩形（全体矩形）を垂直・水平線（分割線）によって複数の小矩形領域（部屋）に分割することを矩形分割と呼ぶ。どの分割線も、その端点は他方面の線分とＴ字状に接するものとする（Ｔ字接点）。分割線が十字をなすとき、Ｔ字接点が同一点上にあるものとみなし、どの２つの分割線も互いに交差し合わないものとする。
図２（Ａ）に６つの部屋に分割された矩形分割の例を示す。矩形分割は各々の線分が座標を持つので、無限に存在するが、部屋とそれに隣接する分割線の相対位置関係のみに着目すると、有限種類に分類することができる。
部屋ｒの右下頂点と同一点上に頂点があり、任意の部屋ｒの１つの辺を含む分割線が存在するとき、その分割線を部屋ｒの主セグとする。最も右下にある部屋以外のどの部屋にもちょうど１つの主セグが存在する。部屋数が２以上矩形分割において、最も左上にある部屋の主セグが垂直線分であるとき、この主セグを左に移動し、全体矩形の左辺に合併させることで、最も左上にある部屋とその主セグを消去できる。同様にして主セグが水平線分のときも最も左上にある部屋を消去できる。
図２（Ｂ）に図２（Ａ）の矩形分割の最も左上にある部屋を消去した状態を示し、図２（Ｃ）に矩形分割後の全体矩形を示す。この操作を繰り返し行うことで、図２（Ｄ）に示すように、部屋数ｎの矩形分割において最も左上になる順に各部屋に１〜ｎの部屋番号を一意に決めることができる。
各部屋の名前をその部屋の部屋番号と置き換えた矩形分割において、全体矩形の左辺に部屋ｒ１，ｒ２，ｒｍ（ただしｒ１＜ｒ２＜・・・＜ｒｍ）が隣接するときＱ（ＳＲ）＝Ｒｒｍ・・・Ｒｒ２Ｒｒ１とする。同様に、全体矩形の上辺にｒ１，ｒ２，・・・ｒｍ（ただしｒ１＜ｒ２＜・・・＜ｒｍ）が隣接するときＱ（ＳＢ）＝Ｂｒｍ・・・Ｂｒ２Ｂｒ１とする。
部屋番号ｉの部屋の主セグＳｉが垂直線分で、部屋ｒ１，ｒ２，・・・，ｒｍ（ただしｒ１＜ｒ２＜・・・＜ｒｍ）の左辺がＳｉに含まれるとき、Ｑ（ｉ）＝ｉＲｒｍ・・・Ｒｒ２Ｒｒ１とする。同様に主セグＳｉが水平線分であり、部屋ｒ１，ｒ２，・・・，ｒｍ（ただしｒ１＜ｒ２＜・・・＜ｒｍ）の上辺がＳｉに含まれるとき、Ｑ（ｉ）＝ｉＢｒｒｍ・・・Ｂｒ２Ｂｒ１とする。また、Ｑ（ｎ）＝ｎとする。
Ｑ−ＳｅｑｅｎｃｅＱは以下のように定義する。
Ｑ＝Ｑ（ＳＲ）Ｑ（ＳＢ）Ｑ（１）Ｑ（２）・・・Ｑ（ｎ−１）Ｑ（ｎ）
Ｑ−Ｓｅｑｅｎｃｅは、矩形分割と１対１で対応する矩形分割の表現手法であり、たとえば図２（Ａ）〜（Ｄ）に示した矩形分割のＱ−Ｓｅｑｅｎｃｅは、Ｒ２Ｒ１Ｂ６Ｂ１１Ｂ３Ｂ２２Ｒ４Ｒ３３Ｂ５Ｂ４４Ｒ５５Ｒ６６となる。
Ｑ−Ｓｅｑｅｎｃｅの必要十分条件を以下に示す。
１，２，・・・ｎ，Ｒ１，Ｒ２，・・・，Ｒｎ，Ｂ１，Ｂ２，・・・，Ｂｎからなり、１，２，・・・ｎはこの順序で含まれる記号列Ｔについて、Ｔにおいて、１より前の記号列をＴ（０）、ｉとｉ＋１の間（ｉを含む）の記号列をＴ（ｉ）としたとき、Ｔが「部屋名を部屋順とした矩形分割に対応するＱ−ｓｅｑｕｅｎｃｅ」であるための必要十分条件は、次の３つの条件を満たすことである。
条件１．Ｔ（０）はＲ，Ｂの記号列の連結である；
条件２．任意の１≦ｉ＜ｎに対してＴ（ｉ）はｉとＲ，Ｂのどちらかのみの記号列である；
条件３．Ｔは（Ｒｉ，ｉ）の順序対の下で括弧対応を満たす。（Ｂｉ，ｉ）についても同様である（図３に括弧対応の一例を示す）：
条件３．から、部屋数ｎの矩形分割を示すＱ−Ｓｅｑｕｅｎｃｅである記号列Ｑの中の任意のＲｒａについて、対応する部屋ｒａを一意に求めることができるので、記号列Ｑの中のＲｒａ（∈｛Ｒ１・・・Ｒｎ｝）を単にＲと表記することもできる。Ｂについても同様である。
以下に矩形分割へのデコードアルゴリズムを示す．
入力：Ｑ−Ｓｅｑｅｎｃｅ
出力：矩形分割
部屋ｎだけからなる矩形分割を用意。
ｆｏｒ（ｋ＝ｎ−１，ｎ−２，ｎ−３，・・・，１）｛
ｉｆ（Ｑ（ｋ）＝ｋＲｒｍＲｒｍ−１・・・Ｒｒ１）
部屋ｋを部屋ｒｍｒｍ−１ｒ１の左に挿入する。
ｉｆ（Ｑ（ｋ）＝ｋＢｒｍＢｒｍ−１・・・Ｂｒ１）
部屋ｋを部屋ｒｍｒｍ−１ｒ１の上に挿入する。
｝
《３》
以下、Ｏ−Ｓｅｑｕｅｎｃｅへの拡張について述べる。
空間座標上でＸＹＺ軸に沿って置かれている直方体（全体直方体）を分割面（Ｘ軸，Ｙ軸，Ｚ軸のいずれかに垂直な平面）によって複数の直方体領域に分割することを直方体分割と呼び、分割された直方体領域を部屋と呼ぶ。
本明細書では分割面について以下の制約を設ける。
（ｉ）分割面は全て矩形形状である。
（ｉｉ）分割面は交差し合わない。
（ｉｉｉ）任意の分割面Ｗの各辺を通り分割面Ｗに垂直である壁はちょうど１つずつ存在する。ここで、壁とは全体直方体の面もしくは分割面のことである。任意の分割面Ｗはその辺上で他の壁とＴ字をなす。
スライス構造である直方体分割集合は本発明で扱う直方体分割集合の部分集合である。
図４（Ａ），（Ｂ）に本発明で扱う直方体分割の例を示す。図４（Ｂ）はスライス構造の直方体分割である。直方体分割は各々の分割面が座標を持つので、無限に存在するが、部屋とそれに隣接する分割面の相対位置関係のみに着目すると、有限種類に分類することができる。
右方向をＸ方向、奥方向をＹ方向、下方向をＺ方向とする。部屋ｒの右下奥頂点と同一点上に頂点があり、任意の部屋ｒの１つの面を含む分割画が存存するとき、その分割面を部屋ｒの主壁とする。最も右下奥にある部屋以外のどの部屋にもちょうど１つの主壁が存在する。
最も左手前にある部屋の主壁がＸ軸に垂直であるとき、その上壁を左に移動させ、全体直方体の左面に合併させることで、最も左上手前にある部屋の主壁を消去できる。
また、この操作を行った後の直方体分割も明らかに本稿で定めた制約を満たす直方体分割である。同様にして主壁Ｙ軸、Ｚ軸に垂直であるときも最も左上手前にある部屋を消去できる。この操作を繰り返し行うことで、部屋数ｎの直方体分割において最も左上手前になる順に各部屋に１〜ｎの部屋番号を一意的に決めることができる。
なお、最も右下奥にある部屋の部屋番号をｎとする。図５（Ａ）から（Ｅ）は、直方体分割の説明図である。図５（Ａ）は４つの部屋（部屋番号１〜４）を示す図であり、図５（Ｂ）〜（Ｅ）は部屋を順次消去したときの様子を示す図である。図５（Ｂ）に示す直方体分割の最も左上手前の部屋を消去すると、（Ｃ）のようになり、（Ｃ）が示す直方体分割の最も左手前の部屋を消去すると（Ｄ）のようになり、（Ｄ）が示す直方体分割の最も左上手前の部屋を消去すると（Ｅ）のようになる。
各部屋の名前をその部屋の部屋番号に書き換えた直方体分割において、全体直方体の左面に部屋ｒ１，ｒ２，・・・，ｒｍ（ただし、ｒ１＜ｒ２＜・・・＜ｒｍ）が隣接するとき、Ｏ（ＷＸ）＝Ｘｒｍ・・・Ｘｒ２Ｘｒ１とする。同様に、Ｏ（ＷＹ）、Ｏ（ＷＺ）を定義する。
部屋ｉの主壁ＷｉがＸ軸に垂直で、部屋ｒ１，ｒ２，・・・，ｒｍ（ただし、ｒ１＜ｒ２＜・・・＜ｒｍ）の左面がＷに含まれるとき、Ｏ（ｉ）＝ｉＸｒｍ・・・Ｘｒ２Ｘｒ１とする。主壁ＷｉがＹ軸に垂直であるとき、Ｚ軸に垂直なときも同様に定義する。また、Ｏ（ｎ）＝ｎとする。Ｏ−ＳｅｑｕｅｎｃｅＯを以下のように定義する。
Ｏ＝Ｏ（ＷＸ）Ｏ（ＷＹ）Ｏ（ＷＺ）Ｏ（１）Ｏ（２）・・・Ｏ（ｎ−１）Ｏ（ｎ）
以下に直方体分割へ線形時間でデコードするアルゴリズムを示す。
入力：Ｏ−Ｓｅｑｅｎｃｅ，出力：直方体分割
部屋ｎだけからなる直方体分割を用意。
ｆｏｒ（ｋ＝ｎ−１，ｎ−２，ｎ−３，・・・，１）｛
ｉｆ（Ｏ（ｋ）＝ｋＸｒｍＸｒｍ−１・・・Ｘｒ１）
部屋ｋを部屋ｒｍｒｍ−１ｒ１の左に挿入する。
ｉｆ（Ｏ（ｋ）＝ｋＹｒｍＹｒｍ−１・・・Ｙｒ１）
部屋ｋを部屋ｒｍｒｍ−１ｒ１の手前に挿入する。
ｉｆ（Ｏ（ｋ）＝ｋＺｒｍＺｒｍ−１・・・Ｚｒ１）
部屋ｋを部屋ｒｍｒｍ−１・・・ｒ１の上に挿入する。
｝
たとえば、図５（Ａ）の直方体分割に対応するＯ−Ｓｅｑ：Ｘ１Ｙ２Ｙ１Ｚ３Ｚ２Ｚ１１Ｘ４Ｘ３Ｘ２２Ｙ４Ｙ３３Ｚ４が与えられらとすると、図５（Ｅ）の部屋４だけからなる直方体分割を初期状態とし、部屋４の上に部屋３を挿入することで図５（Ｄ）の直方体分割が得られる。さらに、その直方体分割の部屋３．４の左に部屋２を挿入することで図５（Ｃ）の直方体分割が得られ、この直方体分割の部屋２，３，４の左に部屋１を挿入することで、図５（Ｂ）の直方体が得られる。
Ｏ−Ｓｅｑｅｎｃｅの必要十分条件を以下に述べる。
１，２，・・・，ｎをこの順で含み、Ｘ１，Ｘ２，・・・，Ｘｎ，Ｙ１，Ｙ２，・・・，Ｙｎ，Ｚ１，Ｚ２，・・・，Ｚｎを含む記号列Ｐについて、Ｐの１より前の記号列をＰ（０），ｉとｉ＋１の間（ｉを含む）の記号列をＰ（ｉ）としたとき、ＰがＯ−Ｓｅｑｕｅｎｃｅであるための必要十分は、次の４つの条件を満たすことである。
条件１．Ｐ（０）はＸ，Ｙ，Ｚの記号列の連結である：
条件２．任意の１≦ｉ＜ｎに対してＰ（ｉ）はｉとＸ，Ｙ，Ｚの何れかのみの記号列である：
条件３．Ｐは（Ｘｉ，ｉ）の順序対の下で括弧対応を満たす。（Ｙｉ，ｉ），（Ｚｉ，ｉ）についても同様である（図６のＯ−Ｓｅｑｕｅｎｃｅにおける括弧対応図参照）：
条件４．任意の１≦ｉ＜ｎに対してＰ（ｉ）＝ＸｒｍＸｒｍ−１・・・Ｘｒ１であるならば、任意のｒｍ＜ａ≦ｎに対して、以下の（１），（２）の何れかを満たす：
（１）Ｐ（ｒ１），・・・，Ｐ（ｒｍ−１）はＹａ，Ｚａの何れも含まない：
（２）Ｐ（ｒｍ），・・・，Ｐ（ａ−１）はＸａを含む：
Ｐ（ｉ）がＹ，Ｚの記号列である場合も同様である。
Ｘ１Ｙ２Ｙ１Ｚ３Ｚ２Ｚ１１Ｘ４Ｘ３Ｘ２２Ｙ４Ｙ３３Ｚ４４
条件３から、部屋数ｎの直方体分割を示すＯ−Ｓｅｑである記号列Ｏの中の任意のＸｒａについて、対応する部屋ｒａを一意に求めることができるので、記号列Ｏの中のＸｒａ（∈｛Ｘ１・・・Ｘｎ｝）を単にＸと表記することもできる。Ｙ，Ｚについても同様である。
条件４を記号列Ｐが満たさないのならば、前述のデコードアルゴリズムにより、直方体分割を得ることができない。例えば、Ｏ−Ｓｅｑｕｅｎｃｅではない記号列：Ｘ４Ｘ１Ｙ２Ｙ１Ｚ３Ｚ２Ｚ１１Ｘ３Ｘ２２Ｙ４Ｙ３３Ｚ４４から直方体分割をデコードすると、Ｘ３Ｘ２２Ｙ４Ｙ３３Ｚ４４までで、図７（Ａ）のような直方体分割が得られる。この後、１とＸ３Ｘ２とあるから、部屋３、部屋２の左に部屋１を挿入しなければならないが、部屋３と部屋２の左面を合わせた領域は矩形ではないので、部屋１を挿入することは不可能である。このように、条件４を満たさない記号列はデコードアルゴリズムにより判別可能である。このように条件４を満たさない記号列はデコードアルゴリズムにより判別可能である。図７（Ｂ）に図７（Ａ）の直方体分割に部屋１を挿入した例を示す。
次に、直方体分割の探索手法を述べる。
ＳＡ方により直方体の分割を検索するために、Ｑ−Ｓｅｑｕｅｎｃｅと同様に任意の部屋を削除した後に、部屋を挿入することで隣接解を生成する。隣接解をたどることでどの解にも到達可能であり、解空間の直径はｎ−１となる。
直方体分割において指定された任意の部屋番号ａの部屋は、部屋番号ａ−１の部屋の主壁、もしくは部屋番号ａの部屋の主壁を部屋番号ａの部屋を挟んで反対側の壁と合併させることにより削除できる。
以下に部屋番号ａの部屋を削除した直方体分割に対応するＯ−Ｓｅｑｕｅｎｃｅを求めるアルゴリズムを示す。
入力：部屋削除前のＯ−Ｓｅｑｕｅｎｃｅ、消去する部屋番号ａ、部屋削除後のＯ−Ｓｅｑｕｅｎｃｅ）
ｉｆ（ａ≠１）
ｉｆ（ａ−１とａの間の記号数が１より多い）｛
ｉｆ（ａの直後の記号列がＸである）
ａとａ＋１の間の記号列をＸａの直後に移動
ｉｆ（ａの直後の記号列がＹである）
ａとａ＋１の間の記号列をＹａの直後に移動
ｉｆ（ａの直後の記号列がＺである）
ａとａ＋１の間の記号列をＺａの直後に移動
｝
ａ，Ｘａ，Ｙａ，Ｚａを消去
部屋削除に必要な計算複雑度はＯ（ｎ）であり、工夫をすればＯ（１）で可能である。
ａ＝１のとき、削除される部屋は最も左上手前の部屋であるので、すでに述べたように、最も左上手前にある部屋はその主壁を全体直方体の外面と合併させて消去できる。図８に示すように削除後のＯ−Ｓｅｑｕｅｎｃｅから、ａ，Ｘａ，Ｙａ，Ｚａを削除したものとなる。
ａ−１とａとの間の記号数が１のとき、部屋番号ａ１−１の主壁を挟んでその部屋と隣接している部屋は部屋番号ａの部屋だけである。このとき部屋番号ａ−１の部屋の主壁を合併させて部屋番号ａの部屋を消去できる。削除後のＯ−Ｓｅｑｕｅｎｃｅからａ、Ｘａ，Ｙａ，Ｚａを削除したものとなる。
ａ−１とａの間の記号数が１より多いとき、部屋番号ａの部屋の主壁を合併させて部屋番号ａの部屋を消去できる。削除前のＯ−Ｓｅｑｕｅｎｃｅのａの直後の記号列がＸの系列だったとき、部屋ａの削除後の直方体分割に対応するＯ−Ｓｅｑｅｎｃｅは、図９に示すように削除前のＯ−Ｓｅｑｕｅｎｃｅのａの直後の記号列をＸａの直前に移ってから、ａ，Ｘａ，Ｙａ，Ｚａを削除したものとなる。ａの直後の記号列が、Ｙ，Ｚの系列だったときも同様である。
たとえば、図１０（Ａ）に示す直方体分割に対応するＯ−ＳｅｑｕｅｎｃｅＸ１Ｙ２Ｙ１Ｚ３Ｚ２Ｚ１１Ｘ３Ｘ２２Ｙ３３について、部屋３を削除する場合、２と３との間にはＹ３しかないため、元のＯ−Ｓｅｑｕｅｎｃｅから３，Ｘ３，Ｙ３，Ｚ３を除いたＸ１Ｙ２Ｙ１Ｚ３Ｚ２Ｚ１１Ｘ３Ｘ２２を得る。これは部屋２の主壁を部屋３の奥側の壁と合併させて部屋３を削除した直方体分割（図１０（Ｂ））に対応するＯ−Ｓｅｑｕｅｎｃｅである。一方、部屋３を削除する場合、１と２との間にはＸ３とＸ２があるため、元のＯ−Ｓｅｑｕｅｎｃｅの２の直後のＹ３をＹ２の直前に移動させ、２，Ｘ２，Ｙ２，Ｚ２を除いた、Ｘ１Ｙ３Ｙ１Ｚ３Ｚ１１Ｘ３３を得る。これは、部屋２の主壁を部屋２の手前側の壁と合併させて部屋２を削除した直方体分割（図１０（Ｂ））に対応するＯ−Ｓｅｑｕｅｎｃｅである。
以下、「指定された部屋の左側、上側、手前側に部屋を新しく挿入する方法」と「指定された部屋の右側、下側、奥側に部屋を新しく挿入する方法」の２つの挿入方法を説明する。
指定された部屋の左側、上側、手前側への部屋の挿入
以下では、指定された部屋の左側に部屋を挿入する操作について述べるがう上側、手前側に挿入する操作も同様である。
部屋数ｎの直方体分割において、部屋番号１〜ｎの部屋の部屋番号の順序を変えずに部屋ａの左側に新しい部屋ｂを挿入する。部屋ｂの右面は、部屋ａの左面を含み、得られた部屋数ｎ＋１の直方体分割において、新しく挿入された部屋ｂの部屋番号は、部屋ａの部屋番号の直前になるものとする。このとき、複数の通りの挿入が可能な場合がある。たとえば、図１１（Ａ）の直方体分割において、部屋２の左側に部屋ｂを挿入して得られる直方体分割は、部屋ｂの右面が部屋２のみと接するもの（図１１（Ｂ））と、部屋ｂの右面が部屋２，３，４と接するもの（図１１（Ｃ））の２つがある。しかし、部屋ｂの形状は直方体でなければならないので、左面が部屋２，３だけと接するように挿入することはできない。また、部屋ｂの右面が部屋１，２，３，４と接するような挿入は部屋ｂの部屋番号が部屋２の直前にならないのでここでは考慮しない。
部屋ａの左に隣接している壁をＷとする。Ｘ，ａがＯ（ｉ）＝ｉＸｒ１Ｘｒ２・・・Ｘｒｎ、もしくはＯ（ＷＸ）＝Ｘｒ１Ｘｒ２・・・Ｘｒｎに含まれるとき、部屋ａの左に隣接している壁Ｗについて、壁Ｗの右に隣接している部屋はｒ１，ｒ２，・・・，ｒｎである。
たとえば、図５（Ａ）の直方体分割の部屋２の左の壁に隣接する部屋は対応するＯ−Ｓｅｑｕｅｎｃｅ：Ｘ１Ｙ２Ｙ１Ｚ３Ｚ２Ｚ１１Ｘ４Ｘ３Ｘ２２Ｙ４Ｙ３３Ｚ４４に・・・１Ｘ４Ｘ３Ｘ２２・・・とあるので、２，３，４である。
本実施形態で設けた制約から壁Ｗは矩形であり壁Ｗの右の部屋と隣接する領域も全部矩形である。また、部屋と隣接する領域はそれぞれ重なりあわず、壁Ｗの右に部屋と隣接しない領域はない。よって、「壁Ｗ」から「各部屋と隣接する領域」への分割は矩形分割とみなすことができる。このとき、部屋ａの左に隣接している壁Ｗについて、壁Ｗの領域を壁Ｗの右の部屋と隣接する領域へ分割する矩形分割と対応するＱ−ＳｅｑｕｅｃｎｃｅＱは、Ｏからｒ１，ｒ２，・・・・・，ｒｎ，Ｙｒ１，Ｙｒ２，・・・・・，Ｙｒｎ，Ｚｒ１，Ｚｒ２，・・・・・，Ｚｒｎ以外のものを除き、ＹをＲ、ＺをＢに変えたものである。なお、このとき、Ｑ−ＳｅｑｕｅｃｎｃｅにおいてＹ方向を水平、Ｚ方向を垂直としている。たとえば、図５（Ａ）の直法体分割の部屋２の左の壁に隣接する部屋は２，３，４なので、Ｏ−Ｓｅｑｕｅｃｎｃｅ：Ｘ１Ｙ２Ｙ１Ｚ３Ｚ２Ｚ１１Ｘ４Ｘ３Ｘ２２Ｙ４Ｙ３３Ｚ４４から、Ｑ−Ｓｅｑｕｅｃｎｃｅ：Ｒ２Ｂ３Ｂ３２Ｒ４Ｒ３３Ｂ４４を得る。
これは、Ｙ方向を水平、Ｚ方向を垂直としたとき壁に対応する全体矩形を部屋２，３，４に分割した矩形分割に対応する。図１２にＱ−Ｓｅｑｕｅｃｎｃｅ：Ｒ２Ｂ３Ｂ２２Ｒ４Ｒ３３Ｂ４４に対応する矩形分割を示す。
図１２では、図５に示す直方体分割の部屋２の右の壁について、右にある部屋と隣接する領域への分割、図５が示す直方体分割の右側について、左にある部屋と隣接する領域に分割する。
部屋番号の順序を変えずに部屋番号ａの部屋の左側に新しい部屋ｂを挿入するとき、部屋ｂとその右の部屋集合が隣接する領域は矩形形状にならなくてはならない。矩形分割において以下の法則が成立する。
部屋の面を含む壁の識別．壁に含まれる面をもつ部屋の識別、直方体分割Φにおいて部屋の面を含む壁の識別，壁に含まれる面をもつ部屋の識別方法を説明する。
矩形分割において、部屋集合の領域が矩形形状となる必要十分条件を以下に説明する。
矩形分割Φにおいて部屋番号がａ以上ｂ以下の部屋すべてを併せた領域が矩形となるための必要十分条件矩形Φに対応するＱ−Ｓｅｑｕｅｎｃｅが以下の２つを満たすことである。
条件１：記号ａとｂの間に、Ｂｃ，Ｒｃを含まない。ここでｃとは、ｃ＞ｂを満たす任意の部屋番号である。
条件２：Ｂａを含むＱ（ｉ）についてｉよりも前にＢｄが存在しない。ここでｄはａ≦ｄ≦ｂを満たす任意の部屋番号であるＲａについても同様である。
たとえば、図２の矩形分割において、部屋２〜５の領域は矩形形状となるが、部屋２〜４の領域では記号２と４の間にＢ５があるので、矩形形状にならない。部屋２〜６では、Ｑ（１）がＢ２を含むが、Ｑ（ＳＢ）がＢ６を含むので矩形計上にならない。
部屋ａの左の壁の矩形分割においてその領域が矩形形状になる部屋集合をＯ（ｎ）時間で全列挙するアルゴリズムを示す。なお、部屋集合の矩形形状の領域において、部屋ａは常に最も左上に位置することに注意する。
矩形分割において、矩形形状となる部屋集合の列挙（ただし、ａが領域の左上に位置する）
（入力：Ｑ−Ｓｅｑｕｅｎｃｅ  Ｑ，部屋ａ，出力：矩形形状の領域となる部屋集合）
Ｒａの直前のＲ列の長さに１を足したものをｋＲとする。Ｂａの直前のＢ列の長さに１を足したものをｋｂとする。
ｌＲ＝０，ｌＢ＝０とする。
部屋ａのＱ−Ｓｅｑｕｅｎｃｅにおける部屋番号をｔとする。
ｆｏｒ（ａから部屋番号がｎとなる部屋までの各部屋）｛
ｉｆ（ｌＲ＝０）、ｋＲを１減らす
ｅｌｓｅ  ｌＲを１減らす
ｉｆ（ｌＢ＝０）、ｋＢを１減らす
ｅｌｓｅ  ｌＢを１減らす
ｉｆ（ｋＲまたはｋＢが０より少ない）アルゴリズム終了
ｉｆ（ｌＲ＝０かつｌＢ＝０）
｛部屋番号ｔからｉの部屋を出力｝
ｉｆ（部屋番号ｉの部屋の直後Ｒ列）
｛直後のＲの数をｌＲに足す｝
ｉｆ（部屋番号ｉの部屋の直後Ｂ列）
｛直後のＢの数をｌＢに足す｝
｝
たとえば、図１２の矩形分割に対応するうＱ−Ｓｅｑｕｅｎｃｅ：Ｙ２Ｚ３Ｚ２２Ｙ４Ｙ３３Ｚ４４において、部屋２を左上とした矩形領域になる部屋集合は、｛２｝，｛２，３，４｝の２通りである。
以下に部屋番号が、ａの部屋の左に新しく部屋ｂを挿入して得られる直方体分割に対応するＯ−Ｓｅｑｕｅｎｃｅを求めるアルゴリズムを示す。
部屋ｂの右にはｈ個の部屋が隣接するものとする。
部屋ａの左に部屋を挿入するアルゴリズム
（入力；Ｏ−ＳｅｑｕｅｎｃｅＯ，部屋ｂ，部屋ａ，部屋数ｈ，
出力：Ｏ−ｓｅｑｕｅｎｃｅ  Ｏ′）
Ｏのａの直前にｂを挿入。
Ｘａ，Ｙａ，Ｚａの直後にそれぞれＸａ，Ｙａ，Ｚａを挿入
Ｚａの直後のＸ列からＸａを含めて記号Ｘをｈ個ｂの後に移動。挿入の操作を図１３に示す。
たとえば、図１１（Ａ）の直方体分割において、部屋２の左側へ部屋ｂを挿入するならば、元のＯ−ＳｅｑｕｅｎｃｅがＸ４Ｘ３Ｘ２Ｘ１Ｙ２Ｙ１Ｚ１１Ｚ３Ｚ２２Ｙ４Ｙ３３Ｚ４４なので、部屋ｂの右側にひとつ部屋が隣接する場合は、Ｘ４Ｘ３Ｘ２ＸｂＸ１Ｙ２ＸｂＹ１Ｚ１１Ｚ３ＺｂｂＺ２２Ｙ４Ｙ３３Ｚ４４となり、部屋ｂの右側に３つ部屋が隣接する場合はＸ４Ｘ３Ｘ２ＸｂＸ１Ｙ２ＸｂＹ１Ｚ１１Ｚ３ＺｂｂＺ２Ｘ４Ｘ３Ｘ２２Ｙ４Ｙ３３Ｚ４４となる。
挿入する操作事態の計算複雑度は、Ｏ（１）だが、挿入された部屋の右に隣接することができる部屋集合を列挙するのにＯ（ｎ）かかるので、部屋挿入全体で必要な計算複雑度はＯ（ｎ）である。
指定された部屋の右側、下側、奥側への部屋挿入
以下では、指定された部屋の右側に部屋を挿入する操作について述べるが、下側、奥側に挿入する操作も同様である。
部屋数ｎの直方体分割において、部屋番号１からｎの部屋番号の順序を変えずに、部屋ａの右側に新しい部屋ｂを挿入する。
部屋ｂの左面は、部屋ａの右面を含み、得られた部屋数ｎ＋１の直方体分割において、新しく挿入された部屋ｂの部屋番号は部屋ａの部屋番号の直後になるものとする。
このとき指定された部屋の左側への挿入と同様に、部屋ｂを直方体に保ったまま、部屋ｂの左側に隣接することが可能な部屋の数を求める必要がある。
部屋ａの右に隣接している壁をＷとする。Ｗは何れかの部屋の主壁か、全体直方体の外面であり、これを以下のアルゴリズムにより識別できるアルゴリズムの計算複雑度はＯ（ｎ）である。
（入力；Ｏ−ＳｅｑｕｅｎｃｅＯ，部屋ｉ
出力：部屋ｉの右面を含む壁）
ｊ＝ｉとする。
ｗｈｉｌｅ（部屋ｉの右面を含む面が未確定）｛
ｉｆ（部屋ｊの直後がＸの記号列である）
｛部屋ｉの右面は部屋ｊの主壁である）
ｅｌｓｅ  ｉｆ（ｊ＝＝ｎ）
｛部屋ｉの右面は全体直方体の右面に含まれる。｝
ｅｌｓｅ｛ｊの直後の記号Ｐａ（Ｐ∈｛Ｙ，Ｚ｝）からｊ＝ａとする｝
｝
図１５に図１４の直方体分割の部屋１の右面が含まれる壁を捜すときのアルゴリズムを簡単に示す。
ここで、以下のアルゴリズムにより壁Ｗの左に隣接する部屋集合を求めることができる。アルゴリズムの計算複雑度はＯ（ｎ）である。
入力；Ｏ−ＳｅｑｕｅｎｃｅＯ，部屋ｉ
出力：部屋ｉの主壁に右面を含まれる部屋集合Ｒ）
Ｒ＝｛ｉ｝とする。
スタックにＹｉとＺｉをｐｕｓｈする
ｗｈｉｌｅ（スタックが空でない）｛
スタックからｐｏｐされた記号をＰａ（Ｐ∈｛Ｙ，Ｚ｝）とする。
ｉｆ（記号例Ｏにおいて，Ｐａの直前が部屋番号である。）
｛直前の部屋番号ｊを部屋集合Ｒに加える。スタックにＹｊとＺｊをｐｕｓｈする。
｝
入力；Ｏ−ＳｅｑｕｅｎｃｅＯ，部屋ｉ
出力：全体直方体の右面に右面が含まれる部屋集合Ｒ）
Ｒ＝｛ｎ｝とする。
スタックにＹｎとＺｎをｐｕｓｈする
ｗｈｉｌｅ（スタックが空でない）｛
スタックからｐｏｐされた記号をＰａ（Ｐ∈｛Ｙ，Ｚ｝）とする。
ｉｆ（記号例Ｏにおいて，Ｐａの直前が部屋番号である。）
｛直前の部屋番号ｊを部屋集合Ｒに加える。スタックにＹｊとＺｊをｐｕｓｈする。
｝
図１６に図１４の直方体分割の部屋５の主壁に右面が含まれる部屋を探すとき、アルゴリズムの動作を簡単に示す。
本実施形態で設けた制約から壁Ｗは矩形であり、壁Ｗの左の部屋と隣接する領域もそれぞれ矩形である。また、部屋と隣接する領域はそれぞれ重なり合わず、壁Ｗの左に部屋と隣接しない領域はない。よって、「壁Ｗ」から「各部屋と隣接する領域」への分割はやはり、矩形分割とみなすことができる。このとき、部屋ａの右に隣接している壁Ｗについて、部屋を左側から挿入したときと同様にして壁Ｗの領域を壁Ｗの左の部屋とを隣接する領域へ分割する矩形分割と対応する、Ｑ−Ｓｅｑｕｅｎｃｅを求めることができる。ここで、部屋ａの右の壁の矩形分割において、その領域が矩形形状になる部屋集合をＯ（ｎ）時間で全列挙するアルゴリズムを示す。なお、部屋集合の矩形形状の領域において、部屋ａは常に最も右下に位置することに注意する。
矩形分割において、矩形形状となる部屋集合の列挙（ただし、部屋ａが領域の右下に位置する）
（入力：Ｑ−ＳｅｑｕｅｎｃｅＱ、部屋ａ，出力：矩形形状の領域となる部屋集合）
ｌＲ＝０、ｌＢ＝０とする。
部屋ａのＱ−Ｓｅｑｕｅｎｃｅにおける部屋番号をｔとする。
ｆｏｒ（部屋ｔから部屋番号が１となる部屋までの各部屋ｐ）｛
Ｒｐの直前のＲ列の長さに１を足したものをｋＲとする。
Ｂｐの直前のＲ列の長さに１を足したものをｋＢとする。
ｉｆ（ｌＲ≧ｔ−ｐもしくはｌＢ≧ｔ−ｐ）アルゴリズム終了
ｉｆ（ｌＲ＋ｋＢ≧ｔ−ｐかつｌＢ＋ｋＢ≧ｔ−ｐ）
｛部屋番号ｐからｔの部屋を出力｝
ｉｆ（部屋番号ｐの部屋の直前がＲ列）
｛直前のＲの数をｌＲに足す｝
ｅｌｓｅ  ｉｆ（部屋番号ｐの部屋の直前がＢ列）
｛直前のＢの数をｌＢに足す｝
｝
たとえば、図１２の矩形分割に対応するＱ−ＳｅｑｕｅｎｃｅＱ：Ｙ２Ｚ３Ｚ２２Ｙ４Ｙ３３Ｚ４４において、部屋４を右下とした矩形領域になる部屋集合は、｛４｝，｛３，４｝，｛２，３，４｝の３通りである。
以下に部屋番号がａの部屋の右に新しく部屋ｂを挿入して得られる直方体分割に対応するＯ−Ｓｅｑｕｅｎｃｅを求めうアルゴリズムを示す。部屋Ｂの左に隣接する部屋集合で、最も部屋番号が小さい部屋をｊとする。
部屋ａの左に部屋を挿入するアルゴリズム
（入力；Ｏ−ＳｅｑｕｅｎｃｅＯ，部屋ｂ，部屋ａ，部屋ｊ，
出力：Ｏ−ＳｅｑｕｅｎｃｅＯ′）
Ｏのａの直後にＸｂｂを挿入
Ｙｊ，Ｚｊの直前にそれぞれＹｂ，Ｚｂを挿入。
挿入する操作自体はＯ（１）だが、指定された部屋の右面を含む壁を捜すアルゴリズム、指定された部屋の右面を含む壁の左に隣接する部屋集合を捜すアルゴリズム、壁と隣接する領域が矩形となる部屋集合を捜すアルゴリズムはそれぞれ、Ｏ（ｎ）なので、挿入全体の計算複雑度はＯ（ｎ）である。
直方体分割Φにおいて部屋の面を含む壁の識別、壁に含まれる面を持つ部屋の識別法として以下の２つの方法を行った。
全体直方体の右側に部屋ｒｍ，ｒｍ−１，．．，ｒ１（ただし、ｒｍ＞ｒｍ−１＞・・・＞ｒ１）が隣接するときＯ′（ＷＸ）＝Ｘｒ１，・・・，Ｘｒｍ−１，Ｘｒｍとする。同様にＯ′（ＷＹ），Ｏ′（ＷＺ）を定義する。
部屋ｉ−１の主壁Ｗｉ−１がＸ軸に垂直で、部屋ｒｍ，ｒｍ−１，…．ｒ１（ただしｒｍ＞ｒｍ−１＞…＞ｒ１）の右面が主壁Ｗｉに含まれるとき．Ｏ′（ｉ）＝ｉＸｒ１・・・Ｘｒｍ−１Ｘｒｍとする。主壁Ｗｉ−１がＹ軸に垂直であるとき、Ｚ軸に垂直なときも、同様に定義する。また、Ｏ′（１）＝１とする。
Ｏ−ＳｅｑｅｎｃｅＯが示す直方体分割φについて．部屋名を保存したままＸ，Ｙ，Ｚ方向をそれぞれ逆転させた直方体分割Φ′を示すＯ−Ｓｅｑｕｅｎｃｅ（ただし部屋順序は降順）Ｏ′は以下のようになる。
Ｏ′＝Ｏ′（ＷＸ）Ｏ′（ＷＹ）Ｏ′（ＷＺ）Ｏ′（ｎ）Ｏ′（ｎ−１）・・・Ｏ′（２）Ｏ′（１）
任意の部屋について以下の条件を満たす面が識別可能である。
（ｉ）Φにおいて部屋ｉの左面を含む面
Ｘｉを含むＯ（ａ）（ただし１≦ａ＜ｎ）が存在するならば．Φにおいて部屋ｉの左面を含む面は部屋ａの主壁である。
Ｏ（ＷＸ）がＸｉを含むならば、Φにおいて部屋ｉの左面は全体直方体の片面に含まれる。
（ｉｉ）Φにおいて部屋ｉの右面を含む面
Ｘｉを含むＯ′（ａ）（ただし１≦ａ＜ｎ）が存在するならば、Φにおいて部屋ｉの右側を含む面は部屋ａ−ｉの主壁である。
Ｏ′（ＷＸ）がＸｉを含むならは、Φにおいて部屋ｉの右面は全体直方体の右面に含まれる。
（ｉ〉．（ｉｉ）はＹ，Ｚ方向についても同様である。
任意の面について以下の条件を満たす部屋が識別可能である。
（ｉ）Φにおいて全体直方体の左面に左面が含まれる部屋
Ｏ（ＷＸ）＝Ｘｒｍ・・・Ｘｒ２Ｘｒ１よりΦにおいて全体直方体の左面に左面が含まれる部屋はｒ１，ｒ２，・・・，ｒｍである。
（ｉｉ）Φにおいて全体直方体の右面に右面が含まれる部屋
Ｏ′（Ｗｘ）＝Ｘｒｎ・・・Ｘｒ２Ｘｒ１よりΦにおいて全体直方体の右面に右面が含まれる部屋はｒ１，ｒ２，・・・，ｒ２である。
（ｉｉｉ）Φにおいて部屋ｉ（ただし、１≦ａ＜ｎ）の主壁がＸ軸に垂直なとき、部屋１の主壁に左面が含まれる部屋。
Φにおいて部屋ｉの主壁がＸ軸に垂直なとき、Ｏ（ｉ）＝ｉＸｒｎ・・・Ｘｒ２Ｘｒ１であり、部屋ｉの主壁に左面が含まれる部屋はｒ１，ｒ２，・・・，ｒｎである。
（ｉｖ）Φにおいて部屋ｒ（ただし１≦ａ＜ｎ）の主壁がＸ軸に垂直なとき、部屋ｉの主壁に右面が含まれる部屋
Φにおいて部屋ｉの上壁がＸ軸に垂直なとき、Ｏ′（ｉ＋１）＝ｉ＋１Ｘｒｍ・・・Ｘｒ２Ｘｒ１であり、部屋ｉの主壁に右面が含まれる部屋ｉの主壁に右面が含まれる部屋はｒ１，ｒ２，・・・，ｒｎである。
（ｉ），（ｉｉ），（ｉｉｉ），（ｖｉ）はＹ，Ｚ方向についても同様である。
ＹＺ方向についても同様である。
Ｏ−Ｓｑｕｅｎｃｅのデコード、エンコード時間はそれぞれ線形時間なので、任意の部屋の面を含む分割面、任意の分割面に含まれる部屋はそれぞれ線形時間で求められる。
Ｏ−Ｓｅｑｕｅｎｃｅコードからの識別について説明する。
任意の部屋について以下の条件を満たす面が識別可能である。
（ｉ）Φにおいて部屋ｉの左面を含む面。
（ｉｉ）Φにおいて部屋ｉの右面を含む面
以下のアルゴリズムにより識別できる．
入力：Ｏ−Ｓｅｑｕｅｎｃｅ，部屋ｉ
出力：部屋ｉの右面を含む壁）
ｊ＝ｉとする。
ｗｈｉｌｅ（部屋ｉの右面を含む面が未確定である）｛
ｉｆ（部屋ｊの直後がＸの記号例である）
｛部屋ｉの右面は部屋ｊの主壁である。
ｅｌｓｅ  ｉｆ（ｉ＝＝ｎ）
｛部屋ｉの右面は全体直方体の右面に含まれる。｝
ｅｌｓｅ｛ｊの直後の記号Ｐａ（Ｐ∈｛Ｙ，Ｚ｝）から、ｊ＝ａとする。｝
｝
図１７に図１４の直方体分割の部屋５の主壁に右面が隣接する部屋を捜すときのアルゴリズムの動作を簡単に示す。
（ｉ）．（ｉｉ）．（ｉｉｉ）．（ｖｉ）はＹ，Ｚ方向についても同様である。
Ｙ，Ｚ方向についても同様である。
前述のアルゴリズムを用いて任意の部屋の面を含む分割面、任意の分割面に含まれる部屋はそれぞれ線形時間で求められる。
【産業上の利用可能性】
【０００６】
本発明の手法をＳＡ法に組み込んで矩形分割面によって分割された直方体分割に基づいた体積最小の直方体パッキングを探索できることを確かめた。各辺の長さが５〜２０までの整数値としてランダムに生成された直方体３０個の集合を入力とし、初期温度と終了温度を事前実験により適切に定めて固定して、３．２ＧＨｚのマイクロプロセッサを用いて、３７５秒で体積比１１３パーセントのパッキングを得た。体積比とは各直方体の体積の総和によって全体直方体の体積を割った値である。
本発明では、分割面が矩形形状である任意の直方体分割構造をコード化できる。計算機上でそのような直方体分割構造を容易に扱えるようにできる。任意に作成したコードでも．必要十分条件を満たせば直方体分割に復元可能である。コードから任意の部屋こ接する面、任意の面に接する部屋を容易に特定できる。これは配線領域の特定や配線検討工程を容易にする。
【図１】
0005124777.tif 000002
【図２】
0005124777.tif 000003
【図３】
0005124777.tif 000004
【図４】
0005124777.tif 000005
【図５】
0005124777.tif 000006
【図６】
0005124777.tif 000007
【図７】
0005124777.tif 000008
【図８】
0005124777.tif 000009
【図９】
0005124777.tif 000010
【図１０】
0005124777.tif 000011
【図１１】
0005124777.tif 000012
【図１２】
0005124777.tif 000013
【図１３】
0005124777.tif 000014
【図１４】
0005124777.tif 000015
【図１５】
0005124777.tif 000016
【図１６】
0005124777.tif 000017
【図１７】
0005124777.tif 000018