(57)【要約】【課題】迅速に所望の組み合わせを抽出する。【解決手段】セットデータ格納手段２により、セットデータ４、５が格納される。複数のアイテムを備えるアイテムデータ７が入力されるとセット検索手段６により、アイテムデータ７内のアイテムを２つ以上含むセットがセットデータ格納手段２から検索される。セットリスト作成手段８により、セット検索手段６によって検索されたセットとアイテム単体群とがこの順番に並べられた配列のセットリスト９が作成される。枝刈り手段１０により、探索木が作成され、この探索木を深さ優先探索する際に、配列におけるセットに付随する値とアイテム単体群のアイテムそれぞれの値の合計値とが加算され、与えられた閾値以上になったとき、探索中のノードの枝が枝刈りされる。組み合わせ出力手段１１により、閾値より小さい合計値を備える配列のセットおよびアイテム単体群の組み合わせが出力される。【選択図】図１
2008112342.tif 000002
【特許請求の範囲】
【請求項１】
アイテムの組み合わせを抽出する組み合わせ抽出プログラムにおいて、
コンピュータを、
値をそれぞれ有する複数のアイテムのセットと、前記セットに付随する値とを有するセットデータが複数格納されたセットデータ格納手段、
複数の前記アイテムを備えるアイテムデータの入力に応答し、前記アイテムデータ内の前記アイテムを２つ以上含む前記セットを前記セットデータ格納手段から検索するセット検索手段、
前記セット検索手段により検索された前記セットと、前記アイテムデータ内の前記セット検索手段により検索された前記セットに含まれない前記アイテムで構成されるアイテム単体群とをこの順番に並べた少なくとも１つの配列を備えるセットリストを作成するセットリスト作成手段、
前記セットリストを参照し、前記アイテム単体群を最終遷移先として前記配列の並びをノード間の遷移で表す探索木を作成し、前記探索木を深さ優先探索する際に前記各配列において、前記セットに付随する値と前記アイテム単体群の前記アイテムそれぞれの値の合計値とを加算していき、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りする枝刈り手段、
前記閾値より小さい前記合計値を備える前記配列の前記セットおよび前記アイテム単体群の組み合わせを出力する組み合わせ出力手段、
として、機能させることを特徴とする組み合わせ抽出プログラム。
【請求項２】
前記セットリスト作成手段は、前記セット検索手段により検索された前記セットのうち、前記アイテムデータ内の前記アイテムを含む数の多い前記セットから順番に並べた前記配列を作成することを特徴とする請求項１記載の組み合わせ抽出プログラム。
【請求項３】
前記枝刈り手段は、前記配列において、前記セットに付随する値と前記アイテム単体群の前記アイテムそれぞれの値の合計値とが前記閾値より小さいとき、前記合計値をその後の深さ優先探索の前記閾値とすることを特徴とする請求項１記載の組み合わせ抽出プログラム。
【請求項４】
アイテムの組み合わせを抽出する組み合わせ抽出方法において、
セットデータ格納手段が、値をそれぞれ有する複数のアイテムのセットと、前記セットに付随する値とを有するセットデータを複数格納し、
セット検索手段が、複数の前記アイテムを備えるアイテムデータの入力に応答し、前記アイテムデータ内の前記アイテムを２つ以上含む前記セットを前記セットデータ格納手段から検索し、
セットリスト作成手段が、前記セット検索手段により検索された前記セットと、前記アイテムデータ内の前記セット検索手段により検索された前記セットに含まれない前記アイテムで構成されるアイテム単体群とをこの順番に並べた少なくとも１つの配列を備えるセットリストを作成し、
枝刈り手段が、前記セットリストを参照し、前記アイテム単体群を最終遷移先として前記配列の並びをノード間の遷移で表す探索木を作成し、前記探索木を深さ優先探索する際に前記各配列において、前記セットに付随する値と前記アイテム単体群の前記アイテムそれぞれの値の合計値とを加算していき、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りし、
組み合わせ出力手段が、前記閾値より小さい前記合計値を備える前記配列の前記セットおよび前記アイテム単体群の組み合わせを出力する、
ことを特徴とする組み合わせ抽出方法。
【請求項５】
アイテムの組み合わせを抽出する組み合わせ抽出装置において、
値をそれぞれ有する複数のアイテムのセットと、前記セットに付随する値とを有するセットデータが複数格納されたセットデータ格納手段と、
複数の前記アイテムを備えるアイテムデータの入力に応答し、前記アイテムデータ内の前記アイテムを２つ以上含む前記セットを前記セットデータ格納手段から検索するセット検索手段と、
前記セット検索手段により検索された前記セットと、前記アイテムデータ内の前記セット検索手段により検索された前記セットに含まれない前記アイテムで構成されるアイテム単体群とをこの順番に並べた少なくとも１つの配列を備えるセットリストを作成するセットリスト作成手段と、
前記セットリストを参照し、前記アイテム単体群を最終遷移先として前記配列の並びをノード間の遷移で表す探索木を作成し、前記探索木を深さ優先探索する際に前記各配列において、前記セットに付随する値と前記アイテム単体群の前記アイテムそれぞれの値の合計値とを加算していき、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りする枝刈り手段と、
前記閾値より小さい前記合計値を備える前記配列の前記セットおよび前記アイテム単体群の組み合わせを出力する組み合わせ出力手段と、
を有することを特徴とする組み合わせ抽出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は組み合わせ抽出プログラム、組み合わせ抽出方法および組み合わせ抽出装置に関し、特に、アイテムの組み合わせを抽出する組み合わせ抽出プログラム、組み合わせ抽出方法および組み合わせ抽出装置に関する。
【背景技術】
【０００２】
通信販売等において、単品アイテム（例えばテレビのチャンネル等）の組み合わせで構成され、単品アイテムをそれぞれ購入するよりも低価格のセット商品（お値打ちパック）の販売が一般的に行われている。
【０００３】
このような商品の販売においては、ユーザが希望するアイテムに一致するセット商品が存在しない場合、ユーザは単品アイテムのみでの購入または単品アイテムとセット商品との組み合わせでの購入のいずれかを選択することになる。
【０００４】
この場合、販売側は、セット商品の全組み合せの中からユーザが購入を希望するアイテムを全て含み、かつ、全てのアイテムを単品で購入するより購入金額が安値となる組み合わせをユーザに提供することになる。
【０００５】
組み合わせを抽出する方法として、例えば構文木を作成し、特定の組み合わせを抽出する方法が知られている（例えば、非特許文献１参照）。
【非特許文献１】”Efficiently mining long patterns from databases” Proceedings of SIGMOD'98, pp85-93.(ISBN:0-89791-995-5).1998
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、アイテムやセット商品の種類が多くなればなる程、組み合わせ候補が多数になり、計算（組み合わせの抽出計算、抽出後の料金計算）量が増大するため、ＣＰＵとメモリの両方の負荷が増大して計算時間が遅延し、適切な組み合わせを迅速に提供することが困難であった。
【０００７】
本発明はこのような点に鑑みてなされたものであり、迅速に所望の組み合わせを抽出することができる組み合わせ抽出プログラム、組み合わせ抽出方法および組み合わせ抽出装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明では上記問題を解決するために、図１に示すような処理をコンピュータ１に実行させるための組み合わせ抽出プログラムが提供される。
本発明に係る組み合わせ抽出プログラムは、アイテムの組み合わせを抽出するプログラムである。
【０００９】
セットデータ格納手段２は、値をそれぞれ有する複数のアイテム（＃ｉｔｅｍ）のセット３、３ａとセット３、３ａにそれぞれ付随する値とを有するセットデータ４、５を格納する。
【００１０】
セット検索手段６は、複数のアイテムを備えるアイテムデータ７の入力に応答し、アイテムデータ７内のアイテムを２つ以上含むセットをセットデータ格納手段２から検索する。
【００１１】
セットリスト作成手段８は、セット検索手段６により検索されたセットと、アイテムデータ７内のセット検索手段６により検索されたセットに含まれないアイテムで構成されるアイテム単体群とをこの順番に並べた少なくとも１つの配列を備えるセットリスト９を作成する。
【００１２】
枝刈り手段１０は、セットリスト９を参照し、アイテム単体群を最終遷移先として配列の並びをノード間の遷移で表す探索木を作成し、この探索木を深さ優先探索する際に各配列において、セットに付随する値とアイテム単体群のアイテムそれぞれの値の合計値とを加算していき、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りする。
【００１３】
組み合わせ出力手段１１は、閾値より小さい合計値を備える配列のセットおよびアイテム単体群の組み合わせを出力する。
このような組み合わせ抽出プログラムによれば、セットデータ格納手段２により、セットデータ４、５が格納される。そして、複数のアイテムを備えるアイテムデータ７が入力されると、セット検索手段６により、アイテムデータ７内のアイテムを２つ以上含むセットがセットデータ格納手段２から検索される。そして、セットリスト作成手段８により、セット検索手段６によって検索されたセットとアイテム単体群とがこの順番に並べられた配列を備えるセットリスト９が作成される。そして、枝刈り手段１０により、セットリスト９が参照されて探索木が作成され、この探索木を深さ優先探索する際に、配列におけるセットに付随する値とアイテム単体群のアイテムそれぞれの値の合計値とが加算されていき、与えられた閾値以上になったとき、探索中のノードの枝が枝刈りされる。その後、組み合わせ出力手段１１により、閾値より小さい合計値を備える配列のセットおよびアイテム単体群の組み合わせが出力される。
【発明の効果】
【００１４】
本発明では、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りするため、以降の計算を行う必要がなく、演算量を低減することができる。
また、深さ優先検索を行うことで、検索木上部の重複計算を省略することができ、演算量を低減することができる。
【００１５】
これにより、閾値より小さい合計値を備える配列のセットおよびアイテム単体群の組み合わせ、すなわちアイテムデータ内のアイテムを全て含み、かつ、値の小さい組み合わせを迅速に提供することができる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態を、図面を参照して詳細に説明する。
まず、本発明の概要について説明し、その後、実施の形態を説明する。
図１は、本発明の概要を示す図である。
【００１７】
コンピュータ１を用いて図１に示すような処理を行う組み合わせ抽出プログラムが提供される。
図１に示すコンピュータ１は、セットデータ格納手段２とセット検索手段６とセットリスト作成手段８と枝刈り手段１０と組み合わせ出力手段１１とを有している。
【００１８】
セットデータ格納手段２は、セット３に付随する値を有するセットデータ４と、セット３ａに付随する値を有するセットデータ５とを格納する。
セット３、３ａはそれぞれ値をそれぞれ有する複数のアイテム（＃ｉｔｅｍ）で構成されている。
【００１９】
セット３、３ａにそれぞれ付随する値（４００、３００）は、セット３、３ａそれぞれを構成するアイテム単体の値をそれぞれ加算した値よりも小さく設定されている。
セット検索手段６は、複数のアイテムを備えるアイテムデータ７の入力に応答し、アイテムデータ７内のアイテムを２つ以上含むセットをセットデータ格納手段２から検索する。なお、アイテムデータ７は全て単体のアイテムで構成され、セットは含まれていない。図１には示していないが、セットとアイテム単体とが混在するデータからアイテムデータ７を作成する手段がコンピュータ１に設けられているのが好ましい。
【００２０】
セットリスト作成手段８は、セット検索手段６により検索されたセットと、アイテムデータ７内のセット検索手段６により検索されたセットに含まれないアイテムで構成されるアイテム単体群とをこの順番に並べた少なくとも１つの配列を備えるセットリスト９を作成する。図１では、セット３の内容をセット＃３とし、セット３ａの内容をセット＃３ａとしている。
【００２１】
枝刈り手段１０は、セットリスト９を参照し、アイテム単体群を最終遷移先として配列の並びをノード間の遷移で表す探索木を作成し、この探索木を深さ優先探索する際に各配列におけて、セットに付随する値とアイテム単体群のアイテムそれぞれの値の合計値とを加算していき、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りする。なお、セットに付随する値とアイテム単体群のアイテムそれぞれの値は、予めセット検索手段６により検索されたセットに添付しておいてもよいし、セットリスト作成手段８がセットリストを作成する時点でセット検索手段６から取得するようにしておいてもよいし、枝刈り手段１０が、探索木を作成する時点でセット検索手段６から取得するようにしてもよい。
【００２２】
組み合わせ出力手段１１は、閾値より小さい合計値を備える配列のセットおよびアイテム単体群の組み合わせを出力する。
このような組み合わせ抽出プログラムによれば、セットデータ格納手段２により、セットデータ４、５が格納される。そして、複数のアイテムを備えるアイテムデータ７が入力されると、セット検索手段６により、アイテムデータ７内のアイテムを２つ以上含むセットがセットデータ格納手段２から検索される。そして、セットリスト作成手段８により、セット検索手段６によって検索されたセットとアイテム単体群とがこの順番に並べられた配列を備えるセットリスト９が作成される。そして、枝刈り手段１０により、セットリスト９が参照されて探索木が作成され、この探索木を深さ優先探索する際に、配列におけるセットに付随する値とアイテム単体群のアイテムそれぞれの値の合計値とが加算されていき、与えられた閾値以上になったとき、探索中のノードの枝が枝刈りされる。その後、組み合わせ出力手段１１により、閾値より小さい合計値を備える配列のセットおよびアイテム単体群の組み合わせが出力される。
【００２３】
図２は、実施の形態の組み合わせ抽出システムを示す図である。
組み合わせ抽出システム３００は、組み合わせ抽出装置（サーバ）１００と、端末装置（クライアント）２００とがネットワーク（インターネット）１５を介して接続されている。
【００２４】
組み合わせ抽出装置１００は、端末装置２００からのアイテム（購入商品）の商品データ（組み合わせ抽出依頼）を受信すると、アイテムの最適な組み合わせを抽出し、端末装置２００に送信する。
【００２５】
端末装置２００は、ユーザやオペレータの入力に応じて前述した商品データを組み合わせ抽出装置１００に送信する。この端末装置２００は、例えばコールセンターの端末機器やユーザが使用する端末機器である。なお、図２では、１つの端末装置２００を図示したが、複数の端末装置２００が組み合わせ抽出装置１００に接続されていてもよい。
【００２６】
図３は、組み合わせ抽出装置のハードウェア構成例を示す図である。
組み合わせ抽出装置１００は、ＣＰＵ（Central Processing Unit）１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０７を介してＲＡＭ（Random Access Memory）１０２、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、および通信インタフェース１０６が接続されている。
【００２７】
ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。ＨＤＤ１０３には、ＯＳやアプリケーションプログラムが格納される。また、ＨＤＤ１０３内には、プログラムファイルが格納される。
【００２８】
グラフィック処理装置１０４には、モニタ１６が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１６の画面に表示させる。入力インタフェース１０５には、キーボード１７とマウス１８とが接続されている。入力インタフェース１０５は、キーボード１７やマウス１８から送られてくる信号を、バス１０７を介してＣＰＵ１０１に送信する。
【００２９】
通信インタフェース１０６は、ネットワーク１５に接続されている。通信インタフェース１０６は、ネットワーク１５を介して、他のコンピュータとの間でデータの送受信を行う。
【００３０】
以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。なお、図３には組み合わせ抽出装置１００のハードウェア構成を示したが端末装置２００についても同様のハードウェア構成で実現することができる。このようなハードウェア構成のシステムにおいて組み合わせ抽出を行うために、組み合わせ抽出装置１００内には、以下のような機能が設けられる。
【００３１】
図４は、組み合わせ抽出装置および端末装置の機能を示すブロック図である。
組み合わせ抽出装置１００は、商品データ受信部１１０と、アイテム分解部１２０と、アイテム一覧格納部１３０と、セット一覧格納部１４０と、セット検索部１５０と、最適組み合わせ探索部１６０と、結果送信部１７０とを有している。
【００３２】
商品データ受信部１１０は、端末装置２００から商品データ３０を受信する。
図５は、商品データを示す図である。
商品データ３０は、アイテムを特定する品番と、複数の品番で構成されるセットとを有している。商品データ３０における品番とセットとの組み合わせは、特に限定されないが、商品データ３０には少なくとも１つのセットが含まれているものとする。図５に示す商品データ３０は、品番＃１０１、＃１０２、＃１０３で構成されるセットＡと、品番＃１０３、＃１０４、＃１０５で構成されるセットＢと、品番＃３０２、＃２０１、＃３０１とで構成されるアイテム単体群とを有している。
【００３３】
図４に戻って説明する。
アイテム分解部１２０は、アイテムに関するデータを格納するアイテム一覧格納部１３０およびセットに関するデータを格納するセット一覧格納部１４０それぞれに格納されているデータを参照し、セットおよびアイテム単体での合計金額と、セットをアイテム単体に分解したときのアイテム単体での合計金額とを算出する。
【００３４】
アイテム一覧格納部１３０およびセット一覧格納部１４０の内容については後述する。
セット検索部１５０は、セット一覧格納部１４０に格納されているデータを参照し、商品データ３０内のアイテムの品番を二つ以上含むセットを検索する。
【００３５】
最適組み合わせ探索部１６０は、セット検索部１５０の検索結果を用いて組み合わせ探索木を作成し、合計金額が最も安い組み合わせを抽出する。なお、組み合わせ探索木の内容については後述する。
【００３６】
この最適組み合わせ探索部１６０がセットリスト作成手段、枝刈り手段および組み合わせ出力手段の主要部を構成している。
結果送信部１７０は、組み合わせ抽出結果を端末装置２００に送信する。
【００３７】
端末装置２００は、データ送信部２１０と結果表示部２２０とを有している。
データ送信部２１０は、ユーザやオペレータの入力に応じて商品データ３０を組み合わせ抽出装置１００に送信する。
【００３８】
結果表示部２２０は、組み合わせ抽出装置１００から得られた組み合わせ抽出結果を受信し、端末装置２００が備えるモニタに表示する。
次に、組み合わせ抽出装置１００の動作について説明する。
【００３９】
図６は、組み合わせ抽出装置の動作を示すフローチャートである。
まず、商品データ受信部１１０が商品データ３０を受信すると、アイテム分解部１２０が、申し込みセット集合Ｓ（Ｓ＝｛ｓ１，・・・，ｓＮ｝⊆Ｓ０（Ｓ０：全セット集合））中の各セットをアイテムに分解して申し込みアイテム集合ｉに加える（ステップＳａ１）。すなわちＵ＝ｉ∪ｓ１∪・・・∪ｓＮ（⊆Ｉ（Ｉ：全アイテム集合））とする。
【００４０】
次に、セット検索部１５０が、任意のセットｓ∈Ｓ０に対して、セットｓがＵの要素を２つ以上含むならばＳｅｔＬｉｓｔに追加する（ステップＳａ２）。ＳｅｔＬｉｓｔ内のセットには、Ｕの要素を多く含む順に一意な順序≦が与えられるものとする。
【００４１】
次に、最適組み合わせ探索部１６０が、（ＳｅｔＬｉｓｔ，≦）に対する仮想的な集合枚挙木を深さ優先探索する。なお、枝刈り用の初期閾値を合計金額α０（アイテムとセットの合計金額）とする。そして、探索により得られる最安値と、この最安値を与えるアイテムの品番、セットの組み合わせとを、組み合わせ抽出結果として結果送信部１７０に渡す（ステップＳａ３）。
【００４２】
次に、結果送信部１７０が、組み合わせ抽出結果を送信する（ステップＳａ４）。
以上で組み合わせ抽出装置１００の動作を終了する。
次に、組み合わせ抽出装置１００の動作を、具体例を用いて説明する。
【００４３】
図７および図８は、アイテム分解部の動作を示す図である。
図７に示すように、アイテム一覧格納部１３０には、アイテム一覧テーブル１３１が格納されている。
【００４４】
アイテム一覧テーブル１３１には、品番、単価、セット有無、セットの欄が設けられている。各欄の横方向に並べられた情報同士が互いに関連づけられている。
品番の欄にはアイテムを特定する品番が設定されている。
【００４５】
単価の欄には、アイテム毎の単価が設定されている。
セット有無の欄には、このアイテムを含むセットの存在の有無が設定されている。
セットの欄には、セットが存在する（○）の場合、このアイテムを含むセット名が設定されている。
【００４６】
セット一覧格納部１４０には、セット一覧テーブル１４１が格納されている。
セット一覧テーブル１４１には、セット、セット価格、品番の欄が設けられている。各欄の横方向に並べられた情報同士が互いに関連づけられている。
【００４７】
セットの欄には、セットを識別する名前が設定されている。
セット価格の欄には、セットのセット価格が設定されている。
品番の欄には、セットに含まれるアイテムの品番が設定されている。
【００４８】
アイテム分解部１２０は、商品データ３０に含まれるアイテム単体群（品番＃３０２、＃２０１、＃３０１のアイテム）について、アイテム一覧テーブル１３１を参照し、各アイテムの単価を取得する。次に、商品データ３０に含まれるセットについて、セット一覧テーブル１４１を参照し、セットＡ、セットＢそれぞれのセット価格を取得する。次に、各アイテムの単価と各セット価格とを合計した合計金額α０を含む商品データ４０を作成する。なお、例えば合計金額α０が予め分かっている場合（ユーザやオペレータにより入力された場合等）は、この動作が省略される。
【００４９】
次に、図８に示すように、アイテム分解部１２０は、商品データ４０に含まれるセットＡ、セットＢ（全セット）をそれぞれアイテム単体に分解し、アイテム一覧テーブル１３１を参照して分解したアイテム単体それぞれの合計金額を算出し、各アイテムの品番および単価とアイテム単体での合計金額α１とを含む商品単価データ５０を作成する。
【００５０】
図９は、セット検索部の動作を示す図である。
セット検索部１５０は、セット一覧テーブル１４１の中から商品単価データ５０に含まれるアイテムの品番を２つ以上含むセットを検索し、アイテムの品番との一致数の多いセットの順番に、セットを並べた検索結果データ６０を作成する。
【００５１】
図１０は、最適組み合わせ探索部のＳｅｔＬｉｓｔ作成動作を示す図である。
最適組み合わせ探索部１６０は、検索結果データ６０の一致数の多いセットから順番にセットを繋ぎ、セットに属しないアイテム単体の品番を、アイテム単体群としてセットの後段に繋いた探索木構造（配列）を作成し、この探索木構造を備えるＳｅｔＬｉｓｔ７０を作成する。
【００５２】
このとき、セットに優先順位をつけ、一致数の等しいセットについてはＡからＺの順番に繋ぐ。例えば一致数の等しいセットＡとセットＢとについては、セットＡを必ず前段（図１０中左側）に配置する。これにより、例えばセットＢ→セットＡという構造が排除されるため、ＳｅｔＬｉｓｔ７０の探索木構造を簡易なものとすることができる。
【００５３】
その後、ＳｅｔＬｉｓｔ７０内の探索木構造に基づいて作成した組み合わせ探索木Ｔを探索して最安値を探す。
図１１は、組み合わせ探索木の木構造を示す図である。
【００５４】
組み合わせ探索木Ｔは、ノード（ｎｏｄｅ）と、ノード間を接続するエッジ（ｅｄｇｅ：辺）とを有している。ノード７１が根ノード（ｒｏｏｔ）であり、他のノードは、ノード７１の下位構造となっている。ノード７１に対し、ＳｅｔＬｉｓｔ７０に基づいてノード（下位ノード）７２〜７８が作成される。各ノード７２〜７８には、それぞれセット名およびセット価格が関連づけられている。各ノード７２〜７８の下位には、アイテム単体群で構成される葉ノード（Ｌｅａｆ）Ｌ７１〜Ｌ７７が作成される。
【００５５】
次に、検索動作の一般例をフローチャートを用いて説明する。
図１２は、検索動作を示すフローチャートである。
以下、現在のノード（の位置）：ノードｖ、現在の合計金額：ｖａｌｕｅ、現在の閾値：閾値α、ノードｕの価格：ｋａｋａｋｕ（ｕ）、スタック：Ｓｔａｃｋ［０．．ｍａｘｄｅｐｔｈ（Ｔ１）］とする。
【００５６】
初期状態としてノードｖ＝ｒｏｏｔ、閾値α＝α０（￥２４００）、Ｓｔａｃｋ［０］＝０とする（ステップＳ１１）。なお、閾値α＝α１（￥２５００）としてもよい。
次に、組み合わせ探索木Ｔのプリオーダ順で次のノードｕが存在するか否かを判断する（ステップＳ１２）。プリオーダ順とは，順序木を時計回り、反時計回りに深さ優先探索して、各節点を、はじめて通ったときに出力して得られる順序である。
【００５７】
次のノードｕが存在する場合（ステップＳ１２のＹｅｓ）、ノードｕに進み、ノードｖ＝ノードｕとする（ステップＳ１２ａ）。
次に、ノードｖが組み合わせ探索木Ｔの葉ノードか否かを判断する（ステップＳ１３）。
【００５８】
ノードｖが葉ノードの場合（ステップＳ１３のＹｅｓ）、葉ノードに含まれるアイテム単体の金額であるｖａｌ＿ｉｔｅｍｓをｖａｌｕｅに加算する（ステップＳ１４）。
次に、ｖａｌｕｅが閾値αより小さいか否かを判断する（ステップＳ１５）。
【００５９】
ｖａｌｕｅが閾値α以上の場合（ステップＳ１５のＮｏ）、ステップＳ１２に移行してステップＳ１２以降の動作を継続して行う。
一方、ｖａｌｕｅが閾値αより小さい場合（ステップＳ１５のＹｅｓ）、ｖａｌｕｅを閾値αに設定する（ステップＳ１６）。
【００６０】
次に、現在のセット、アイテム単体群の組み合わせとｖａｌｕｅとをＲＡＭ１０２に記録（保持）する（ステップＳ１７）。そして、ステップＳ１２に移行してステップＳ１２以降の動作を継続して行う。
【００６１】
ところで、ステップＳ１３にてノードｖが葉ノードではない場合（ステップＳ１３のＮｏ）、
ｖａｌｕｅ＝Ｓｔａｃｋ［ｄｅｐｔｈ（ｕ）−１]+ｋａｋａｋｕ（ｕ）
Ｓｔａｃｋ［ｄｅｐｔｈ（ｕ）]=ｖａｌｕｅ
とする（ステップＳ１８）。すなわち、ノードｕの１つ上位のノードまでのスタック（合計金額）にノードｕでのセット価格を加算し、加算した価格を新たなスタックとする。
【００６２】
次に、ｖａｌｕｅが閾値αより小さいか否かを判断する（ステップＳ１９）。
ｖａｌｕｅが閾値αより小さい場合（ステップＳ１９のＹｅｓ）、ステップＳ１２に移行し、引き続き検索動作を行う。
【００６３】
一方、ｖａｌｕｅが閾値α以上の場合（ステップＳ１９のＮｏ）、組み合わせ探索木Ｔの枝刈りを行う、すなわちノードｕの全ての子孫を組み合わせ探索木Ｔから削除したとみなして探索を省く（ステップＳ２０）。そして、ステップＳ１２に移行し、引き続き検索動作を行う。
【００６４】
また、ステップＳ１２にて次のノードｕが存在しない場合（ステップＳ１２のＮｏ）、ＲＡＭ１０２に記録されているｖａｌｕｅ（最安値）とセット、アイテム単体群の組み合わせとを組み合わせ抽出結果として結果送信部１７０に渡し（ステップＳ２１）、検索動作を終了する。
【００６５】
これにより、検索動作終了時には、最安値となるｖａｌｕｅと、それを与える組み合わせが得られる。このように、最適組み合わせ探索部１６０は、計算途中に前に算出した金額を上回った枝については、枝刈りを行い最後まで計算を行わずに計算を中止する。これにより、計算時間の短縮を図ることができる。
【００６６】
次に、検索動作の具体例について、図１１に示す組み合わせ探索木Ｔを用いて説明する。ここでは初期状態として閾値α＝合計金額α１＝￥２５００とする。
まず、組み合わせ探索木Ｔのノード７１〜７４および葉ノードＬ７１を含むグループ（セット、アイテム単体群の組み合わせ）Ｇ１について探索する。このグループＧ１においてはノード７２（ノードｕ）が存在するためノード７２（ノードｕ）に進み、現在の位置（ノードｖ）をノード７２（ノードｕ）とする。ノード７２（ノードｕ）は葉ノードではないので、セットＡのセット価格￥５００をｖａｌｕｅに加算する。
【００６７】
そして、ｖａｌｕｅを閾値αと比較する。ｖａｌｕｅ（￥５００）＜閾値α（￥２５００）であり、ノード７３（ノードｕ）が存在するためノード７３（ノードｕ）に進み、現在の位置（ノードｖ）をノード７３（ノードｕ）とする。ノード７３（ノードｕ）は葉ノードではないので、セットＢのセット価格￥５００をｖａｌｕｅに加算する。
【００６８】
そして、ｖａｌｕｅを閾値αと比較する。ｖａｌｕｅ（￥１０００）＜閾値α（￥２５００）であり、ノード７４（ノードｕ）が存在するためノード７４（ノードｕ）に進み、現在の位置（ノードｖ）をノード７４（ノードｕ）とする。ノード７４（ノードｕ）は葉ノードではないので、セットＤのセット価格￥２０００をｖａｌｕｅに加算する。
【００６９】
そして、ｖａｌｕｅを閾値αと比較する。ｖａｌｕｅ（￥３０００）＞閾値α（￥２５００）であるため、ノード７４、葉ノードＬ７１間の枝を枝刈りする（葉ノードＬ７１について計算を行わない）。
【００７０】
そして、次のノード（葉ノードＬ７２）が存在するため、葉ノードＬ７２がノードｕ（＝ノードｖ）となる。
次に、組み合わせ探索木Ｔのノード７１〜ノード７３、葉ノードＬ７２を含むグループＧ２について探索する。このグループＧ２においては、セットＢの処理まではグループＧ１と同様である。すなわち、ｖａｌｕｅ（￥１０００）＜閾値α（￥２５００）であり、葉ノードＬ７２（ノードｖ）は葉ノードであるので、葉ノードＬ７２に含まれるアイテム単体の金額の合計を計算し、得られた金額￥１４００をｖａｌｕｅに加算する。
【００７１】
そして、ｖａｌｕｅを閾値αと比較する。ｖａｌｕｅ（￥２４００）＜閾値α（￥２５００）であるため、閾値α＝ｖａｌｕｅ（￥２４００）とする。
そして、現在のセット、アイテム単体群の組み合わせとｖａｌｕｅ（￥２４００）とをＲＡＭ１０２に記録する。
【００７２】
そして、ノード７５がノードｕ（ノードｖ）となる。以下、同様に探索を行う。
ノード７１、７２、７５、葉ノードＬ７３を含むグループは、ノード７５の探索時に、ｖａｌｕｅ（￥２５００）となるので、この時点でノード７５、葉ノードＬ７３間の枝を枝刈りする。
【００７３】
ノード７１、７２、葉ノードＬ７４を含むグループは、葉ノードＬ７４の探索時にｖａｌｕｅ（￥２３５０）となるので、α＝Ｖａｌｕｅ（￥２３５０）とする。
そして、現在のセット、アイテム単体群の組み合わせとｖａｌｕｅ（￥２３５０）とをＲＡＭ１０２に記録（上書き）する。
【００７４】
ノード７１、７６、７７、葉ノードＬ７５を含むグループは、ノード７７の探索時に、ｖａｌｕｅ（￥２５００）となるので、ノード７７、葉ノード７５間の辺を枝刈りする（ノード７７で枝刈りし、その子孫は探索しない）。
【００７５】
ノード７１、７６、葉ノードＬ７６を含むグループは、葉ノードＬ７６の探索時にｖａｌｕｅ（￥２２５０）となるので、α＝Ｖａｌｕｅ（￥２２５０）とし、ノード７６、葉ノードＬ７６間の枝を枝刈りする。
【００７６】
そして、現在のセット、アイテム単体群の組み合わせとｖａｌｕｅ（￥２２５０）とをＲＡＭ１０２に記録（上書き）する。
ノード７１、７８、葉ノードＬ７７を含むグループでは、葉ノードＬ７７の探索時にｖａｌｕｅ（￥３９５０）となるので、この時点でノード７８、葉ノードＬ７７間の枝を枝刈りする。
【００７７】
そして、葉ノードＬ７７まで探索が終了すると、ＲＡＭ１０２に記録されているｖａｌｕｅ（最安値）とセット、アイテム単体群の組み合わせとを組み合わせ抽出結果として結果送信部１７０に渡す。
【００７８】
ここでは、ｖａｌｕｅ（￥２２５０）と、セットＢと品番＃１０１、＃１０２、＃２０１、＃３０１、＃３０２のアイテム単体群の組み合わせとを組み合わせ抽出結果として渡す。
【００７９】
以上述べたように、組み合わせ抽出装置１００によれば、ユーザが購入を希望するアイテムを全て含み、かつ、合計金額が最安値となる組み合わせを容易かつ確実に出力（提示）することができる。
【００８０】
また、組み合わせ探索木Ｔを用いて探索を行うことにより、重複する計算部分の演算を省略することができるので、従来に比べ演算量が指数的に減少する。よって、ＣＰＵへの負荷を軽減することができ、短時間で演算を終了することができる。
【００８１】
また、探索時に閾値αを上回ったグループについてはその時点で枝刈りを行うことにより、ＣＰＵへの負荷を、より軽減することができ、より短時間で演算を終了することができる。
【００８２】
さらに、出力される組み合わせ抽出結果によっては商品データ３０の入力時にはユーザ、オペレータ等が気づかなかった組み合わせを提示することができる。
また、中間ノードにロジック（枝刈り、最安値の判断）を持たせることにより、単純な料金計算以外のロジック搭載を可能としている。これにより、アイテム毎に設定される期間限定のキャンペーン割引や、年齢制限等による購入可否等を容易に判断対象とすることができ、中間ノードにおいて、他の計算条件を含めた計算量の削減を容易に行うことができる。
【００８３】
よって、例えばアイテム、セットの価格に変更が発生した場合においても、最新情報での最安値の組み合わせ選択を容易に行うことができる。特に、新しいセットが次から次へと出現し、組み合わせ候補が膨大となる程、効果が顕著に現れる。
【００８４】
次に、第２の実施の形態の組み合わせ抽出システムについて説明する。
以下、第２の実施の形態の組み合わせ抽出システムについて、前述した第１の実施の形態との相違点を中心に説明し、同様の事項については、その説明を省略する。
【００８５】
第２の実施の形態の組み合わせ抽出システムは、最安値が複数存在した場合の最適組み合わせ探索部１６０の処理方法に特徴を有する。
図１３は、第２の実施の形態のアイテム分解部の動作を示す図であり、図１４は、第２の実施の形態のセット検索部の動作を示す図である。
【００８６】
第２の実施の形態のセット一覧格納部１４０には、セットＤのセット価格がセット一覧テーブル１４１と異なるセット一覧テーブル１４１ａが格納されている。なお、アイテム分解部１２０およびセット検索部１５０の動作については第１の実施の形態と同様であるため、その説明を省略する。
【００８７】
図１５は、第２の実施の形態の最適組み合わせ探索部のＳｅｔＬｉｓｔ作成動作を示す図である。
最適組み合わせ探索部１６０は、第１の実施の形態と同様にしてＳｅｔＬｉｓｔ７０ａを作成する。その後、ＳｅｔＬｉｓｔ７０内の探索木構造に基づいて作成した組み合わせ探索木Ｔ１を探索して最安値を探す。
【００８８】
図１６は、第２の実施の形態の組み合わせ探索木の木構造を示す図である。
この第２の実施の形態においても第１の実施の形態と同様に、最適組み合わせ探索部１６０は、組み合わせ探索木Ｔ１のプリオーダ順で探索を行う。そして、最安値が発見される度に、α＝ｖａｌｕｅとし、組み合わせ探索木Ｔ１を枝刈りしていく。このとき、ｖａｌｕｅと閾値αとを比較したときに、ｖａｌｕｅ＝閾値αとなったグループが複数存在する場合、それぞれのセット、アイテム単体群の組み合わせとｖａｌｕｅ（￥２４００）とをＲＡＭ１０２に記録する。
【００８９】
そして、探索が終了した時点で、これらグループの中の、セット、アイテム単体群を含めたアイテムの数が最も多いグループにおけるセット、アイテム単体群の組み合わせとｖａｌｕｅとを組み合わせ抽出結果として結果送信部１７０に渡す。図１６では、最安値￥２１５０と、セットＢとセットＤと品番＃１０２、＃２０１、＃３０２とを組み合わせ抽出結果として渡す。
【００９０】
この第２の実施形態の組み合わせ探索システムによれば、第１の実施の形態の組み合わせ探索システムと同様の効果が得られる。
そして、第２の実施形態の組み合わせ探索システムによれば、最安、かつ、アイテムの数が最も多いグループを容易に抽出することができるため、ユーザに対してよりお買い得感のある組み合わせを提供することができる。
【００９１】
次に、第３の実施の形態の組み合わせ抽出システムについて説明する。
以下、第３の実施の形態の組み合わせ抽出システムについて、前述した第１の実施の形態との相違点を中心に説明し、同様の事項については、その説明を省略する。
【００９２】
第３の実施の形態の組み合わせ抽出システムは、商品データ３０の合計金額α１より安い値を備えるグループが複数存在した場合の最適組み合わせ探索部１６０の処理方法に特徴を有する。
【００９３】
図１７は、第３の実施の形態のアイテム一覧テーブルを示す図である。
アイテム一覧テーブル１３１ａのデータ構造は、アイテム一覧テーブル１３１と同様であるが、品番＃２０３が追加されており、また、品番＃４０２以下のアイテムについての詳細が図示されている。
【００９４】
また、アイテム一覧テーブル１３１ａには、新たに内容の欄が設定されている。内容の欄には、アイテムの内容（図１７では番組名）が設定されている。
図１８は、第３の実施の形態のセット一覧テーブルを示す図である。
【００９５】
セット一覧テーブル１４１ｂのデータ構造は、セット一覧テーブル１４１と同様であるが、セットＡおよびセットＢに含まれる品番が異なっている。
図１９は、アイテム分解部の動作を示す図である。
【００９６】
アイテム分解部１２０は、検索結果データ６０ｂを作成する。
図２０は、セット検索部の動作を示す図である。
セット検索部１５０は、ＳｅｔＬｉｓｔ７０ｂを作成する。
【００９７】
図２１は、第３の実施の形態の探索動作を示すフローチャートである。
ステップＳ３１〜ステップＳ３５、それぞれステップＳ１１〜ステップＳ１５と同様の動作を行う。
【００９８】
そして、ｖａｌｕｅが閾値αより小さい場合（ステップＳ３５のＹｅｓ）、ｖａｌｕｅを閾値αに設定せずに、現在のセット、アイテム単体群の組み合わせと、ｖａｌｕｅとを組み合わせ抽出結果として結果送信部１７０に渡す（ステップＳ３６）。この際、この組み合わせに含まれるユーザが申し込んでいないアイテム件数と、それらのアイテム名を同時に渡す。
【００９９】
ステップＳ３７〜ステップＳ３９：ステップＳ１８〜ステップＳ２０と同様の動作を行う。
なお、ステップＳ３６にて説明したように、閾値αより安値のセット、アイテム単体群の組み合わせを発見した時点で、結果送信部１７０に組み合わせ抽出結果を渡しているため、ステップＳ２１に対応する動作は行わない。
【０１００】
次に、第３の実施の形態の検索動作の具体例について説明する。
図２２は、第３の実施の形態の組み合わせ探索木の木構造を示す図である。
この第３の実施の形態においても第１の実施の形態と同様に、最適組み合わせ探索部１６０は、組み合わせ探索木Ｔ２のプリオーダ順で探索を行う。そして、閾値αよりも安値のｖａｌｕｅを備えたグループを発見した場合でも閾値α＝２５００のままで（α＝ｖａｌｕｅとせず）組み合わせ探索木Ｔ２を枝刈りしていく。そして、閾値αより安値のｖａｌｕｅを備えたグループが発見された時点で、このグループのｖａｌｕｅとアイテムの組み合わせと商品データ３０に含まれない品番のアイテムの内容とを組み合わせ抽出結果として結果送信部１７０に渡す。図２２では、まず、ｖａｌｕｅ（￥２４００）と、セットＡとセットＢと品番＃２０１、＃３０１、＃３０２のアイテム単体群の組み合わせと、これらのアイテム数と、商品データ３０に含まれない品番のアイテムの内容とを組み合わせ抽出結果として渡す。
【０１０１】
次に、ｖａｌｕｅ（￥２３５０）と、セットＡと品番＃１０４、＃１０５、＃２０１、＃３０１、＃３０２のアイテム単体群の組み合わせと、これらのアイテム数と、商品データ３０に含まれない品番のアイテムの内容とを組み合わせ抽出結果として渡す。
【０１０２】
次に、ｖａｌｕｅ（￥２２５０）と、セットＢとセットＤと品番＃１０１、＃１０２、＃２０１、＃３０１、＃３０２のアイテム単体群の組み合わせと、これらのアイテム数と、商品データ３０に含まれない品番のアイテムの内容とを組み合わせ抽出結果として渡す。
【０１０３】
図２３は、結果表示部により表示された組み合わせ抽出結果を示す図である。
組み合わせ抽出結果画面２２１には、候補、金額、アイテム数、申し込み以外のアイテムの欄が設けられており、各欄の横方向に並べられた情報同士が互いに関連づけられている。
【０１０４】
候補の欄には、組み合わせ抽出結果を識別する名前が設定される。
金額の欄には、組み合わせ抽出結果として出力されたｖａｌｕｅが設定される。
アイテム数の欄には、全てのアイテムの数が設定される。
【０１０５】
申し込み以外のアイテムの欄には、商品データ３０に記載されてないアイテムの品番とその内容とが設定される。
この第３の実施形態の組み合わせ探索システムによれば、第１の実施の形態の組み合わせ探索システム３００と同様の効果が得られる。
【０１０６】
そして、第３の実施形態の組み合わせ探索システムによれば、さらに、ユーザに対し、お買い得感（アイテム数や金額、買いたいアイテムのバランス）のある組み合わせを容易に選択することができる。
【０１０７】
なお、本実施の形態では、安値を発見する度に結果送信部１７０に組み合わせ抽出結果を渡したが、本発明はこれに限らず、例えば予め結果送信部１７０に渡す組み合わせ抽出結果の数を予め設定（例えば３個）しておき、安値を発見する度に組み合わせ抽出結果をＲＡＭ１０２に記録し、ＲＡＭ１０２に記録された組み合わせ抽出結果が３個を超える場合、新たに発見した組み合わせ抽出結果をＲＡＭ１０２に記録されている３個の組み合わせ抽出結果と比較し、これらのうちから最も値の大きい組み合わせ抽出結果除いた３個をＲＡＭ１０２に記録し、探索が終了した時点で、ＲＡＭ１０２に記録されている３個の組み合わせ抽出結果を結果送信部１７０に渡すようにしてもよい。
【０１０８】
以上、本発明の組み合わせ抽出プログラム、組み合わせ抽出方法および組み合わせ抽出装置を、図示の実施の形態に基づいて説明したが、本発明はこれに限定されるものではなく、各部の構成は、同様の機能を有する任意の構成のものに置換することができる。また、本発明に、他の任意の構成物や工程が付加されていてもよい。
【０１０９】
また、本発明は、前述した各実施の形態のうちの、任意の２以上の構成（特徴）を組み合わせたものであってもよく、例えば、閾値αの値を一定にして探索を行い、閾値αより安値のｖａｌｕｅを備えたグループの中の、セット、アイテム単体群を含めたアイテムの数が最も多いグループにおけるセット、アイテム単体群の組み合わせとｖａｌｕｅとを組み合わせ抽出結果として結果送信部１７０に渡すようにしてもよい。
【０１１０】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、組み合わせ抽出装置１００が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等が挙げられる。磁気記録装置としては、例えば、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープ等が挙げられる。光ディスクとしては、例えば、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等が挙げられる。光磁気記録媒体としては、例えば、ＭＯ（Magneto-Optical disk）等が挙げられる。
【０１１１】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１１２】
組み合わせ抽出プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１１３】
（付記１）  アイテムの組み合わせを抽出する組み合わせ抽出プログラムにおいて、
コンピュータを、
値をそれぞれ有する複数のアイテムのセットと、前記セットに付随する値とを有するセットデータが複数格納されたセットデータ格納手段、
複数の前記アイテムを備えるアイテムデータの入力に応答し、前記アイテムデータ内の前記アイテムを２つ以上含む前記セットを前記セットデータ格納手段から検索するセット検索手段、
前記セット検索手段により検索された前記セットと、前記アイテムデータ内の前記セット検索手段により検索された前記セットに含まれない前記アイテムで構成されるアイテム単体群とをこの順番に並べた少なくとも１つの配列を備えるセットリストを作成するセットリスト作成手段、
前記セットリストを参照し、前記アイテム単体群を最終遷移先として前記配列の並びをノード間の遷移で表す探索木を作成し、前記探索木を深さ優先探索する際に前記各配列において、前記セットに付随する値と前記アイテム単体群の前記アイテムそれぞれの値の合計値とを加算していき、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りする枝刈り手段、
前記閾値より小さい前記合計値を備える前記配列の前記セットおよび前記アイテム単体群の組み合わせを出力する組み合わせ出力手段、
として、機能させることを特徴とする組み合わせ抽出プログラム。
【０１１４】
（付記２）  前記コンピュータを、さらに、
前記各アイテムそれぞれの値の値情報が格納されたデータ格納手段、
少なくとも１つの前記アイテムと、前記セットとが混在する混在データ入力に応答し、前記混在データに含まれる前記セットの前記アイテムそれぞれの値を前記値情報から取り出し、前記混在データに含まれる前記アイテム単体の全ての合計値を算出して前記アイテムデータを作成する算出手段、
として機能させることを特徴とする付記１記載の組み合わせ抽出プログラム。
【０１１５】
（付記３）  前記枝刈り手段は、前記混在データに含まれる前記セットの値と前記各アイテムそれぞれの値との合計値を前記閾値とすることを特徴とする付記２記載の組み合わせ抽出プログラム。
【０１１６】
（付記４）  前記枝刈り手段は、前記アイテムデータの前記各アイテムそれぞれの値の合計値を前記閾値とすることを特徴とする付記１記載の組み合わせ抽出プログラム。
（付記５）  前記セットリスト作成手段は、前記セット検索手段により検索された前記セットのうち、前記アイテムデータ内の前記アイテムを含む数の多い前記セットから順番に並べた前記配列を作成することを特徴とする付記１記載の組み合わせ抽出プログラム。
【０１１７】
（付記６）  前記枝刈り手段は、前記配列において、前記セットに付随する値と前記アイテム単体群の前記アイテムそれぞれの値の合計値とが前記閾値より小さいとき、前記合計値をその後の深さ優先探索の前記閾値とすることを特徴とする付記１記載の組み合わせ抽出プログラム。
【０１１８】
（付記７）  前記組み合わせ出力手段は、前記閾値より小さい前記セットおよび前記アイテム単体群の組み合わせが複数存在する場合、複数の前記閾値より小さい前記セットおよび前記アイテム単体群の組み合わせのうち最も多く前記アイテムを含む組み合わせを出力することを特徴とする付記１記載の組み合わせ抽出プログラム。
【０１１９】
（付記８）  前記コンピュータを、前記アイテムに関する付記情報を格納する付記情報格納手段としてさらに機能させ、
前記組み合わせ出力手段は、前記閾値以下の前記セットおよび前記アイテム単体群の組み合わせを出力する際に、全ての前記アイテムまたは前記アイテムデータに含まれていない前記アイテムそれぞれについて前記付記情報を付加して出力することを特徴とする付記１記載の組み合わせ抽出プログラム。
【０１２０】
（付記９）  アイテムの組み合わせを抽出する組み合わせ抽出方法において、
セットデータ格納手段が、値をそれぞれ有する複数のアイテムのセットと、前記セットに付随する値とを有するセットデータを複数格納し、
セット検索手段が、複数の前記アイテムを備えるアイテムデータの入力に応答し、前記アイテムデータ内の前記アイテムを２つ以上含む前記セットを前記セットデータ格納手段から検索し、
セットリスト作成手段が、前記セット検索手段により検索された前記セットと、前記アイテムデータ内の前記セット検索手段により検索された前記セットに含まれない前記アイテムで構成されるアイテム単体群とをこの順番に並べた少なくとも１つの配列を備えるセットリストを作成し、
枝刈り手段が、前記セットリストを参照し、前記アイテム単体群を最終遷移先として前記配列の並びをノード間の遷移で表す探索木を作成し、前記探索木を深さ優先探索する際に前記各配列において、前記セットに付随する値と前記アイテム単体群の前記アイテムそれぞれの値の合計値とを加算していき、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りし、
組み合わせ出力手段が、前記閾値より小さい前記合計値を備える前記配列の前記セットおよび前記アイテム単体群の組み合わせを出力する、
ことを特徴とする組み合わせ抽出方法。
【０１２１】
（付記１０）  アイテムの組み合わせを抽出する組み合わせ抽出装置において、
値をそれぞれ有する複数のアイテムのセットと、前記セットに付随する値とを有するセットデータが複数格納されたセットデータ格納手段と、
複数の前記アイテムを備えるアイテムデータの入力に応答し、前記アイテムデータ内の前記アイテムを２つ以上含む前記セットを前記セットデータ格納手段から検索するセット検索手段と、
前記セット検索手段により検索された前記セットと、前記アイテムデータ内の前記セット検索手段により検索された前記セットに含まれない前記アイテムで構成されるアイテム単体群とをこの順番に並べた少なくとも１つの配列を備えるセットリストを作成するセットリスト作成手段と、
前記セットリストを参照し、前記アイテム単体群を最終遷移先として前記配列の並びをノード間の遷移で表す探索木を作成し、前記探索木を深さ優先探索する際に前記各配列において、前記セットに付随する値と前記アイテム単体群の前記アイテムそれぞれの値の合計値とを加算していき、与えられた閾値以上になったとき、探索中のノードの枝を枝刈りする枝刈り手段と、
前記閾値より小さい前記合計値を備える前記配列の前記セットおよび前記アイテム単体群の組み合わせを出力する組み合わせ出力手段と、
を有することを特徴とする組み合わせ抽出装置。
【図面の簡単な説明】
【０１２２】
【図１】本発明の概要を示す図である。
【図２】実施の形態の組み合わせ抽出システムを示す図である。
【図３】組み合わせ抽出装置のハードウェア構成例を示す図である。
【図４】組み合わせ抽出装置および端末装置の機能を示すブロック図である。
【図５】商品データを示す図である。
【図６】組み合わせ抽出装置の動作を示すフローチャートである。
【図７】アイテム分解部の動作を示す図である。
【図８】アイテム分解部の動作を示す図である。
【図９】セット検索部の動作を示す図である。
【図１０】最適組み合わせ探索部のＳｅｔＬｉｓｔ作成動作を示す図である。
【図１１】組み合わせ探索木の木構造を示す図である。
【図１２】検索動作を示すフローチャートである。
【図１３】第２の実施の形態のアイテム分解部の動作を示す図である。
【図１４】第２の実施の形態のセット検索部の動作を示す図である。
【図１５】第２の実施の形態の最適組み合わせ探索部のＳｅｔＬｉｓｔ作成動作を示す図である。
【図１６】第２の実施の形態の組み合わせ探索木の木構造を示す図である。
【図１７】第３の実施の形態のアイテム一覧テーブルを示す図である。
【図１８】第３の実施の形態のセット一覧テーブルを示す図である。
【図１９】アイテム分解部の動作を示す図である。
【図２０】セット検索部の動作を示す図である。
【図２１】第３の実施の形態の探索動作を示すフローチャートである。
【図２２】第３の実施の形態の組み合わせ探索木の木構造を示す図である。
【図２３】結果表示部により表示された組み合わせ抽出結果を示す図である。
【符号の説明】
【０１２３】
１  コンピュータ
２  セットデータ格納手段
３、３ａ  セット
４、５  セットデータ
６  セット検索手段
７  アイテムデータ
８  セットリスト作成手段
９  セットリスト
１０  枝刈り手段
１１  組み合わせ出力手段
３０、４０  商品データ
５０  商品単価データ
６０、６０a、６０ｂ  検索結果データ
７１〜７８  ノード
１００  組み合わせ抽出装置
１１０  商品データ受信部
１２０  アイテム分解部
１３０  アイテム一覧格納部
１３１、１３１ａ  アイテム一覧テーブル
１４０  セット一覧格納部
１４１、１４１ａ、１４１ｂ  セット一覧テーブル
１５０  セット検索部
１６０  最適組み合わせ探索部
１７０  結果送信部
２００  端末装置
２１０  データ送信部
２２０  結果表示部
３００  抽出システム
Ａ、Ｂ、Ｄ  セット
Ｇ１  グループ
Ｇ２  グループ
Ｌ７１〜Ｌ７７  葉ノード
Ｔ、Ｔ１、Ｔ２  探索木
α  閾値
【図１】
2008112342.tif 000003
【図２】
2008112342.tif 000004
【図３】
2008112342.tif 000005
【図４】
2008112342.tif 000006
【図５】
2008112342.tif 000007
【図６】
2008112342.tif 000008
【図７】
2008112342.tif 000009
【図８】
2008112342.tif 000010
【図９】
2008112342.tif 000011
【図１０】
2008112342.tif 000012
【図１１】
2008112342.tif 000013
【図１２】
2008112342.tif 000014
【図１３】
2008112342.tif 000015
【図１４】
2008112342.tif 000016
【図１５】
2008112342.tif 000017
【図１６】
2008112342.tif 000018
【図１７】
2008112342.tif 000019
【図１８】
2008112342.tif 000020
【図１９】
2008112342.tif 000021
【図２０】
2008112342.tif 000022
【図２１】
2008112342.tif 000023
【図２２】
2008112342.tif 000024
【図２３】
2008112342.tif 000025