(57)【要約】開始時間ｂと終了時間ｅを有するある時間［ｂ，ｅ］に録画または視聴するためにテレビ番組を同時に選択するシステム（４００）、装置（３００）、及び方法（２００）を提供する。各テレビ番組について、受信と録画に対し１つの値を与え、視聴に対して追加の値を与える。この値は視聴者の好みを表す。選択及び視聴問題を最適（保障される）に解く動的プログラミングアプローチを提供する。動的プログラミングアプローチの鍵となるアイデアは、状態の定義である。状態は、以降のステップを判断するのに必要な、前のステップのすべての関連情報を表す。状態の定義は、番組を受信した後に利用できるチューナが利用可能である時点と、次の番組を視聴するために視聴者が視聴可能である時点とを含む。この状態の定義を用いて、本発明は、録画及び／または視聴のためにある番組を選択する効果を繰り返し表して計算する。考慮するチューナ数とテレビ番組数により、このアプローチの実行時間は指数関数的に増大するが、実際には適切なものである。実行時間が大幅に減るが終了結果の質は変わらない別の実施形態も提供する。
2009509452.tif 000002
【特許請求の範囲】
【請求項１】
時間ｂに始まり時間ｅに終わる時間［ｂ，ｅ］にお気に入りのテレビ番組を受信及び視聴する方法であって、
各々が開始時間ｂｓと終了時間ｅｓと受信値ｖｒｓと視聴値ｖｗｓとを有する、ｓ＝１，．．．，ｎの番号がついたｎ≧１個のお気に入りのテレビ番組の集合Ｓを指定する段階と、
Ｓの番組ｓを受信（及び録画）するｍ≧１個の複数のチューナを設ける段階と、
動的プログラミングアプローチを適用して、指定された番組の集合Ｓの部分集合Ｓｒ⊆Ｓを選択し、視聴もする番組の部分集合Ｓｗ⊆Ｓｒを選択し、Ｓｒ中の番組を前記複数のチューナで衝突無く受信できるようにし、Ｓｗ中の番組を時間［ｂ，ｅ］ないで視聴できるようにし、前記部分集合の合計値を最大化する段階とを有する方法。
【請求項２】
前記適用する段階は、さらに、
Ｓの各番組ｓに対してスキップ、受信、及び視聴よりなる群から選択した動作の１つを実行する段階と、
受信及び付加的に録画をするショーの最適な集合を決定する段階とを有する、請求項１に記載の方法。
【請求項３】
適用する段階は、さらに、Ｓの各番組ｓに対してスキップ、受信、及び受信かつ視聴よりなる群から選択した動作の１つを実行する段階を有する、請求項１に記載の方法。
【請求項４】
指定する段階は、さらに、すべてのｓ＝１，．．．，ｎについて、ｂｓ≦ｂｓ＋１となるように、番組ｓの開始時間ｂｓにより、ｎ≧１個のお気に入りのテレビ番組ｓ＝１，．．．，ｎ−１よりなる集合Ｓを順序付ける段階と、
適用する段階は、さらに、開始時間の昇順に各番組を考慮する段階を有する、請求項１に記載の方法。
【請求項５】
適用する段階は、さらに、Ｓの各番組ｓに対してスキップ、受信、及び受信かつ視聴よりなる群から選択した動作の１つを実行する段階を有する、請求項４に記載の方法。
【請求項６】
適用する段階は、さらに、動的プログラミング状態を表し、次のショーを受信するためにｍ＞１個のチューナの各々が利用可能である時間を含める段階を有する、請求項５に記載の方法。
【請求項７】
前記適用する段階は、さらに、
所定の判断基準を用いて、１つの状態が他の状態に優位に立たれているか判断する段階と、
他の状態に優位に立たれていると判断された状態を除去する段階とを有する、請求項６に記載の方法。
【請求項８】
判断する段階は、連続する状態の各ペアの間でのみ行われる、請求項７に記載の方法。
【請求項９】
すべての開始時間と終了時間を所定時間の倍数に丸める、請求項８に記載の方法。
【請求項１０】
事前にフィルタリングする段階を行って、最初に、所定の最小お気に入り濃度ｐｍｉｎに番組の長さｅｓ−ｂｓをかけたものより小さいお気に入り値ｖｓを有するすべての番組ｓを除去する、請求項９に記載の方法。
【請求項１１】
時間ｂに始まり時間ｅに終わる時間［ｂ，ｅ］中にお気に入りのテレビ番組を受信及び配信をする装置であって、
各々が開始時間ｂｓと終了時間ｅｓと受信値ｖｒｓと視聴値ｖｗｓとを有する、ｓ＝１，．．．，ｎの番号がついたｎ≧１個のお気に入りのテレビ番組の集合Ｓを含むメモリモジュールと、
Ｓの番組ｓを受信（及び録画）するｍ≧１個のチューナと、
動的プログラミングモジュールを実行するように構成されたプロセッサモジュールであって、前記メモリにアクセスして、指定された番組の集合Ｓの部分集合Ｓｒ⊆Ｓを選択し、視聴もする番組の部分集合Ｓｗ⊆Ｓｒを選択し、Ｓｒ中の番組を前記複数のチューナで衝突無く受信できるようにし、Ｓｗ中の番組を時間［ｂ，ｅ］ないで視聴できるようにし、前記部分集合の合計値を最大化するプロセッサモジュールを有する装置。
【請求項１２】
時間ｂに始まり時間ｅに終わる時間［ｂ，ｅ］中にお気に入りのテレビ番組を受信及び配信をする装置であって、
各々が開始時間ｂｓと終了時間ｅｓと受信値ｖｒｓと視聴値ｖｗｓとを有する、ｓ＝１，．．．，ｎの番号がついたｎ≧１個のお気に入りのテレビ番組の集合Ｓを記述するデータ含むメモリモジュールと、
Ｓの番組ｓを受信（及び録画）するｍ≧１個の複数のチューナと、
前記メモリ中の集合Ｓを記述するデータと、前記複数のチューナとを用いて、請求項１０に記載の方法を実行するように構成されたプロセッサモジュールとを有する装置。
【請求項１３】
視聴者がお気に入りの番組のテレビ視聴セッションをスケジューリングするシステムであって、
番組を視聴するテレビセットと、
視聴者のお気に入りのテレビ番組を選択して受信し、開始時間ｂと終了時間ｅとを有する所定時間［ｂ，ｅ］の間に、前記受信した番組の少なくとも一部を前記テレビに表示する、請求項１２に記載の装置と、を有するシステム。
【請求項１４】
メモリに格納されたコンピュータプログラムであって、請求項１に記載の方法を実行する実行可能モジュールと、各々が開始時間ｂｓ、終了時間ｅｓ、受信値ｖｒｓ、視聴値ｖｗｓを有する、ｓ＝１，．．．，ｎ−１で番号付けされたｎ≧１個のお気に入りのテレビ番組を有する、請求項１の方法の入力として集合Ｓを含むデータモジュールとを有するコンピュータプログラム。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
本発明は、一定の時間に同時に録画と視聴をするために、事前に指定したお気に入り番組のセットからテレビ番組を選択する動的プログラミングの使用に関する。
【０００２】
地上波放送、衛星放送、ケーブルテレビにより、視聴可能なテレビジョンチャンネル数は増え続けており、視聴及び録画するテレビ番組を視聴者が選択するのは、手作業で行うには大変過ぎる。デジタルテレビジョンの出現により、選択するチャンネル数及びオプション数は増大している。それゆえ、視聴者は利用できるすべてのコンテンツを概観することはもはやできず、視聴者が非常に興味を持つであろうテレビ番組を見損なう可能性が高まりつつある。
【０００３】
毎週の視聴可能なテレビ番組数は多いので、印刷された番組ガイドはもはや存続可能なオプションではない。使うのが大変過ぎるからである。多数のチャンネルで視聴可能なテレビ番組をテレビ画面に表示する電子番組ガイド（ＥＰＧ）がこの問題の解決策となる。しかし、表示できる情報量は限られている。例えば、画面に表示される部分のチャンネル数と時間的長さは非常に限られている。この種の情報に対してはテレビ画面の解像度は低いからである。また、解像度が十分高いとしても、視聴可能なテレビコンテンツをすべて予定に入れると、平均的な視聴者は圧倒されてしまうだろう。
【０００４】
どのテレビ番組を選択し、それをいつ視聴するかという視聴者の問題、すなわち、視聴者ごとの視聴計画を作る問題を軽くするため、ＥＰＧにはキーワードによる検索（フィルタリング）のオプションがある。こうして、ＥＰＧにより、視聴者がスクリーニング及び選択すべきテレビ番組の数が、扱える数に減らす。視聴者が、興味がない複数のテレビ番組を間引くもう一つの方法は、人口知能（ＡＩ）技術に基づくリコメンダシステム（recommender  system）を使用することである。これらのＡＩリコメンダシステムは、視聴者が何を好きで何が嫌いかを示すその視聴者のお気に入りプロファイル（preference  profile）を持っており、このプロファイルを利用して、新しく提供される各番組に、視聴者がその番組をどの程度好むかに関する得点を付ける。そして、視聴者ごとの所定の許容値を超える点数がついた番組をＥＰＧ中でハイライトするか、またはこれらの番組のリストを視聴者に提示する。しかし、これらの解決策の問題は、番組が時間的に重なっているかどうかを考慮しておらず、視聴者は、例えば晩に視聴する点数が高いテレビ番組の予定を自分で作らなければならない。換言すると、フィルタやリコメンダで個々の番組のリストは得られるが、かかるリストは、視聴する番組の予定を作るという視聴者の問題に対する不完全な解決策である。
【０００５】
テレビ番組の録画でも同様な場合がある。
【０００６】
必要な解決策は、チューナの数が限られており、共用しなければならない場合に、ある時間に、２つのステップを１つにし、すなわち、同時に視聴及び録画する番組を選択するものである。
【０００７】
本発明によるシステム、装置、及び方法は、同時に、視聴し録画するために連続したテレビ番組のシーケンスを集めることにより、パーソナル化されたテレビ視聴の晩を提供する方法を提供する。かかるシーケンスを集める前に、放送スケジュールに現れる視聴者のお気に入りのテレビ番組の集合を選択する。
【０００８】
時間シフトを入れる時（番組を録画して後で視聴する場合）は、複数のチューナを利用でき、視聴する番組の合計時間の制限が与えられ、本発明は、時間シフトを含む番組選択問題を解いて最適化する動的プログラミングアプローチを提供する。実験によると、時間シフトを含む実施例は、実際の問題事例において適切な時間で実行できた。さらに、別の実施形態により、最適解を見つけるという保障はなくなるが、実行時間を短縮することができる。
【０００９】
本発明のシステム、装置、及び方法により、視聴者にある時間の最適なテレビ体験（TV  experience）を決定する方法を提供する。この体験には、複数のチューナを用いてお気に入りのテレビ番組を視聴するだけでなく録画することも含まれる。
【００１０】
時間シフト視聴
視聴者のスケジューリング問題には２つの側面がある。第１の側面は、受信（して録画）する番組の選択である。第２の側面は、この第１の選択から、ある時間（例えば、その晩）にどの番組をいつ視聴するか決定しなければならない。
【００１１】
番組ごとにそれを受信する場合にある値を与え、その番組を視聴する選択もした場合、追加の値を与える。例えば、スポーツ番組に、受信（及び録画）する場合にある値を割り当て、放送の日の晩に視聴できたら、追加の値を与える。
【００１２】
複数のチューナを用いて番組を完全に受信した場合を考える。
【００１３】
時間シフト番組選択問題（ＴＳＳＰ）の実施形態
視聴者がお気に入りであると指定したテレビ番組の集合をＳとし、各番組ｓに対して、開始時間をｂｓ、終了時間をｅｓ、チューナ数をｍ＞１とする。さらに、各番組ｓに対して、その番組を受信するとｖｒｓが与えられ、その番組を視聴すると追加的に値ｖｗｓが与えられる。また、開始時間をｂ、終了時間をｅとし、時間［ｂ，ｅ］中に視聴者が番組を視聴することを欲しているとする。
【００１４】
本発明のシステム、装置、及び方法は、いつもたかだかｍ個の番組を受信しなければならないように、受信（及び録画）する番組の部分集合Ｓｒ⊆Ｓと、視聴する番組の部分集合Ｓｗ⊆Ｓｒとを決定する。すなわち、
すべての時間ｘについて、
【００１５】
【数１】
2009509452.tif 000003
であり、視聴するために選択された番組の集合Ｓｗを時間［ｂ，ｅ］中にスケジューリングでき、次式
【００１６】
【数２】
2009509452.tif 000004
で与えられるこの解の合計値が最大化されるようにする。
【００１７】
視聴するために選択された集合Ｓｗを時間［ｂ，ｅ］中にスケジューリングできるという制約条件は、この集合中の各番組について、その視聴を開始する時間ｗｓも決定し、すべてのｓ∈Ｓｗについて、
【００１８】
【数３】
2009509452.tif 000005
であり、すべてのｓ，ｔ∈Ｓｗ，ｓ≠ｔについて、
【００１９】
【数４】
2009509452.tif 000006
であることを意味する。
【００２０】
視聴するために選択された番組をスケジューリングすることにより、スケジュールにギャップが入れられるかもしれないことに留意せよ。かかるギャップが入れられるのは、例えば、番組の値が非常に高いとき、その番組が放送されるのを少しの時間待った方がよい場合である。
【００２１】
上記の問題は、一般的には、例えば晩などの限られた時間について解く。Ｓｗ中の番組は同じ晩に視聴でき、一方、Ｓｒ＼Ｓｗ中の番組は別の機会に視聴できる。例えば、Ｓｗ中の番組が期待を裏切るものであったり、別の日によい番組が放送されていない場合に使用できる。
【００２２】
視聴のための番組のスケジューリング
定理実現可能性を損なうことなく、視聴するために選択された番組の集合Ｓｗを、時間［ｂ，ｅ］中に、開始時間の順にスケジューリングすることができる。
【００２３】
証明実現可能なスケジュールがあるとし、すべてのｓ∈Ｓｗの開始時間をｗｓとする。２つの番組ｓ、ｔがあり、ｓはｔの直前にスケジューリングされているが、ｔはｓの前に視聴可能である（すなわち、ｂｔ＜ｂｓ）とする。このとき、ｓとｔを交換してもスケジュールは実現可能である。これは次の説明から分かる。
【００２４】
番組ｓとｔ以外はすべての番組の開始時間が同じスケジュールｗ′を考える。ｓとｔの開始時間は
【００２５】
【数５】
2009509452.tif 000007
で与えられる。
【００２６】
これらの番組は相前後している。この交換を示した図１を参照せよ。この交換により影響を受けるのは番組ｓとｔだけであり、他の番組には影響はないので、制約条件を満たすかどうかチェックするのはｓとｔだけでよい。このため、次式を導く：
【００２７】
【数６】
2009509452.tif 000008
それゆえ、視聴する番組のスケジューリングは、開始時間の昇順で行える。さらに、受信する番組にチューナを割り当てるのは、時間グラフ（interval  graph）を色分けすることに対応し、いわゆる左端色分けアルゴリズム（left-edge  coloring  algorithm）により開始時間の昇順で行える。これにより、動的プログラミングアプローチを適用でき（このアプローチでは、番組を開始時間の昇順で反復的に考慮する）、各番組をスキップするか、受信するか、受信して視聴するか決定できる。ここから後は、番組には番号ｓ＝１，２，．．．，ｎが付され、すべてのｓ＝１，．．．，ｎ−１についてｂｓ＜ｂｓ＋１であると仮定する。
【００２８】
動的プログラミングアプローチ
好ましい実施形態は動的プログラミングアプローチである。このアプローチでは、テレビ番組を開始時間の昇順で検討する。状態空間は、ある番組ｓを考えるとき、その番組ｓをスキップ、受信、または受信及び視聴する（時間シフトされる場合もある）か決定するために、事前に行われた決定に関する情報はすべて利用できるように選択される。
【００２９】
それゆえ、好ましい実施形態では、次の番組を受信するために各チューナを（再び）利用できる時以降、及び次の番組を視聴するためにスケジューリングできる時以降の時間で状態が与えられる。この情報があると、検討中の次の番組ｓをスキップ、受信、または受信及び視聴するどうか、及びこれらの選択によりどんな効果があるか、決定できる。一般性を失うことなく、すべてのチューナは同じなので、チューナの時間を非降順にソートすることができる。
【００３０】
状態を追跡する（keep  track）上記のパラメータに加えて、各状態について、受信及び視聴するためにすでに選択された番組の値が保持される。さらに、各状態について、受信と視聴のために選択された番組の各集合ＳｒとＳｗが記憶されているので、後で何が解か単に読み出すことができる。
【００３１】
もっと形式的には、状態は（ｍ＋４）組（ａ１，．．．，ａｍ；ａ；ｖ；Ｓｒ．Ｓｗ）により与えられる。ここで、ａ１，．．．，ａｍは各チューナが再び利用できる時間であり、すべてのｉ＝１，．．．，ｍ−１についてａｉ≦ａｉ＋１であり、ａは視聴者が次の番組を視聴する準備ができる時間を示し、ｖは今までに選択された番組の合計値である。
【００３２】
動的プログラミングの開始状態は、すべてのｉ＝１，．．．，ｍについてａｉ＝ｂ１により与えられる。すなわち、どの番組の開始時点でもチューナは利用可能であり、ａ＝ｂである。すなわち、視聴者は時間ｂ以降視聴を開始できる、値ｖ＝０であり、集合Ｓｒ＝Ｓｗ＝φである。可能な状態の集合は、最初、Ｐ０＝｛（ｂ１，．．．，ｂ１；ｂ；０；φ；φ）｝である。
【００３３】
次に、動的プログラミングアプローチの繰り返しｓ＝１，．．．，ｎの始めにおいて、可能な状態Ｐｓ−１の集合が与えられると、この繰り返しの終わりにおける可能な状態Ｐｓの集合を次のように計算できる。各状態（ａ１，．．．，ａｍ；ａ；ｖ；Ｓｒ．Ｓｗ）∈Ｐｓ−１について、考えている問題ｓに対して（多くて）３つの取り得る動作がある：
１.  第１の動作は、単に番組ｓをスキップすることである。これにより状態は全く変わらず、Ｐｓにおいて同じ状態（ａ１，．．．，ａｍ；ａ；ｖ；Ｓｒ．Ｓｗ）が得られる。
【００３４】
２.  第２の動作は、番組ｓの受信である。この動作は、チューナが時間ｂｓで利用できる場合にのみ可能である。チューナが利用可能な時間はソートされているので、ａ１≦ｂｓが成り立つかどうか調べることにより、調べられる。成り立つ場合、この第１のチューナを番組の受信に使用でき、このチューナは終了時間ｅｓにまた利用可能である。そこで、Ｐｓにおいて、新しい状態（ｅｓ，ａ２，．．．，ａｍ；ａ；ｖ＋ｖｒｓ；Ｓｒ∪｛ｓ｝，Ｓｗ）が得られ、利用できる時間ｅｓ，ａ２，．．．，ａｍが次にソートされる。
【００３５】
３.  第３の動作は、受信及び視聴（時間シフトされる場合もある）のために番組ｓを選択することであり、これは時間ｂｓにチューナが利用可能である場合、すなわち、ａ１≦ｂｓであり、番組ｓを視聴する時間がまだある場合にのみ可能である。後者の場合、視聴者は時間ａ以降は視聴することができ、番組は時間ｂｓ以降視聴することができるので、この番組の視聴は時間ｗｓ＝ｍａｘ｛ａ，ｂｓ｝に開始できる。ａ＞ｂｓである場合、番組は時間シフトされ、すなわち、録画される。番組の視聴は時間ｅまでに終了しなければならないので、ｍａｘ｛ａ，ｂｓ｝＋ｅｓ−ｂｓ≦ｅでなければならない。これらの２つの条件を満たすと、番組ｓを視聴のために選択できる。再び、第１のチューナを番組の受信に使用するので、時間ｅｓには再び利用可能である。さらに、番組を時間ｗｓ＝ｍａｘ｛ａ，ｂｓ｝に視聴するようにスケジューリングし、視聴者は時間ｗｓ＋ｅｓ−ｂｓ以降、視聴を続けることができる。そこで、新しい状態
【００３６】
【数７】
2009509452.tif 000009
が得られる。ここで、利用可能時間ｅｓ，ａ２，．．．，ａｍは再びソートされている。
【００３７】
次に、状態の集合Ｐｓを削ってもよい（pruned）。一部の状態が他の状態より優位になるからである。しかし、その前にＰｓ中の状態を次のように更新する。次の番組は時間ｂｓ＋１（ｂｎ＋１＝∞と定義してもよい）に始まり、その後の番組はそれより早くには始まらないので、チューナ利用可能時間ａｉ＜ｂｓ＋１を利用可能時間ａｉ＝ｂｓ＋１に置き換えてもよい。同様に、ｂｓ＋１＞ａである場合、視聴者が再び視聴をできる時間ａをｂｓ＋１で置き換える後者の場合、対応する状態の視聴スケジュールにはギャップがあることに留意せよ。
【００３８】
更新ステップの後、非優位（dominated）な状態を削除する。次の３つの条件
【００３９】
【数８】
2009509452.tif 000010
が成り立つ場合にのみ、状態
【００４０】
【数９】
2009509452.tif 000011
は、他の状態
【００４１】
【数１０】
2009509452.tif 000012
より優位であると言う。
【００４２】
状態σにおいてチューナの使用可能性と視聴者の視聴可能性は、状態σ′におけるよりも遅くなく、一方、σの値は少なくともσ′と同じくらいよい。この場合、σ′は最適性を損なわずにＰｓから除去できる。これにより、状態集合が小さくなり、アルゴリズムの実行時間が短くなる。
【００４３】
すべての非優位（dominated）な状態を削除するために、状態の各ペアについてチェックする。これには状態数の二乗のステップ数がかかる。現実にはこれには時間がかかりすぎるので、好ましい実施形態では、より簡単なチェックを行う。最初に状態をソートし、次に連続する状態の各ペアを比較する。この結果、優位性のチェックにかかる実行時間と、状態空間を小さくすることにより節約できる実行時間の間をうまくトレードオフ（trade-off）することができる。図２に、動的プログラミングアプローチによる擬似コードを示した。
【００４４】
実行時間の改善
代替的な３つの実施形態により、最適解を見つけるという保障はないが、実行時間を短縮することができる。
【００４５】
１．時間の精度を粗くすることにより状態空間を減らす
本発明の動的プログラミングアプローチの鍵は、非優位状態を削除することにより各ステップの後に状態空間を小さくし、これにより、状態空間を小さく保つことができることである。この場合の重要な要因は、問題事例の時間精度である。全体の時間的長さと比較して時間精度が比較的粗いとき、利用可能時間の数は非常に少ない。例えば、すべての番組が３０分ごとに開始及び終了し、最も早い時点が１８：００であり、最も遅い時点が２３：００であるとすると、（各チューナと各視聴者の）各利用可能時間には１１個の値のみがある（can  assume  only  11  values）。チューナが２つあれば、チューナの利用可能時間のペア（ａ１，ａ２）は６６通りあり、状態空間には番組の数に拘わらず多くて６６×１１＝７２６個の状態がある。しかし、時間格子が１分であれば、可能な利用可能時間の数はもっと多くなり、状態空間は非常に大きくなる。
【００４６】
状態空間が非常に大きくなることを避ける方法は、意図的に時間精度を粗くすることである。例えば、すべての時間を５分の倍数に丸めてもよい。好ましい実施形態では、視聴者の視聴可能時間に対して、切り上げのみを行う。時間を丸めて視聴するために選択した番組は、時間が丸められていなければ、確実に視聴できる。換言すると、見つかった解は実行可能であることが保障されるが、最適性は失われるかも知れない。利用可能時間を時間格子の最寄りの（必ずしも高くはない）倍数に丸めることもできるが、その解は終了時間ｅを越えてしまうこともある。
【００４７】
好ましい実施形態では、チューナｉ＝１，．．．，ｍの利用可能時間ｅｎのみを切り上げる（rounded  upwards）。しかし、このアプローチの欠点は、１つのチャンネルの相前後する２つの番組において、どちらか一方が選択されないことがあることである。例えば、第１の番組が選択され、対応するチューナがこの番組の終了時間から利用可能であるとき、この利用可能時間を切り上げすることにより、この同じチューナで次の番組を受信できないという結論になるかも知れない。番組の開始及び終了時間が、１つの番組の終了と、同じチャンネルの次の番組の開始との間にギャップがあるようになっていれば（例えば、間にコマーシャルがあることによる）、丸めによるこの効果は生じない。さらに、番組の始めを見逃しても問題なければ、時間切り上げにより生じる問題を、すべての開始時間を一定量切り上げることにより解決することができる。
【００４８】
２．番組のフィルタリング
別の好ましい実施形態では、事例を解く前に番組の集合を削る（prune）ことにより、動的プログラミングアプローチの実行時間を短縮する。このため、番組のお気に入り密度（preference  density）に下限ｐｍｉｎを設定し、値ｖｓ＜ｐｍｉｎ（ｅｓ−ｂｓ）であるすべての番組を削除する。この事前フィルタリングステップの鍵は、興味のない多数の番組が削除されるが、興味のある多数の番組が保持されて選択できることである。
【００４９】
３．２ステップアプローチ
さらに別の実施形態では、２ステップアプローチを使うことにより実行時間を短縮する。このため、動的プログラミング問題を、最初に、番組ごとにそれをスキップするか視聴するために選択するかいずれかのオプションのみの場合について解く。それゆえ、番組を受信するだけ（視聴はしない）のオプションはこの実施形態では考慮しない。この実施形態により状態空間の拡大が小さくなる。
【００５０】
次に、番組の最適集合Ｓｗを視聴するために選択した時に、どの番組を追加的に（録画のために）受信できるか決定する。そこで、Ｓｗを固定しておいて、Ｓｗに加えて受信する番組の最適集合Ｓｒを決定する。
【図面の簡単な説明】
【００５１】
【図１】直接後に続く番組ｓとｔの交換を示す図である。
【図２】動的プログラミングアプローチの擬似コードを示す図である。
【図３】本発明による方法を実行する装置を示す図である。
【図４】本発明によるテレビ番組のセットを受信、録画、表示するシステムを示す図である。
【図１】
2009509452.tif 000013
【図２】
2009509452.tif 000014
【図３】
2009509452.tif 000015
【図４】
2009509452.tif 000016
【国際調査報告】
2009509452.tif 000017
2009509452.tif 000018