(57)【要約】【課題】詰め込み物の詰め込み可能性の判断を高速に行う技術を提供する。【解決手段】詰め込み支援装置１０において，二分決定グラフ情報記憶部１３には，制約情報記憶部１２に記憶された詰め込み可能な詰め込み物の数の組合せの制約から，生成部１１によって生成された，詰め込み可能な詰め込み物の数の組合せの制約を展開した，詰め込み物の数の組合せパタンの集合を表す二分決定グラフが記憶されている。取得部１４は，ユーザにより指定された詰め込み物の数の組合せパタンを取得する。判定部１５は，二分決定グラフ情報記憶部１３に記憶された二分決定グラフを用いた探索により，取得部１４が取得した詰め込み物の数の組合せパタンが詰め込み可能であるか否かを判定する。【選択図】図１
2014029622.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに，
ユーザにより指定された，詰め込み物の数の組合せパタンを取得し，
詰め込み可能な詰め込み物の数の組合せの制約を展開した，詰め込み物の数の組合せの集合を表す二分決定グラフを用いた探索により，前記取得した詰め込み物の数の組合せパタンが詰め込み可能であるか否かを判定する
処理を実行させるための詰め込み支援プログラム。
【請求項２】
前記コンピュータに，さらに，
前記取得した詰め込み物の数の組合せパタンが詰め込み不可能と判定された場合に，前記二分決定グラフを用いた探索により，前記取得した詰め込み物の数の組合せパタンにおける詰め込み物の数の制限内で，所定の目的とする値の最大値が得られる詰め込み物の数の組合せパタンを抽出する
処理を実行させるための請求項１に記載の詰め込み支援プログラム。
【請求項３】
ユーザにより指定された，詰め込み物の数の組合せパタンを取得する取得部と，
詰め込み可能な詰め込み物の数の組合せの制約を展開した，詰め込み物の数の組合せの集合を表す二分決定グラフを用いた探索により，前記取得した詰め込み物の数の組合せパタンが詰め込み可能であるか否かを判定する判定部とを備える
ことを特徴とする詰め込み支援装置。
【請求項４】
コンピュータが，
ユーザにより指定された，詰め込み物の数の組合せパタンを取得し，
詰め込み可能な詰め込み物の数の組合せの制約を展開した，詰め込み物の数の組合せの集合を表す二分決定グラフを用いた探索により，前記取得した詰め込み物の数の組合せパタンが詰め込み可能であるか否かを判定する
ことを特徴とする詰め込み支援方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，物品等の詰め込み可能性の判断を支援する詰め込み支援プログラム，詰め込み支援装置および詰め込み支援方法に関するものである。
【背景技術】
【０００２】
手元にある物品を入れ物に詰め込むことができるか，どれだけの物品を入れ物に詰め込むことができるのかなどを判断するケースがある。以下では，詰め込む物品を詰め込み物とも呼び，詰め込み物を入れる入れ物を詰め込み先とも呼ぶ。例えば，配送計画では，手元にある荷物などの詰め込み物を運搬車やコンテナなどの詰め込み先に詰め込み可能であるか，どのぐらいの荷物なら詰め込み可能であるかなどを判断する。
【０００３】
詰め込み先である入れ物に対して，詰め込み物である物品が詰め込み可能であるかを判断する問題として，詰め込み先であるナップサックに対して，詰め込み物である荷物を詰め込むナップサック問題がある。ナップサックに詰め込むことができる荷物の総重量には，制限があるものとする。また，詰め込みを判断する対象の荷物はＮ個あり，各荷物には重量と価値とが与えられているものとする。このとき，重さの合計がナップサックに詰め込める荷物の重量制限を越えない範囲で，価値の合計が最大となる荷物の組合せを求める問題が，ナップサック問題である。ナップサック問題では，ナップサックに詰め込み可能な荷物の組合せを，簡単な条件式で表すことができる。
【０００４】
なお，正規表現を０抑制型二分決定グラフ（ＺＤＤ：Zero-suppressed Binary Decision Diagrams）で表現して処理する技術が知られている。また，二分決定グラフ（ＢＤＤ：Binary Decision Diagram ）と充足可能性検査（ＳＡＴ：Satisfiability Testing）の両方を組み合わせて，有限状態機械の状態数え上げを行う技術が知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平８−２４９３６３号公報
【特許文献２】特開２００４−２８８２０４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし，実際に詰め込み可能性の判断を行う場合には，詰め込み物の大きさや重さなどの単純計算だけでは，詰め込み物の詰め込み可能性を判断できないケースも多い。例えば，トラックなどの運搬車で荷物を配送する場合において，荷物の大きさや重量だけではなく，荷物の形状や性質なども考慮して，その荷物の運搬車への詰め込み可能性を判断しなければならないケースもある。
【０００７】
このようなケースでは，詰め込み可能な詰め込み物の組合せを，重さ何キロ以下といったような単純な条件式ではなく，詰め込み可能な詰め込み物の組合せの制約の集合で表す必要がある。例えば，Ａ，Ｂ，Ｃの三種類の荷物がある場合に，「Ａが３個以下，Ｂが７個以下，Ｃが５個以下の組合せなら詰め込み可能」，または「Ａが１個以下，Ｂが１０個以下，Ｃが６個以下の組合せなら詰め込み可能」といった荷物の組合せパタンの制約の集合で，詰め込み可能な荷物の組合せを表すことになる。
【０００８】
例えば，荷物の配送計画などでは，詰め込み可能な荷物の組合せの制約の集合が，数百〜数千の組合せの制約の集合からなるケースも考えられる。現在手元にある荷物の組合せが詰め込み可能であるか否かを判断する際に，すべての詰め込み可能な荷物の組合せの制約についてチェックすると，その処理に膨大な時間がかかる。
【０００９】
一側面では，本発明は，詰め込み物の詰め込み可能性の判断を高速に行う技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
１態様では，開示するプログラムは，コンピュータを次のように機能させる。すなわち，前記プログラムは，前記プログラムがインストールされて実行されるコンピュータに，ユーザにより指定された，詰め込み物の数の組合せパタンを取得し，詰め込み可能な詰め込み物の数の組合せの制約を展開した，詰め込み物の数の組合せの集合を表す二分決定グラフを用いた探索により，前記取得した詰め込み物の数の組合せパタンが詰め込み可能であるか否かを判定する処理を実行させる。
【発明の効果】
【００１１】
１態様では，詰め込み物の詰め込み可能性の判断を高速に行うことが可能となる。
【図面の簡単な説明】
【００１２】
【図１】本実施の形態による詰め込み支援装置の構成例を示す図である。
【図２】本実施の形態による詰め込み支援装置を実現するコンピュータのハードウェア構成例を示す図である。
【図３】二分決定グラフの例を説明する図である。
【図４】本実施の形態による（ｘ11ｘ10）＝（０１）が真となるＢＤＤを生成する例を説明する図である。
【図５】本実施の形態による荷物＃１についての制約を表すＢＤＤを生成する例を説明する図である。
【図６】本実施の形態による組合せパタン制約を表すＢＤＤを生成する例を説明する図である。
【図７】本実施の形態による展開パタン集合ＢＤＤの例を示す図である。
【図８】本実施の形態による展開パタン集合ＢＤＤデータの例を示す図である。
【図９】本実施の形態の詰め込み支援装置による展開パタン集合ＢＤＤ生成処理フローチャートである。
【図１０】本実施の形態による展開パタン集合ＢＤＤを用いた積み込み可能判定の例を説明する図である。
【図１１】本実施の形態の詰め込み支援装置による積み込み可能性判定処理フローチャートである。
【図１２】本実施の形態の詰め込み支援装置の判定部によるＢＤＤ探索判定処理フローチャートである。
【図１３】本実施の形態による層と重みを説明する図である。
【図１４】本実施の形態による最適パタン抽出の例を説明する図である。
【図１５】本実施の形態による最適パタン抽出の例を説明する図である。
【図１６】本実施の形態による最適パタン抽出の例を説明する図である。
【図１７】本実施の形態による最適パタン抽出の例を説明する図である。
【図１８】本実施の形態の詰め込み支援装置による最適パタン抽出処理フローチャートである。
【図１９】本実施の形態の詰め込み支援装置の抽出部による最適パタン取得処理フローチャートである。
【図２０】本実施の形態の詰め込み支援装置の抽出部による層探索処理フローチャートである。
【発明を実施するための形態】
【００１３】
以下，本実施の形態について，図を用いて説明する。
【００１４】
図１は，本実施の形態による詰め込み支援装置の構成例を示す図である。
【００１５】
図１に示す詰め込み支援装置１０は，詰め込み先への詰め込み物の詰め込み可能性の判断を行う。詰め込み支援装置１０は，生成部１１，制約情報記憶部１２，二分決定グラフ情報記憶部１３，取得部１４，判定部１５，抽出部１６，出力部１７を備える。
【００１６】
生成部１１は，詰め込み可能な詰め込み物の数の組合せの制約を展開した，詰め込み物の数の組合せパタンの集合を表す二分決定グラフを生成する。制約情報記憶部１２は，詰め込み可能な詰め込み物の数の組合せの制約の情報を記憶する記憶部である。二分決定グラフ情報記憶部１３は，生成部１１により生成された二分決定グラフの情報を記憶する記憶部である。
【００１７】
取得部１４は，ユーザにより指定された，詰め込み物の数の組合せパタンを取得する。判定部１５は，二分決定グラフを用いた探索により，取得部１４が取得した詰め込み物の数の組合せパタンが詰め込み可能であるか否かを判定する。抽出部１６は，判定部１５により詰め込み可能でないと判定された場合に，二分決定グラフ情報記憶部１３に記憶された二分決定グラフを用いた探索により，取得した詰め込み物の数の組合せパタンにおける詰め込み物の数の制限内で，所定の目的とする値の最大値が得られる詰め込み物の数の組合せパタンを抽出する。出力部１７は，判定部１５による詰め込み可能であるか否かの判定結果を出力する。また，出力部１７は，抽出部１６による詰め込み物の数の組合せパタンの抽出結果を出力する。
【００１８】
図２は，本実施の形態による詰め込み支援装置を実現するコンピュータのハードウェア構成例を示す図である。
【００１９】
図１に示す本実施の形態の詰め込み支援装置１０を実現するコンピュータ１は，例えば，ＣＰＵ（Central Processing Unit ）２，主記憶となるメモリ３，記憶装置４，通信装置５，媒体読取・書込装置６，入力装置７，出力装置８等を備える。記憶装置４は，例えばＨＤＤ（Hard Disk Drive ）等の外部記憶装置や，補助記憶装置などである。媒体読取・書込装置６は，例えばＣＤ−Ｒ（Compact Disc Recordable ）ドライブやＤＶＤ−Ｒ（Digital Versatile Disc Recordable ）ドライブなどである。入力装置７は，例えばキーボード・マウス等の入力機器などである。出力装置８は，例えばディスプレイ等の表示装置などである。
【００２０】
図１に示す詰め込み支援装置１０および詰め込み支援装置１０が備える各機能部は，コンピュータ１が備えるＣＰＵ２，メモリ３等のハードウェアと，ソフトウェアプログラムとによって実現することが可能である。コンピュータ１が実行可能なプログラムは，記憶装置４に記憶され，その実行時にメモリ３に読み出され，ＣＰＵ２により実行される。
【００２１】
コンピュータ１は，可搬型記録媒体から直接プログラムを読み取り，そのプログラムに従った処理を実行することもできる。また，コンピュータ１は，サーバコンピュータからプログラムが転送されるごとに，逐次，受け取ったプログラムに従った処理を実行することもできる。さらに，このプログラムは，コンピュータ１で読み取り可能な記録媒体に記録しておくことができる。
【００２２】
以下，本実施の形態の詰め込み支援装置１０による詰め込み支援処理について，より具体的な例を用いて説明する。なお，以下の説明では，配送計画における，運搬車やコンテナへの荷物の積み込み可能性を判断する例を用いるものとする。以下の例では，詰め込み物は配送する荷物となり，詰め込み先は荷物を配送する運搬車やコンテナとなる。詰め込みは，積み込みとなる。
【００２３】
本実施の形態による詰め込み支援装置１０では，積み込み可能な荷物の数の組合せの制約の集合を，二分決定グラフで表現する。以下では，二分決定グラフを，ＢＤＤ（Binary Decision Diagram ）とも呼ぶ。
【００２４】
図３は，二分決定グラフの例を説明する図である。
【００２５】
図３（Ａ）は，場合分け二分木の例を示す。図３（Ａ）において，ａ，ｂ，ｃは，それぞれ０または１の値をとる２値変数である。丸枠と四角枠は，ノードを示す。一番上のノードが根ノードであり，四角枠のノードが葉ノードである。葉ノードを示す四角枠内は真偽値を示し，１が真，０が偽を示すものとする。以下では，値が１の葉ノードを１葉とも呼び，値が０の葉ノードを０葉とも呼ぶ。ノード間を結ぶ矢印の枝の数値は，変数の値を示す。以下では，値が１の枝を１枝とも呼び，値が０の枝を０枝とも呼ぶ。矢印の枝で結ばれたノード間には親子関係があり，矢印の元のノードを親ノード，矢印の先のノードを子ノードと呼ぶ。
【００２６】
図３（Ｂ）は，二分決定グラフの例を示す。図３（Ｂ）に示す二分決定グラフすなわちＢＤＤは，図３（Ａ）に示す場合分け二分木を圧縮表現したものである。場合分け二分木は，次の２つの規則に従って圧縮表現できる。
（１）同型的なサブグラフがある場合，そのサブグラフをマージして表現する（共有化）。
（２）２つの子ノードが同型的であるノードがある場合，そのノードを省略する（非冗長化）。２つの子ノードが同型的であるノードは，冗長ノードとも呼ばれる。
【００２７】
これらの規則に基づいて，図３（Ａ）に示す場合分け二分木を圧縮表現すると，図３（Ｂ）に示すＢＤＤが得られる。本実施の形態では，このようなＢＤＤを用いることで，積み込み可能な荷物の数の組合せの制約の集合を，効率的に表現することが可能となる。
【００２８】
また，ＢＤＤでは，圧縮表現したままで，論理積や論理和，否定などの演算を超高速に行うことができる。本実施の形態では，例えば，積み込み可能な荷物の数の組合せの制約ごとにＢＤＤを生成し，それらの制約ごとのＢＤＤの論理和を求めることで，高速に積み込み可能な荷物の数の組合せの制約の集合を表すＢＤＤを求めることができる。
【００２９】
なお，ＢＤＤに関する技術が記載された文献としては，例えば参考文献１や参考文献２などが挙げられる。
〔参考文献１〕
R.E.Bryant，“Graph-Based Algorithms for Boolean Function Manipulation，”IEEE Trans. Comput. ，Vol. C-35, No. 8, pp. 677-691 （Aug. 1986 ）
〔参考文献２〕
S.Minato，“Zero-suppressed BDDs for set manipulation in combinatorial problems ，”Proc. 30th ACM/IEEE Design Automation Conf. ，pp272-277 （1993）
参考文献１には，場合分け二分木を経ずに，効率的にＢＤＤ同士の演算を行う技術が記載されている。
【００３０】
また，参考文献２には，疎な集合を表現する場合にＢＤＤより少ないノード数で表現することができるＺＤＤ（Zero-suppressed Binary Decision Diagrams）の技術が記載されている。なお，ＢＤＤとＺＤＤとの違いは，冗長ノードの定義部分のみである。ＢＤＤにおける冗長ノードが０枝と１枝の子ノードが同一なものであるのに対し，ＺＤＤの冗長ノードは１枝の子ノードが０葉であるものとなる。
【００３１】
本実施の形態の詰め込み支援装置１０において，生成部１１は，制約情報記憶部１２に記憶された積み込み可能な荷物の数の組合せの制約の集合から，積み込み可能な荷物の数の組合せの制約の集合を表すＢＤＤを生成する。以下では，積み込み可能な荷物の数の組合せの制約を，組合せパタン制約と呼ぶ。
【００３２】
ここで，荷物＃１，荷物＃２の二種類の荷物があるとし，荷物＃１の個数を示す変数をＸ1 ，荷物＃２の個数を示す変数をＸ2 とする。制約情報記憶部１２には，これらの荷物についての組合せパタン制約が記憶されている。
【００３３】
ここでは，荷物＃１，荷物＃２についての組合せパタン制約を，（Ｘ1 の制限数，Ｘ2 の制限数）で表すものとする。このとき，例えば，（０，３），（１，２），（２，１），（０，３）で表される４つの組合せパタン制約が，制約情報記憶部１２に記憶されているものとする。組合せパタン制約（１，２）は，「Ｘ1 ≦１，かつＸ2 ≦２」であること，すなわち「荷物＃１が１個以下で，かつ荷物＃２が２個以下であれば積み込み可能」であることを示している。
【００３４】
なお，本実施の形態では，同じ種類の荷物が複数個ある状況を想定している。荷物の配送では，同じ製品の荷物など，同じ種類の複数個の荷物を配送するケースも多々ある。大きさや重さ，形状，性質などがまったく同じ荷物のみを同じ種類の荷物としてもよいし，大きさや重さ，形状，性質などが多少異なっていても，積み込み可能性を判断する上で同じ扱いをできる荷物を同じ種類の荷物に分類するようにしてもよい。
【００３５】
生成部１１は，組合せパタン制約ごとに，組合せパタン制約のＢＤＤを生成する。上記のように，組合せパタン制約では，積み込み可能な各荷物の数の組合せが不等式で表される条件で制約されている。ＢＤＤでは，直接に不等式を表現できないので，組合せパタン制約は，積み込み可能な各荷物の数の組合せが等式で表される組合せパタンの集合に展開されて表現される。例えば，組合せパタン制約（１，２）は，「（Ｘ1 ＝０またはＸ1 ＝１）かつ（Ｘ2 ＝０またはＸ2 ＝１またはＸ2 ＝２）」と表すことができるので，２×３＝６個の組合せパタンからなる集合に展開できる。
【００３６】
また，ＢＤＤでは，ノードの各変数の値が，０，１の２値となる。本実施の形態では，各荷物の個数を，二進数の各桁を表す変数を用いて表す。以下では，桁を表す変数を，桁変数とも呼ぶ。例えば，荷物＃２の個数Ｘ2 が２個である場合，その個数を二進数で表すと，“１０”と表せる。この場合，２桁目に桁変数ｘ21，１桁目に桁変数ｘ20を割り当てると，ｘ21＝１，ｘ20＝０となる。このように，十進数の変数Ｘ2 を二進数の桁変数ｘ21，ｘ20で表すことが可能である。このような二進数の桁変数を用いれば，積み込み可能な荷物の組合せパタンをＢＤＤで表すことができる。
【００３７】
生成部１１は，荷物の種類ごとに，組合せパタン制約で制約された個数の最大値を求める。例えば，上記の４つの組合せパタン制約の例では，荷物＃１について制約された個数の最大値は３であり，荷物＃２について制約された個数の最大値は３である。
【００３８】
生成部１１は，荷物の種類ごとに，組合せパタン制約で制約された個数の最大値を二進数で表したときの桁数を求め，その桁数分の変数を設定する。最大値を二進数で表したときの桁数は，ｌｏｇ2 （最大値＋１）で求められる。ここでは，荷物＃１，荷物＃２ともに個数の最大値が３であるので，最大値を二進数で表したときの桁数は，それぞれｌｏｇ2 （３＋１）＝２となる。生成部１１は，荷物＃１，荷物＃２について，それぞれ２つの桁変数を設定する。例えば，生成部１１は，荷物＃１について，個数の二進数表現における１桁目を表す桁変数をｘ10，２桁目を現す桁変数をｘ11と設定する。また，生成部１１は，荷物＃２について，個数の二進数表現における１桁目を表す桁変数をｘ20，２桁目を現す桁変数をｘ21と設定する。
【００３９】
生成部１１は，組合せパタン制約ごとのＢＤＤを生成する。生成部１１は，例えば，荷物＃１についての制約を表すＢＤＤと，荷物＃２についての制約を表すＢＤＤとをそれぞれ生成し，それらのＢＤＤの論理積を求めることで，組合せパタン制約を表すＢＤＤを生成する。
【００４０】
ここでは，組合せパタン制約（１，２）を表すＢＤＤを生成する例を説明する。上述したように，組合せパタン制約（１，２）は，「（Ｘ1 ＝０またはＸ1 ＝１）かつ（Ｘ2 ＝０またはＸ2 ＝１またはＸ2 ＝２）」であることを表している。このとき，荷物＃１についての制約は，「Ｘ1 ＝０またはＸ1 ＝１」となり，荷物＃２についての制約は，「Ｘ2 ＝０またはＸ2 ＝１またはＸ2 ＝２」となる。
【００４１】
荷物＃１についての制約を表すＢＤＤを生成する第一の例を説明する。この第一の例では，生成部１１は，制約下で荷物＃１の個数が取り得る値について，それぞれの値が真となるＢＤＤを生成し，それらのＢＤＤの論理和を求めることで，荷物＃１についての制約を表すＢＤＤを生成する。
【００４２】
荷物＃１についての制約は「Ｘ1 ＝０またはＸ1 ＝１」であるので，それぞれを二進数で表すと荷物＃１についての制約を二進数表現すると“００”，“０１”となる。これらの二進数表現を，それぞれの桁変数に割り当てると，荷物＃１についての制約は，「（ｘ11ｘ10）＝（００）または（ｘ11ｘ10）＝（０１）」となる。なお，本実施の形態の例では，個数を二進数の桁変数で表す場合において，「ｘ11＝０かつｘ10＝１」を（ｘ11ｘ10）＝（０１）と表すものとする。生成部１１は，（ｘ11ｘ10）＝（００）が真となるＢＤＤと，（ｘ11ｘ10）＝（０１）が真となるＢＤＤとをそれぞれ生成する。
【００４３】
生成部１１は，桁変数ごとに，それぞれの桁変数の値が真となるＢＤＤを生成し，それらのＢＤＤの論理積を求めることで，制約下で荷物＃１の個数が取り得る値が真となるＢＤＤを生成する。桁変数ごとのＢＤＤは，例えば次の手順で生成できる。
（１）桁変数の値が１である場合
生成部１１は，桁変数のノードの１枝の子ノードが，真を示す１葉のノードとなるＢＤＤを生成する。
（２）桁変数の値が０である場合
生成部１１は，桁変数のノードの１枝の子ノードが，真を示す１葉のノードとなるＢＤＤを生成する。生成されたＢＤＤの否定を求めて，目的とする，桁変数のノードの０枝の子ノードが真を示す１葉のノードとなるＢＤＤを生成する。
【００４４】
図４は，本実施の形態による（ｘ11ｘ10）＝（０１）が真となるＢＤＤを生成する例を説明する図である。
【００４５】
ここで，図４を用いて，（ｘ11ｘ10）＝（０１）が真となるＢＤＤを生成する例を説明する。ｘ10＝１であるので，生成部１１は，図４右上に示すように，ｘ10＝１が真となるＢＤＤを生成する。
【００４６】
ｘ11＝０が真となるＢＤＤについては，生成部１１は，まず，図４左上に示すｘ11＝１が真となるＢＤＤを生成する。生成部１１は，図４左上に示すｘ11＝１が真となるＢＤＤに対するＮＯＴ演算により，図４左中に示すｘ11＝０が真となるＢＤＤを生成する。ＮＯＴ演算は，ＢＤＤの否定を求める演算である。
【００４７】
生成部１１は，図４左中に示すｘ11＝０が真となるＢＤＤと，図４右上に示すｘ10＝１が真となるＢＤＤとのＡＮＤ演算により，図４下に示す（ｘ11ｘ10）＝（０１）が真となるＢＤＤを生成する。ＡＮＤ演算は，ＢＤＤとＢＤＤとの論理積を求める演算である。
【００４８】
図４に示す手順と同様の手順で，（ｘ11ｘ10）＝（００）が真となるＢＤＤも生成できる。生成部１１は，（ｘ11ｘ10）＝（００）が真となるＢＤＤと，（ｘ11ｘ10）＝（０１）が真となるＢＤＤとのＯＲ演算により，荷物＃１についての制約を表すＢＤＤを生成する。ＯＲ演算は，ＢＤＤとＢＤＤとの論理和を求める演算である。
【００４９】
ここまで説明した，荷物＃１についての制約を表すＢＤＤを生成する第一の例では，制約下で荷物＃１の個数が取り得る値の数だけそのＢＤＤを生成し，それらのＢＤＤの論理和を求めている。この第一の例では，制約下で荷物＃１の個数が取り得る値の数が多くなると，ＯＲ演算やＡＮＤ演算の実行回数が膨大な回数となってしまう。
【００５０】
以下では，荷物＃１についての制約を表すＢＤＤを生成する第二の例を説明する。この第二の例では，ある桁以下のすべての桁で０と１の値を取り得る場合に，それらの桁変数について，１度の演算でまとめて行えるようにする。この第二の例は，例えば次の手順で行われる。
（１）生成部１１は，恒偽のＢＤＤと，恒真のＢＤＤとを生成する。ここでは，恒偽のＢＤＤをＡｃｃと呼び，恒真のＢＤＤをＰｒｅと呼ぶものとする。
（２）生成部１１は，組合せ制約パタンにおける荷物＃１についての制約を示す値を二進数表現した各桁変数の値に対して，最上位の桁変数から順に，次の処理を行う。なお，組合せ制約パタンにおける荷物＃１についての制約を示す値は，該当組合せ制約パタンの制約下で荷物＃１の個数が取り得る最大の値である。
（ａ）現在の処理対象の桁変数の値が１である場合
（ｉ）現在の処理対象の桁より下の桁変数の値がすべて１であれば，それらの桁変数の値は，すべて０と１の両方の値を取り得る。このとき，生成部は，その時点のＡｃｃとＰｒｅのＯＲ演算を行い，結果をＡｃｃに代入する。この場合，生成部１１は，この時点で処理を終了する。終了時点でのＡｃｃが，荷物＃１についての制約を表すＢＤＤである。
（ii）現在の処理対象の桁より下の桁変数の値に０が含まれていれば，生成部１１は，現在の桁変数の値が１で真となるＢＤＤにＮＯＴ演算を施したＢＤＤとその時点のＰｒｅとのＡＮＤ演算を行った結果のＢＤＤと，その時点のＡｃｃとのＯＲ演算を行い，結果をＡｃｃに代入する。さらに，生成部１１は，その時点のＰｒｅと現在の桁変数の値が１で真となるＢＤＤとのＡＮＤ演算を行い，結果をＰｒｅに代入する。
（ｂ）現在の処理対象の桁変数の値が０である場合
生成部１１は，現在の桁変数の値が１で真となるＢＤＤにＮＯＴ演算を施したＢＤＤの結果と，その時点のＰｒｅとのＡＮＤ演算を行い，結果をＰｒｅに代入する。
（ｃ）最下位の桁まで処理が終わった場合
生成部１１は，その時点のＡｃｃとＰｒｅのＯＲ演算を行い，結果をＡｃｃに代入して，処理を終了する。終了時点でのＡｃｃが，荷物＃１についての制約を表すＢＤＤである。
【００５１】
図５は，本実施の形態による荷物＃１についての制約を表すＢＤＤを生成する例を説明する図である。
【００５２】
ここで，図５を用いて，上述の第二の例に示す手順で，組合せパタン制約（１，２）における荷物＃１についての制約を表すＢＤＤを生成する例を説明する。組合せ制約パタンにおける荷物＃１についての制約を示す値は１であり，それを二進数表現した各桁変数の値は，（ｘ11ｘ10）＝（０１）となる。生成部１１は，準備として，図５の上段に示すように，恒偽のＢＤＤであるＡｃｃと，恒真のＢＤＤであるＰｒｅとを生成する。
【００５３】
まず，生成部１１は，最上位の桁変数ｘ11を処理対象とする。ｘ11＝０であるので，生成部１１は，上述の第二の例に示す手順（２）の（ｂ）に従って，図５の中段に示すように，ｘ11＝１が真となるＢＤＤに対してＮＯＴ演算を行い，結果として得られるｘ11＝０が真となるＢＤＤと，その時点のＰｒｅとのＡＮＤ演算を行い，結果をＰｒｅに代入する。
【００５４】
次に，生成部１１は，変数ｘ10を処理対象とする。ｘ10＝１であり，それより下の桁がないので，生成部１１は，上述の第二の例に示す手順（２）の（ａ）（ｉ）に従って，その時点のＡｃｃとＰｒｅのＯＲ演算を行い，結果をＡｃｃに代入する。図５の下段に示すように，ここで得られるＡｃｃが，荷物＃１についての制約を表すＢＤＤである。
【００５５】
このように，上述の第二の例に示す手順で荷物＃１についての制約を表すＢＤＤの生成を行えば，少ない演算回数で，目的とするＢＤＤが得られる。図５に示す手順と同様の手順で，荷物＃２についての制約を表すＢＤＤも生成できる。生成部１１は，荷物＃１についての制約を表すＢＤＤと荷物＃２についての制約を表すＢＤＤとの論理積を求めることで，組合せパタン制約を表すＢＤＤを生成する。
【００５６】
図６は，本実施の形態による組合せパタン制約を表すＢＤＤを生成する例を説明する図である。
【００５７】
生成部１１は，図６に示すように，例えば図５に示す手順で生成される荷物＃１についての制約を表すＢＤＤと，同様の手順で生成される荷物＃２についての制約を表すＢＤＤとのＡＮＤ演算を行うことにより，組合せパタン制約（１，２）を表すＢＤＤを生成する。生成部１１は，他の組合せパタン制約（０，３），（２，１），（０，３）についても，組合せパタン制約（１，２）を表すＢＤＤと同様に，組合せパタン制約を表すＢＤＤを生成できる。
【００５８】
生成部１１は，すべての組合せパタン制約を表すＢＤＤの論理和を求めて，組合せパタン制約の集合を積み込み可能な組合せパタンに展開したＢＤＤを生成する。以下では，組合せパタン制約の集合を積み込み可能な組合せパタンに展開したＢＤＤを，展開パタン集合ＢＤＤと呼ぶ。
【００５９】
図７は，本実施の形態による展開パタン集合ＢＤＤの例を示す図である。
【００６０】
図７に示す展開パタン集合ＢＤＤは，上記の組合せパタン制約の集合（０，３），（１，２），（２，１），（０，３）から生成された展開パタン集合ＢＤＤである。図７に示す展開パタン集合ＢＤＤにおいて，各ノードの横に示される＃付きの数字は，ノードＩＤを示す。ノードＩＤは，展開パタン集合ＢＤＤの各ノードを一意に識別する識別情報である。
【００６１】
変数番号は，桁変数ごとに割り当てられる識別番号である。図７に示す例では，変数ｘ11に変数番号１，変数ｘ10に変数番号２，変数ｘ21に変数番号３，変数ｘ20に変数番号４が割り当てられている。なお，展開パタン集合ＢＤＤのデータ扱い上の問題で，変数ではない葉ノードにも，変数番号０が割り当てられている。
【００６２】
図８は，本実施の形態による展開パタン集合ＢＤＤデータの例を示す図である。
【００６３】
図８に示す展開パタン集合ＢＤＤデータ１３０は，生成部１１により生成され，二分決定グラフ情報記憶部１３に記憶される展開パタン集合ＢＤＤのデータの一例を示す。特に，図８に示す展開パタン集合ＢＤＤデータ１３０は，図７に示す展開パタン集合ＢＤＤについて，コンピュータの処理で扱われる形式で表したデータの一例となる。なお，図８に示す展開パタン集合ＢＤＤデータ１３０では，テーブルデータとは別に，該当展開パタン集合ＢＤＤにおける根ノードのノードＩＤが保持されている。
【００６４】
図８に示す展開パタン集合ＢＤＤデータ１３０におけるノードＩＤは，図７に示す展開パタン集合ＢＤＤの各ノードに割り当てられたノードＩＤに対応する。図８に示す展開パタン集合ＢＤＤデータ１３０における変数番号は，図７に示す展開パタン集合ＢＤＤの各桁変数に割り当てられた変数番号に対応する。図８に示す展開パタン集合ＢＤＤデータ１３０における１つのレコードは，それぞれ図７に示す展開パタン集合ＢＤＤにおける１つのノードに１対１で対応する。
【００６５】
図８に示す展開パタン集合ＢＤＤデータ１３０において，０枝の子ノード項目には，該レコードのノードからその０枝の子ノードへのポインタ情報として，該当子ノードのノードＩＤが記録されている。また，図８に示す展開パタン集合ＢＤＤデータ１３０において，１枝の子ノード項目には，該レコードのノードからその１枝の子ノードへのポインタ情報として，該当子ノードのノードＩＤが記録されている。なお，０葉および１葉の葉ノードのレコードについては，０枝の子ノード項目と１枝の子ノード項目に，ポインタ情報ではなく，それぞれ偽真を示す０または１の値が記録されている。
【００６６】
このように，本実施の形態による詰め込み支援装置１０では，組合せパタン制約の集合をＢＤＤで表すことにより，組合せパタン制約の集合を表すデータを圧縮表現することが可能となる。
【００６７】
図９は，本実施の形態の詰め込み支援装置による展開パタン集合ＢＤＤ生成処理フローチャートである。
【００６８】
詰め込み支援装置１０において，生成部１１は，二分決定グラフ情報記憶部１３に記憶される展開パタン集合ＢＤＤを０集合のＢＤＤに初期化する（ステップＳ１０）。
【００６９】
生成部１１は，制約情報記憶部１２に記憶された組合せパタン制約を順に１つ選択する（ステップＳ１１）。生成部１１は，選択された組合せパタン制約のＢＤＤを生成する（ステップＳ１２）。生成部１１は，生成した組合せパタン制約のＢＤＤを，二分決定グラフ情報記憶部１３に記憶された展開パタン集合ＢＤＤに加算する（ステップＳ１３）。
【００７０】
生成部１１は，すべての組合せパタン制約について処理が終了したかを判定する（ステップＳ１４）。すべての組合せパタン制約についてまだ処理が終了していなければ（ステップＳ１４のＮＯ），生成部１１は，ステップＳ１１の処理に戻って，次の組合せパタン制約の処理に移る。すべての組合せパタン制約について処理が終了していれば（ステップＳ１４のＹＥＳ），生成部１１は，処理を終了する。
【００７１】
次に，指定された荷物の組合せパタンについて，積み込み可能であるか否かを，展開パタン集合ＢＤＤを用いて判定する処理について説明する。
【００７２】
取得部１４は，積み込み可能性を判断する対象の荷物の数の組合せパタンを取得する。以下では，積み込み可能性を判断する対象の荷物の数の組合せパタンを，積み込みパタンと呼ぶ。例えば，ユーザは，キーボード・マウス等の入力装置を用いて，詰め込み支援装置１０のコンピュータに，積み込み可能性を判断する対象の積み込みパタンの指定を入力する。取得部１４は，ユーザにより指定された積み込みパタンを取得する。
【００７３】
判定部１５は，二分決定グラフ情報記憶部１３に記憶された展開パタン集合ＢＤＤを参照し，取得した積み込みパタンが積み込み可能であるか否かを判定する。より具体的には，判定部１５は，積み込みパタンで，展開パタン集合ＢＤＤを根ノードから探索する。判定部１５は，探索の結果，到達した葉ノードが１葉であれば，積み込みパタンで示される荷物の組合せパタンが積み込み可能であると判定し，到達した葉ノードが０葉であれば，積み込みパタンで示される荷物の組合せパタンが積み込み不可能であると判定する。
【００７４】
図１０は，本実施の形態による展開パタン集合ＢＤＤを用いた積み込み可能判定の例を説明する図である。
【００７５】
図１０（Ａ）は，取得した積み込みパタンが（Ｘ1 ，Ｘ2 ）＝（１，１）である場合に，該積み込みパタンの積み込み可能性を，図７に示す展開パタン集合ＢＤＤを用いた探索で判定する例を示す。積み込みパタン（Ｘ1 ，Ｘ2 ）＝（１，１）を，桁変数を用いた二進数で表すと，（ｘ11ｘ10，ｘ21ｘ20）＝（０１，０１）となる。この二進数表現の積み込みパタン（ｘ11ｘ10，ｘ21ｘ20）＝（０１，０１）の各桁変数の値を，図７に示す展開パタン集合ＢＤＤの根ノードから順に代入して探索を行うと，その探索経路は図１０（Ａ）の太線矢印で示すパスとなる。最後に到達した葉ノードが真であることを示す１葉であるので，積み込みパタン（Ｘ1 ，Ｘ2 ）＝（１，１）は，積み込み可能であると判定される。
【００７６】
図１０（Ｂ）は，取得した積み込みパタンが（Ｘ1 ，Ｘ2 ）＝（２，２）である場合に，該積み込みパタンの積み込み可能性を，図７に示す展開パタン集合ＢＤＤを用いた探索で判定する例を示す。積み込みパタン（Ｘ1 ，Ｘ2 ）＝（２，２）を，桁変数を用いた二進数で表すと，（ｘ11ｘ10，ｘ21ｘ20）＝（１０，１０）となる。この二進数表現の積み込みパタン（ｘ11ｘ10，ｘ21ｘ20）＝（１０，１０）の各桁変数の値を，図７に示す展開パタン集合ＢＤＤの根ノードから順に代入して探索を行うと，その探索経路は図１０（Ｂ）の太線矢印で示すパスとなる。最後に到達した葉ノードが偽であることを示す０葉であるので，積み込みパタン（Ｘ1 ，Ｘ2 ）＝（２，２）は，積み込み不可能であると判定される。
【００７７】
このように，本実施の形態による詰め込み支援装置１０では，組合せパタン制約の集合を表すＢＤＤを用いることにより，指定された積み込みパタンの積み込み可能性を，高速に判定できる。
【００７８】
図１１は，本実施の形態の詰め込み支援装置による積み込み可能性判定処理フローチャートである。
【００７９】
詰め込み支援装置１０において，判定部１５は，取得部１４が取得した積み込みパタンの二進数表現配列ｐ2 を入力する（ステップＳ２０）。また，判定部１５は，展開パタン集合ＢＤＤにおける根ノードのノードＩＤ＝ｒを取得する（ステップＳ２１）。
【００８０】
判定部１５は，積み込みパタンの配列ｐ2 と，根ノードのノードＩＤ＝ｒとを引数として，ＢＤＤ探索判定処理を実行する（ステップＳ２２）。ＢＤＤ探索判定処理は，二分決定グラフ情報記憶部１３に記憶された展開パタン集合ＢＤＤデータ１３０を用いた探索により，積み込みパタンの積み込み可能性の判定結果を取得する処理である。ＢＤＤ探索判定処理の結果として，真を示す“１”または偽を示す“０”の判定結果が得られる。ＢＤＤ探索判定処理の詳細については，後述する。
【００８１】
判定部１５は，ＢＤＤ探索判定処理による判定結果が“１”であるかを判定する（ステップＳ２３）。判定結果が“１”であれば（ステップＳ２３のＹＥＳ），指定された積み込みパタンが積み込み可能と判定されたことになる。このとき，出力部１７は，指定された積み込みパタンが積み込み可能である旨を出力する（ステップＳ２４）。判定結果が“１”でなければ（ステップＳ２３のＮＯ），すなわち判定結果が“０”であれば，指定された積み込みパタンが積み込み不可能と判定されたことになる。このとき，出力部１７は，指定された積み込みパタンが積み込み不可能である旨を出力する（ステップＳ２４）。なお，出力部１７による出力先としては，例えばディスプレイや記憶装置，プリンタなど，任意の設計が可能である。
【００８２】
図１２は，本実施の形態の詰め込み支援装置の判定部によるＢＤＤ探索判定処理フローチャートである。
【００８３】
図１２のフローチャートに示すＢＤＤ探索判定処理では，積み込みパタンの配列ｐ2 と，根ノードのノードＩＤ＝ｒとが引数として得られている。判定部１５は，処理対象ノードのノードＩＤを示すｎｉｄに，根ノードのノードＩＤ＝ｒを代入する（ステップＳ３０）。ステップＳ３０の処理では，判定部１５は，探索の開始を根ノードに設定している。
【００８４】
判定部１５は，処理対象となる桁変数の変数番号を示すｉに，ｂ［ｎｉｄ］．ｖａｒを代入する（ステップＳ３１）。ここでは，展開パタン集合ＢＤＤデータ１３０を，ｂで示すものとする。ｖａｒは，展開パタン集合ＢＤＤデータ１３０における変数番号項目を示す。すなわち，ｂ［ｎｉｄ］．ｖａｒは，展開パタン集合ＢＤＤデータ１３０のノードＩＤ＝ｎｉｄのレコードにおける変数番号項目の値を示している。ステップＳ３１の処理では，判定部１５は，処理対象となる桁変数の変数番号ｉを，処理対象ノードの桁変数の変数番号に合わせている。
【００８５】
判定部１５は，ｉの値が１を下回っているかを判定する（ステップＳ３２）。図７，図８に示すように，本実施の形態では，葉ノードに対して変数番号０を割り当てている。ステップＳ３２の処理では，判定部１５は，探索が葉ノードに到達したか否かを判定している。
【００８６】
ｉの値が１を下回っていなければ（ステップＳ３２のＮＯ），すなわちｉの値が１以上であれば，判定部１５は，処理対象となる桁変数の値を示すｖａｌに，ｐ2 ［ｉ］を代入する（ステップＳ３３）。ｐ2 ［ｉ］は，積み込みパタンの配列ｐのｉ番目の要素を示す。すなわち，ｐ2 ［ｉ］は，積み込みパタンにおける，処理対象となる桁変数の値を示している。ステップＳ３３の処理では，判定部１５は，処理対象ノードがまだ葉ノードに到達していない場合において，積み込みパタンから，処理対象となる桁変数の値を特定している。
【００８７】
判定部１５は，処理対象ノードのノードＩＤを示すｎｉｄに，ｂ［ｎｉｄ］．ｃｈｉｌｄ［ｖａｌ］を代入し（ステップＳ３４），ステップＳ３１の処理に戻る。ｃｈｉｌｄ［０］は，展開パタン集合ＢＤＤデータ１３０における０枝の子ノード項目を示し，ｃｈｉｌｄ［１］は，展開パタン集合ＢＤＤデータ１３０における１枝の子ノード項目を示す。すなわち，ｂ［ｎｉｄ］．ｃｈｉｌｄ［ｖａｌ］は，展開パタン集合ＢＤＤデータ１３０のノードＩＤ＝ｎｉｄのレコードにおける，処理対象となる桁変数の値が示す枝の子ノード項目の値を示している。ステップＳ３４の処理では，判定部１５は，ｎｉｄを次の処理対象ノードのノードＩＤに更新している。
【００８８】
ｉの値が１を下回っていれば（ステップＳ３２のＹＥＳ），すなわちｉの値が０であれば，判定部１５は，ｂ［ｎｉｄ］．ｃｈｉｌｄ［０］の値を判定結果とし（ステップＳ３５），その判定結果の値を返して処理を終了する。判定結果は，ｂ［ｎｉｄ］．ｃｈｉｌｄ［１］の値でもよい。ｉの値が０であるということは，処理対象ノードが葉ノードに到達したということである。本実施の形態では，真偽を示す葉ノードの値は，展開パタン集合ＢＤＤデータ１３０における，０葉または１葉の葉ノードのレコードの，０枝の子ノード項目または１枝の子ノード項目に記録されている。ステップＳ３５の処理では，判定部１５は，処理対象ノードが葉ノードに到達した場合に，その葉ノードの値を判定結果に設定している。
【００８９】
次に，指定された積み込みパタンが積み込み不可能と判定された場合に，該指定された積み込みパタンにおける各荷物の個数の制限内で，所定の目的とする値の最大値が得られる荷物の数の組合せパタンを，展開パタン集合ＢＤＤを用いて抽出する処理について説明する。以下では，所定の目的とする値の最大値が得られる荷物の組合せパタンを，最適パタンと呼ぶ。
【００９０】
所定の目的とする値としては，例えば，荷物の個数や，荷物の重量，荷物の価値などがある。所定の目的とする値の最大値が得られる荷物の組合せパタンは，例えば荷物の総個数が最大となる組合せパタンや，荷物の総重量が最大となる組合せパタン，荷物の合計価値が最大となる組合せパタンなどである。どのような値を目的として設定するかは，任意である。以下では，所定の目的とする値を荷物の個数とし，荷物の総個数が最大となる組合せパタンを最適パタンとする例を説明する。
【００９１】
例えば，配送計画では，指定された積み込みパタンが積み込み不可能と判定された場合，積み込みできる荷物の組合せを別に考える必要がある。配送計画において，例えば，積み込み可能性の判定対象となる積み込みパタンは，ある配送拠点で用意される各荷物の種類ごとの個数を表している。そのため，指定された積み込みパタンの範囲内で，積み込みできる適切な荷物の個数を求めたいという要望がある。本実施の形態では，抽出部１６は，指定された積み込みパタンにおける各種荷物の個数を上限とした制約のもとに，最適パタンの抽出を行う。
【００９２】
図１３は，本実施の形態による層と重みを説明する図である。
【００９３】
図１３に示す展開パタン集合ＢＤＤは，図７に示す展開パタン集合ＢＤＤと同じものである。図１３では，展開パタン集合ＢＤＤにおける層と重みの例が示されている。図１３において，層番号は，層を一意に識別する識別情報である。重みは，各桁変数の値に重み付けする値を示す。
【００９４】
展開パタン集合ＢＤＤを利用した最適パタンの探索では，荷物の種類ごとにその個数が積み込みパタンの制限内であるかをチェックする必要がある。そこで，本実施の形態では，展開パタン集合ＢＤＤにおける桁変数を，荷物の種類ごとにグループ化した層を設定する。
【００９５】
図１３に示すように，桁変数ｘ11とｘ10は，同じ荷物の個数を表す変数であるので，同じ層が設定される。また，桁変数ｘ21とｘ20は，同じ荷物の個数を表す変数であるので同じ層が設定される。なお，本実施の形態の例では，変数ではない葉ノードにも，層番号０が割り当てられている。
【００９６】
図１３に示す展開パタン集合ＢＤＤにおいて，例えば，ｘ11＝１である場合とｘ10＝１である場合とでは，各桁変数の値は同じ１であっても，それぞれが表す荷物の個数は異なる。ｘ11は二進数の２桁目を表す変数であり，ｘ10は二進数の１桁目を表す変数であるので，ｘ11＝１はｘ10＝１の２倍の値を表していることになる。
【００９７】
図１３に示す展開パタン集合ＢＤＤに示す重みは，各桁変数の値の重みを示している。すなわち，二進数の１桁目を表す変数ｘ10，ｘ20はそれぞれ重み１となり，二進数の２桁目を表す変数ｘ11，ｘ21はそれぞれ変数ｘ10，ｘ20の倍の重み２となる。
【００９８】
図１４〜図１７は，本実施の形態による最適パタン抽出の例を説明する図である。
【００９９】
以下では，図１４〜図１７を用いて，本実施の形態による最適パタン抽出の例を説明する。ここでは，取得部１２により積み込みパタン（２，２）が取得され，判定部１５によって，すでに積み込み不可能の判定がなされているものとする。すなわち，積み込みパタン（２，２）が，抽出部１６による最適パタン抽出における各荷物の種類の制限個数となる。
【０１００】
二分決定グラフ情報記憶部１３には，図１３に示す展開パタン集合ＢＤＤのデータが記憶されている。図１４〜図１７に示す展開パタン集合ＢＤＤデータ１３０’は，その一例を示す。図１４〜図１７に示す展開パタン集合ＢＤＤデータ１３０’は，最適パタン抽出の過程における展開パタン集合ＢＤＤデータ１３０’の変遷を示している。
【０１０１】
なお，図８に示す展開パタン集合ＢＤＤデータ１３０と，図１４〜図１７に示す展開パタン集合ＢＤＤデータ１３０’とでは，一部データ項目が異なるが，基本的には同じデータの例を示している。図８に示す展開パタン集合ＢＤＤデータ１３０は，積み込み可能性判定の処理に使用するデータ項目を明示したものであり，図１４〜図１７に示す展開パタン集合ＢＤＤデータ１３０’は，最適パタン抽出の処理に使用するデータ項目を明示したものである。
【０１０２】
図１４〜図１７に示す展開パタン集合ＢＤＤデータ１３０’において，ノードＩＤ，変数番号，０枝の子ノード，１枝の子ノードについては，図８に示す展開パタン集合ＢＤＤデータ１３０と全く同じものである。層番号は，図１３の展開パタン集合ＢＤＤにも示す，層の識別情報である。最大荷物数は，各レコードが示すノードから葉ノードまでのパスで表される荷物数のうち，最大の荷物数を示す。最適パタンは，最大荷物数が得られる場合の荷物の数の組合せパタンを示す。
【０１０３】
図１４〜図１７に示す展開パタン集合ＢＤＤデータ１３０’において，最大荷物数と最適パタンの項目については，最適パタン抽出の処理過程で値が記録されるワークエリアである。別の制限となる積み込みパタンの指定を受けた場合には，最大荷物数と最適パタンのデータはクリアされて，新たな最適パタン抽出の処理過程でデータが記録される。このようなワークエリアを，展開パタン集合ＢＤＤデータ１３０’から切り離して管理してもよい。
【０１０４】
抽出部１６は，図１４に示すように，０葉の葉ノードを示すノードＩＤ＃０の最大荷物数を−∞に設定する。これは，組合せパタン制約を満たさない，０葉の葉ノードに到達する荷物の組合せパタンが最適パタンとして抽出されないための設定である。また，図１４に示すように，１葉の葉ノードを示すノードＩＤ＃１の最大荷物数を０に設定する。これは，１葉の葉ノードを最大荷物数を求める起点とするための設定である。
【０１０５】
抽出部１６は，根ノードを処理の開始点として，子ノードに対する処理を再帰的に行うことにより，目的とする最大荷物数が得られる最適パタンの抽出を行う。
【０１０６】
抽出部１６は，根ノード（ノードＩＤ＃２）を含む層番号１の層の処理を行おうとするが，処理開始の時点ではまだ先の層の処理が行われていないので，根ノード（ノードＩＤ＃２）を含む層における最大荷物数と最適パタンとが決定できない。抽出部１６は，根ノード（ノードＩＤ＃２）を含む層番号１の層の処理を置いておき，先に層番号２の層の処理を行う。
【０１０７】
抽出部１６は，層番号２の層の次層が，葉ノードを示す層番号０の層であるので，そのまま層番号２の層の処理を行う。根ノードから層番号１の変数ｘ11，ｘ10に値を割り当ててたどりつくノードには，ノードＩＤ＃５，＃６，＃７の３つのノードがある。抽出部１６は，それらのノードのそれぞれについて，最大荷物数と最適パタンとを求める処理を行う。
【０１０８】
ここで，抽出部１６は，まずノードＩＤ＃５のノードについて，最大荷物数と最適パタンとを求める。図１３の展開パタン集合ＢＤＤに示すように，ノードＩＤ＃５のノードから葉ノードまでの経路のうち，（ｘ21ｘ20）＝（１１）の経路は，０葉の葉ノードに到達するため，最大荷物数と最適パタンとを求める経路から除外される。（ｘ21ｘ20）＝（１０）の経路は，１葉の葉ノードに到達する。この経路が表す荷物数を求めると，図１３の展開パタン集合ＢＤＤから桁変数ｘ21の重みが２であるので，荷物数は２個となる。
【０１０９】
ノードＩＤ＃５のノードの０枝は，桁変数ｘ20を飛び越して，直接に１葉の葉ノードに到達している。このようなケースでは，飛び越した桁変数の分も考慮する必要がある。ノードＩＤ＃５のノードの０枝の場合，桁変数ｘ20を飛び越した経路が表す最大の荷物数は，（ｘ21ｘ20）＝（０１）の場合の１個となる。
【０１１０】
抽出部１６は，ノードＩＤ＃５のノードについて，（ｘ21ｘ20）＝（１０）の経路が表す荷物数２個が最大となり，かつ荷物数２個は積み込みパタン（２，２）における荷物＃２の制限個数２以下であるため，図１４に示すように，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＃５のレコードにおける最大荷物数項目に２を記録する。また，層番号２の層は，荷物＃２に対応するので，抽出部１６は，図１４に示すように，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＃５のレコードにおける最適パタン項目の配列に，（−，２）を記録する。最適パタンにおいて，“−”は，値が得られていないことを示す。ノードＩＤ＃５のノードについての処理段階では，また層番号１の層に対応する荷物＃１の個数は得られていない。
【０１１１】
抽出部１６は，ノードＩＤ＃６のノードについて，ノードＩＤ＃５のノードと同様の処理を行う。ノードＩＤ＃６のノードについての処理では，（ｘ21ｘ20）＝（０１）の経路が表す荷物数１個が最大となる。抽出部１６は，図１５に示すように，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＃６のレコードにおける最大荷物数項目に１を記録する。また，抽出部１６は，図１５に示すように，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＃６のレコードにおける最適パタン項目の配列に，（−，１）を記録する。
【０１１２】
抽出部１６は，ノードＩＤ＃７のノードについても，ノードＩＤ＃５のノードと同様の処理を行う。ノードＩＤ＃７のノードについての処理では，（ｘ21ｘ20）＝（００）の経路が表す荷物数０個が最大となる。抽出部１６は，図１６に示すように，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＃７のレコードにおける最大荷物数項目に０を記録する。また，抽出部１６は，図１６に示すように，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＃７のレコードにおける最適パタン項目の配列に，（−，０）を記録する。
【０１１３】
抽出部１６は，層番号２の層の処理が終了すると，層番号１の層の処理に戻る。抽出部１６は，ノードＩＤ＃２のノードについて，最大荷物数と最適パタンとを求める。
【０１１４】
図１３の展開パタン集合ＢＤＤに示すように，（ｘ11ｘ10）＝（００）の経路，すなわちノードＩＤ＃２のノードからノードＩＤ＃３のノードの０枝を経由して１葉の葉ノードに至る経路では，層番号２の層の飛び越しがある。このとき，抽出部１６は，飛び越した層について，積み込みパタンによる制限値を，該当経路における最大の荷物数とする。図１３の展開パタン集合ＢＤＤに示す例の場合，（ｘ11ｘ10）＝（００）の経路の最大荷物数は積み込みパタン（２，２）における荷物＃１の制限個数の２個となり，そのときの最適パタンは（０，２）となる。
【０１１５】
（ｘ11ｘ10）＝（０１）の経路の場合，ノードＩＤ＃５の結果が最大荷物数２，最適パタン（−，２）であるので，（ｘ11ｘ10）＝（０１）で表される荷物＃１の個数１と合わせて，最大荷物数は３個となり，そのときの最適パタンは（１，２）となる。
【０１１６】
（ｘ11ｘ10）＝（１０）の経路の場合，ノードＩＤ＃６の結果が最大荷物数１，最適パタン（−，１）であるので，（ｘ11ｘ10）＝（１０）で表される荷物＃１の個数２と合わせて，最大荷物数は３個となり，そのときの最適パタンは（２，１）となる。
【０１１７】
（ｘ11ｘ10）＝（１１）の経路の場合，（ｘ11ｘ10）＝（１０）で表される荷物＃１の個数は３個となるので，積み込みパタン（２，２）における荷物＃１の制限を超えている。そのため，（ｘ11ｘ10）＝（１１）の経路は，最大荷物数と最適パタンとを求める経路から除外される。
【０１１８】
これらのノードＩＤ＃２のノードについての処理結果から，最大荷物数は，（ｘ11ｘ10）＝（０１）の経路と（ｘ11ｘ10）＝（１０）の経路における３個となる。ここでは，抽出部１６は，０枝の結果を優先して，（ｘ11ｘ10）＝（０１）の経路についての探索結果である最大荷物数３，最適パタン（１，２）を採用する。なお，１枝の結果を優先する，最大荷物数が得られるすべてのパタンを結果とするなどの設計は任意である。
【０１１９】
抽出部１６は，図１７に示すように，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＃２のレコードにおける最大荷物数項目に３を記録する。また，抽出部１６は，図１７に示すように，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＃２のレコードにおける最適パタン項目の配列に，（１，２）を記録する。ここで得られた根ノード（ノード１Ｄ＃２）の結果が，最終的に抽出する最適パタンの結果となる。
【０１２０】
このように，本実施の形態による詰め込み支援装置１０では，組合せパタン制約の集合を表すＢＤＤを用いることにより，指定された積み込みパタンの制限内で，最大の目的値が得られる荷物の組合せパタンを高速に抽出できる。
【０１２１】
図１８は，本実施の形態の詰め込み支援装置による最適パタン抽出処理フローチャートである。
【０１２２】
詰め込み支援装置１０において，抽出部１６は，取得部１４が取得した積み込みパタンの配列ｐを入力する（ステップＳ４０）。ここで取得する配列ｐは，整数配列である。また，抽出部１６は，展開パタン集合ＢＤＤにおける根ノードのノードＩＤ＝ｒを取得する（ステップＳ４１）。
【０１２３】
抽出部１６は，ｂ［＃０］．ｍａｘｖに−∞を記録し，ｂ［＃１］．ｍａｘｖに０を記録する（ステップＳ４２）。ｍａｘｖは，展開パタン集合ＢＤＤデータ１３０’における最大荷物数項目を示す。すなわち，ｂ［＃０］．ｍａｘｖは，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＝＃０のレコードにおける最大荷物数項目の値を示している。また，ｂ［＃１］．ｍａｘｖは，展開パタン集合ＢＤＤデータ１３０’のノードＩＤ＝＃０のレコードにおける変数番号項目の値を示している。ステップＳ４２の処理では，抽出部１６は，０葉の葉ノードと１葉の葉ノードに対する最大荷物数の設定を行っている。
【０１２４】
抽出部１６は，Ｗn+1 に０を入力する（ステップＳ４３）。Ｗn+1 は，計算で使用される便宜上のもので，０が設定される。抽出部１６は，カウンタｉに，桁変数の数すなわち変数番号の最大値ｎを設定する（ステップＳ４４）。抽出部１６は，Ｗi に，Ｗi+1 ＋ｍａｘ（ｗi ，０）の値を入力する（ステップＳ４５）。ｗi は，変数番号ｉの変数に対応する重みを示し，ｍａｘ（ｗi ，０）は，ｗi と０のうちで値が大きい方を示す。これは，重みが大きくなる方の枝を選ぶことを示している。抽出部１６は，カウンタｉの値が１であるかを判定する（ステップＳ４６）。カウンタｉの値が１でなければ（ステップＳ４６のＮＯ），抽出部１６は，カウンタｉの値をデクリメントし（ステップＳ４７），ステップＳ４５の処理に戻る。Ｗi （ｉ＝１〜ｎ）は，変数番号ｉの桁変数のノードから重みが重い方の枝を選んで葉ノードまで到達する場合の，変数番号ｉの桁変数のノードから葉ノードに至るパスの重みの合計値である。ステップＳ４３〜Ｓ４７の処理で求められるＷi （ｉ＝１〜ｎ）は，後述の処理で桁変数レベルの飛び越しがある場合に，飛び越した桁変数レベルの荷物数を考慮するために使用される。
【０１２５】
カウンタｉの値が１であれば（ステップＳ４６のＹＥＳ），抽出部１６は，ｍに，葉ノードを除いた層の数を入力する（ステップＳ４８）。抽出部１６は，ＬＷm+1 に０を入力する（ステップＳ４９）。ＬＷm+1 は，計算で使用される便宜上のもので，０が設定される。抽出部１６は，カウンタｊに，層の数ｍを設定する（ステップＳ５０）。抽出部１６は，ＬＷj に，ＬＷj+1 ＋ｍａｘ（ｐ［ｊ］，０）の値を入力する（ステップＳ５１）。ｐ［ｊ］は，積み込みパタンの配列ｐのｊ番目の要素の値を示し，これは，層番号ｊの層に対応する荷物の制限数を示す。ｍａｘ（ｐ［ｊ］，０）は，ｐ［ｊ］と０のうちで値が大きい方を示す。抽出部１６は，カウンタｊの値が１であるかを判定する（ステップＳ５２）。カウンタｊの値が１でなければ（ステップＳ５２のＮＯ），抽出部１６は，カウンタｊの値をデクリメントし（ステップＳ５３），ステップＳ５１の処理に戻る。ＬＷj （ｊ＝１〜ｍ）は，層番号ｊが与えられたノードから最下層までに至る各層に対応する荷物の制限数の合計値である。ステップＳ４８〜Ｓ５３の処理で求められるＬＷj （ｊ＝１〜ｍ）は，後述の処理で層の飛び越しがある場合に，飛び越した層の荷物数を考慮するために使用される。
【０１２６】
カウンタｊの値が１であれば（ステップＳ５２のＹＥＳ），抽出部１６は，積み込みパタンの配列ｐ，ｎｉｄ＝ｒ（根ノードのノードＩＤ），ｌｉｄ＝１（根ノードの層番号）を引数として，最適パタン取得処理を実行する（ステップＳ５４）。ｎｉｄは，現在の処理対象ノードのノードＩＤを示す。ｌｉｄは，現在の処理対象層の層番号を示す。最適パタン取得処理は，現在の処理対象ノードについて，最大荷物数と最適パタンとを取得する処理である。最適パタン取得処理の詳細については，後述する。
【０１２７】
出力部１７は，ステップＳ５４の最適パタン取得処理の結果得られる最適パタンｂ［ｒ］．ｍａｘｐと最大荷物数ｂ［ｒ］．ｍａｘｖを出力する（ステップＳ５５）。ｍａｘｐは，展開パタン集合ＢＤＤデータ１３０’における最適パタン項目を示す。すなわち，ｂ［ｒ］．ｍａｘｐは，展開パタン集合ＢＤＤデータ１３０’の根ノード（ノードＩＤ＃２）のレコードにおける最適パタン項目の値を示している。また，ｂ［ｒ］．ｍａｘｖは，展開パタン集合ＢＤＤデータ１３０’の根ノード（ノードＩＤ＃２）のレコードにおける最大荷物数項目の値を示している。このように，展開パタン集合ＢＤＤデータ１３０’の根ノード（ノードＩＤ＃２）のレコードにおける最適パタン項目の値が，目的とする最適パタンを抽出した結果となる。
【０１２８】
図１９は，本実施の形態の詰め込み支援装置の抽出部による最適パタン取得処理フローチャートである。
【０１２９】
図１９のフローチャートに示す最適パタン取得処理では，積み込みパタンの配列ｐと，現在の処理対象ノードのノードＩＤを示すｎｉｄと，現在の処理対象層の層番号を示すｌｉｄとが引数として得られている。抽出部１６は，ｂ［ｎｉｄ］．ｍａｘｖがすでに記録済みであるかを判定する（ステップＳ６０）。ｂ［ｎｉｄ］．ｍａｘｖは，展開パタン集合ＢＤＤデータ１３０’における処理対象ノードの最大荷物数項目を示している。ｂ［ｎｉｄ］．ｍａｘｖがすでに記録済みであれば（ステップＳ６０のＹＥＳ），抽出部１６は，最適パタン取得処理を終了する。
【０１３０】
ｂ［ｎｉｄ］．ｍａｘｖがまだ記録済みでなければ（ステップＳ６０のＮＯ），抽出部１６は，ｍａｘＶを−∞で初期化する（ステップＳ６１）。ｍａｘＶは，現在の処理対象ノードにおける現時点での最大荷物数を示す。
【０１３１】
抽出部１６は，ｐ，ｎｉｄ，ｌｉｄ，ｃｕｒＶ＝０，ｌａｙｅｒｍａｘ，ｍａｘｉｄ，ｍａｘＶを引数として，層探索処理を実行する（ステップＳ６２）。ｃｕｒＶは，現在の処理対象ノードにおける荷物数を示す。ｌａｙｅｒｍａｘは，現在の処理対象ノードにおいて，現在の処理対象層内の探索での最大の荷物数を示す。ｍａｘｉｄは，ｌａｙｅｒｍａｘが得られる場合に辿り着く次層のノードのノードＩＤを示す。層探索処理は，現在の処理対象ノードについて，現在の処理対象層についての探索を行い，最大荷物数ｍａｘＶを求める処理である。層探索処理の詳細については，後述する。
【０１３２】
抽出部１６は，ｂ［ｎｉｄ］．ｍａｘｖに，層探索処理で得られたｍａｘＶの値を記録する（ステップＳ６３）。ステップＳ６３の処理は，求められた現在の処理対象ノードにおける最大荷物数ｍａｘＶを，展開パタン集合ＢＤＤデータ１３０’における処理対象ノードの最大荷物数項目ｂ［ｎｉｄ］．ｍａｘｖに記録する処理である。
【０１３３】
抽出部１６は，ｂ［ｎｉｄ］．ｍａｘｐに，（ｌａｙｅｒｍａｘ，ｂ［ｍａｘｉｄ］．ｍａｘｐ）を記録する（ステップＳ６４）。ｂ［ｎｉｄ］．ｍａｘｐは，展開パタン集合ＢＤＤデータ１３０’における処理対象ノードの最適パタン項目の配列を示す。ｂ［ｍａｘｉｄ］．ｍａｘｐは，展開パタン集合ＢＤＤデータ１３０’における，ｌａｙｅｒｍａｘが得られる次層のノードの最適パタン項目の配列を示す。ステップＳ６４の処理は，次層のノードにおける最適パタン項目の配列ｂ［ｍａｘｉｄ］．ｍａｘｐに現在の処理対象層の探索で得られた最大の荷物数ｌａｙｅｒｍａｘを追加した配列を，展開パタン集合ＢＤＤデータ１３０’における処理対象ノードの最適パタン項目ｂ［ｎｉｄ］．ｍａｘｐに記録する処理である。
【０１３４】
図２０は，本実施の形態の詰め込み支援装置の抽出部による層探索処理フローチャートである。
【０１３５】
図２０のフローチャートに示す層探索処理では，ｐ，ｎｉｄ，ｌｉｄ，ｃｕｒＶ，ｌａｙｅｒｍａｘ，ｍａｘｉｄ，ｍａｘＶが引数として得られている。抽出部１６は，ｂ［ｎｉｄ］．ｌａｙｅｒとｌｉｄとが一致するかを判定する（ステップＳ７０）。ｂ［ｎｉｄ］．ｌａｙｅｒは，展開パタン集合ＢＤＤデータ１３０’における処理対象ノードの層番号項目を示している。ステップＳ７０の処理では，現在の処理対象ノードが属する層と，現在の処理対象層とが一致するかを判定している。
【０１３６】
ｂ［ｎｉｄ］．ｌａｙｅｒとｌｉｄとが一致すれば（ステップＳ７０のＹＥＳ），抽出部１６は，ｋを０に設定する（ステップＳ７１）。ｋは，桁変数の値を表す。
【０１３７】
抽出部１６は，ｋが１以下であるかを判定する（ステップＳ７２）。ｋは桁変数の値を表すので，０か１の値となる。ｋが１以下でなければ（ステップＳ７２のＮＯ），すなわちｋ＝２であれば，抽出部１６は，層探索処理を終了する。
【０１３８】
ｋが１以下であれば（ステップＳ７２のＹＥＳ），抽出部１６は，ｎｅｘｔＶに，ｃｕｒＶ＋ｗb[nid].var＊ｋを入力する（ステップＳ７３）。ｎｅｘｔＶは，現在の処理対象ノードの子ノードにおける荷物数を示す。ｂ［ｎｉｄ］．ｖａｒは，展開パタン集合ＢＤＤデータ１３０’における処理対象ノードの変数番号項目の値を示すので，ｗb[nid].varは現在の処理対象ノードが示す桁変数の重みを示す。ｗb[nid].var＊ｋは，現在の処理対象ノードが示す桁変数の値がｋである場合の該桁変数が表す荷物数を示す。ｃｕｒＶ＋ｗb[nid].var＊ｋは，現在の処理対象ノードのｋ枝の子ノードにおける荷物数を示す。ステップＳ７３の処理は，現在の処理対象ノードのｋ枝の子ノードにおける荷物数を算出する処理である。
【０１３９】
抽出部１６は，ｎｅｘｔＶがｐ［ｌｉｄ］以下であるかを判定する（ステップＳ７４）。ｐ［ｌｉｄ］は，積み込みパタンの配列ｐにおける，現在の処理対象層の要素を示す。すなわち，ｐ［ｌｉｄ］は，現在の処理対象層の荷物数の制限値を表す。ステップＳ７４の処理では，現在の処理対象ノードの子ノードにおける荷物数が，現在の処理対象層における荷物数の制限の範囲内であることを確認している。ｎｅｘｔＶがｐ［ｌｉｄ］以下でなければ（ステップＳ７４のＮＯ），抽出部１６は，層探索処理を終了する。
【０１４０】
ｎｅｘｔＶがｐ［ｌｉｄ］以下であれば（ステップＳ７４のＹＥＳ），抽出部１６は，ｎｅｘｔＶに，ｎｅｘｔＶ＋ｍａｘ（Ｗb[nid].var+1−Ｗb[nid].child(k).var ，ｐ［ｌｉｄ］−ｎｅｘｔＶ）を入力する（ステップＳ７５）。ｂ［ｎｉｄ］．ｖａｒ＋１は，展開パタン集合ＢＤＤデータ１３０’における現在の処理対象ノードの変数番号項目の値に１を加えた値を示す。ｂ［ｎｉｄ］．ｃｈｉｌｄ（ｋ）．ｖａｒは，パタン集合ＢＤＤデータ１３０’における現在の処理対象ノードのｋ枝の子ノードの変数番号項目の値を示す。Ｗb[nid].var+1−Ｗb[nid].child(k).var は，桁変数レベルの飛び越しがある場合に，飛び越された分の桁変数により表される最大の荷物数を示す。ｐ［ｌｉｄ］−ｎｅｘｔＶは，現在の処理対象層の荷物数の制限値を超えない範囲でｎｅｘｔＶに加算できる荷物数を示す。ｍａｘ（Ｗb[nid].var+1−Ｗb[nid].child(k).var ，ｐ［ｌｉｄ］−ｎｅｘｔＶ）は，Ｗb[nid].var+1−Ｗb[nid].child(k).var と，ｐ［ｌｉｄ］−ｎｅｘｔＶとのいずれか値が大きい方を示す。ステップＳ７５の処理は，桁変数レベルの飛び越しがある場合に対応する処理である。
【０１４１】
抽出部１６は，積み込みパタン配列ｐ，ｎｉｄ＝ｂ［ｎｉｄ］．ｃｈｉｌｄ（ｋ），ｌｉｄ，ｃｕｒＶ＝ｎｅｘｔＶ，ｌａｙｅｒｍａｘ，ｍａｘｉｄ，ｍａｘＶを引数として，再帰的に層探索処理を実行する（ステップＳ７６）。ｂ［ｎｉｄ］．ｃｈｉｌｄ（ｋ）は，現在の処理対象ノードのｋ枝の子ノードを示す。抽出部１６は，ｋの値をインクリメントし（ステップＳ７７），ステップＳ７２の処理に戻る。
【０１４２】
ｂ［ｎｉｄ］．ｌａｙｅｒとｌｉｄとが一致しなければ（ステップＳ７０のＮＯ），抽出部１６は，積み込みパタン配列ｐ，ｎｉｄ，ｌｉｄ＝ｂ［ｎｉｄ］．ｌａｙｅｒを引数として，再帰的に最適パタン取得処理を実行する（ステップＳ７８）。ここでは，現在の処理対象層の，次層の処理を行っている。
【０１４３】
抽出部１６は，ｏｂｊＶに，ｃｕｒＶ＋ｂ［ｎｉｄ］．ｍａｘｖ＋ＬＷlid+1 −ＬＷb[nid].layerを入力する（ステップＳ７９）。ｏｂｊＶは，現在の処理対象層における荷物数を示す。ＬＷlid+1 −ＬＷb[nid].layerは，層の飛び越しがある場合の飛び越された層の分の荷物数を示す。ステップＳ７９の処理は，層の飛び越しを含めた現在の処理対象層における荷物数を求める処理である。
【０１４４】
抽出部１６は，ｍａｘＶよりｏｂｊＶの方が大きいかを判定する（ステップＳ８０）。ｍａｘＶよりｏｂｊＶの方が大きければ（ステップＳ８０のＹＥＳ），ｍａｘＶをｏｂｊＶで更新し，ｌａｙｅｒｍａｘをｃｕｒＶで更新し，ｍａｘｉｄをｎｉｄで更新する（ステップＳ８１）。ステップＳ８０，Ｓ８１の処理は，現在の処理対象ノードにおける最大荷物数ｍａｘＶとして，より大きな荷物数を選択する処理である。抽出部１６は，層探索処理を終了する。
【０１４５】
以上，本実施の形態について説明したが，本発明はその主旨の範囲において種々の変形が可能であることは当然である。
【０１４６】
例えば，本実施の形態では，主に運搬車に対する荷物の積み込みに関する例について説明したが，この例に限られるものではない。例えば，本実施の形態による技術を，詰め込み先の箱に対して物品を詰め込む場合の判断などに，適用することも可能である。
【符号の説明】
【０１４７】
１０  詰め込み支援装置
１１  生成部
１２  制約情報記憶部
１３  二分決定グラフ情報記憶部
１４  取得部
１５  判定部
１６  抽出部
１７  出力部
【図１】
2014029622.tif 000003
【図２】
2014029622.tif 000004
【図３】
2014029622.tif 000005
【図４】
2014029622.tif 000006
【図５】
2014029622.tif 000007
【図６】
2014029622.tif 000008
【図７】
2014029622.tif 000009
【図８】
2014029622.tif 000010
【図９】
2014029622.tif 000011
【図１０】
2014029622.tif 000012
【図１１】
2014029622.tif 000013
【図１２】
2014029622.tif 000014
【図１３】
2014029622.tif 000015
【図１４】
2014029622.tif 000016
【図１５】
2014029622.tif 000017
【図１６】
2014029622.tif 000018
【図１７】
2014029622.tif 000019
【図１８】
2014029622.tif 000020
【図１９】
2014029622.tif 000021
【図２０】
2014029622.tif 000022