(57)【要約】【課題】計算機資源の有効活用を図ることができるネットワークサービスを利用した計算機システムを提供する。【解決手段】サーバから提供される情報に基づいて位置情報を取り扱うアプリケーションがクライアントで実行され、サーバとクライアント間で情報提供と位置情報の共有がなされる既存のネットワークサービスシステムに対して、クライアントには、クライアントで実行するアプリケーションに位置情報を監視し蓄積する手段と、蓄積した位置情報とサーバから提供される情報と照合する手段と、照合結果を蓄積しサーバに送信する手段とを備える。  また、サーバには、前記クライアントの照合する手段におけるサーバから提供される情報を送信する手段と、クライアントにおける照合結果を受信する手段と、クライアントの照合結果を蓄積する手段を備えたことを特徴とする。【選択図】図１
2010227163.tif 000002
【特許請求の範囲】
【請求項１】
サーバから提供される情報に基づいて位置情報を取り扱うアプリケーションがクライアントで実行され、サーバとクライアント間で情報提供と位置情報の共有がなされるネットワークサービスシステムにおいて、
クライアントには、
クライアントで実行するアプリケーションに対して位置情報を監視し蓄積する手段と、
蓄積した位置情報とサーバから提供される情報と照合する手段と、
照合結果を蓄積しサーバに送信する手段を備え、
サーバには、
前記クライアントの照合する手段におけるサーバから提供される情報を送信する手段と、
クライアントにおける照合結果を受信する手段と、
クライアントの照合結果を蓄積する手段
を備えたことを特徴とする
ネットワークサービスを利用した計算機システム。
【請求項２】
ＮＰ完全問題を位置情報にコード化するための変換情報と結果照合のための照合情報がサーバからクライアントに提供され、
クライアントのアプリケーションの位置情報を監視する手段は、前記変換情報を基に位置情報をコード化して蓄積手段へ出力し、
照合手段は蓄積した前記コード対して、ＮＰ完全問題の解に該当するか否かを前記照合情報を基に判定する手段であることを特徴とする
請求項１記載のネットワークサービスを利用した計算機システム。
【請求項３】
クライアントにおいて、監視手段から出力されるアプリケーションの位置情報は、サーバから指示された開始状態でかつ起点に到達してから蓄積を開始し、照合手段における照合結果が不正であるもしくは、サーバから指示された中止状態であれば、開始状態をアイドル状態にし、蓄積した位置情報を破棄することを特徴とする請求項１乃至２記載のネットワークサービスを利用した計算機システム。
【請求項４】
クライアントにおいて、監視手段から出力されるアプリケーションの位置情報がサーバから指示された終点に到達した場合に、照合結果を蓄積したデータベースをサーバに送信し、位置情報を破棄することを特徴とする請求項１乃至２記載のネットワークサービスを利用した計算機システム。
【請求項５】
オンラインゲームの仮想空間における座標もしくは場所を位置情報とすることを特徴とする請求項１乃至２記載のネットワークサービスを利用した計算機システム。
【請求項６】
サーバは、ＷＥＢサーバと計算課題の委託するサーバとがあり、ＵＲＬ（Uniform Resource Locator）を位置情報とすることを特徴とする請求項１乃至２記載のネットワークサービスを利用した計算機システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はＮＰ完全問題の解を得るための、ネットワークサービスを利用した計算機システムに関する。
【背景技術】
【０００２】
大規模な計算に対してはネットワークに接続した既存の複数のコンピュータに分散し、並列処理を行うことで莫大な計算資源への投資を抑えることが考えられている。だだし、莫大な計算資源の確保には、主にボランティアを募って徴収しているが、常に多数の協力を得られないのが課題である。この課題に対して、特許文献１によれば、ネットワークに接続されているコンピュータのほとんどがアイドリング状態であり、その計算資源の確保するために、計算を委託する企業がクライアントにインセンティブを与え、その見返りに計算資源を徴収するという仕組みを提案している。
【特許文献１】特開２００３−００６１７１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
前記従来は、クライアントがアイドリング状態であることが前提であるため、クライアントが本来目的とするアプリケーションを実行している最中に計算資源を徴収することは難しい。また近年、環境問題（ＣＯ２削減）への配慮からオフィスや家庭においては、未使用機器の電源をオフにする習慣が広まっており、インセンティブがあったとしても本来の目的外に対する計算資源の提供には消極的になっている。
【０００４】
本発明は、クライアントが本来目的とするアプリケーションを実行している最中においても計算資源を徴収し、計算資源を有効活用することを目的とする。
【課題を解決するための手段】
【０００５】
前記従来の課題を解決するために、本発明のネットワークサービスを利用した計算機システムにおいては、サーバから提供される情報に基づいて位置情報を取り扱うアプリケーションがクライアントで実行され、サーバとクライアント間で情報提供と位置情報の共有がなされる既存のネットワークサービスシステムに対して、クライアントには、クライアントで実行するアプリケーションに位置情報を監視し蓄積する手段と、蓄積した位置情報とサーバから提供される情報と照合する手段と、照合結果を蓄積しサーバに送信する手段とを備える。
【０００６】
また、サーバには、前記クライアントの照合する手段におけるサーバから提供される情報を送信する手段と、クライアントにおける照合結果を受信する手段と、クライアントの照合結果を蓄積する手段を備えたことを特徴とする。
【０００７】
例えば、ＮＰ完全問題の一つとして有向ハミルトン経路問題がある。有向ハミルトン経路問題は、各頂点間の通行制約に従った起点から終点への経路の中で各頂点を１回ずつ通過するような経路があるか否かを決定する問題である。各頂点をアプリケーション内の位置情報にコード化するための変換情報と結果照合のための照合情報がサーバからクライアントに提供され、前記クライアントのアプリケーションの位置情報を監視する手段は、変換情報を基に位置情報をコード化して、蓄積手段へ出力し、前記照合手段は蓄積したコード対して、有向ハミルトン経路問題の解に該当するか否かを照合情報を基に判定する手段であることを特徴とする。
【０００８】
本構成によって位置情報を扱う既存のネットワークサービスに対して大きな変更を施すことなくＮＰ完全問題を既存アプリケーションに帰着させることが可能となる。
【発明の効果】
【０００９】
本発明は、クライアントが本来目的とするアプリケーションを実行している最中においても計算資源を徴収することが可能となり、計算資源を有効活用することが可能となる。
【発明を実施するための最良の形態】
【００１０】
以下本発明の実施の形態について、図面を参照しながら説明する。
【００１１】
（実施の形態１）
図１は、本発明の実施の形態１におけるオンラインゲームシステムを示す図である。近年のオンラインゲームは、インターネットを介して数千〜数万人規模のプレイヤが数百台のサーバに接続してプレイしており、膨大な計算機資源を確保しているネットワークシステムである。
【００１２】
図１において、ゲームサーバ１００とゲーム機１０６は、ネットワーク１０５を介して相互の情報通信を行う。
【００１３】
ゲームサーバ１００において、従来から備えている手段は、ゲーム進行指示及び情報送受信する手段１０１である。ゲーム進行指示及び情報送受信する手段１０１は、オンラインゲームの仮想空間において他のプレイヤとのコミュニケーションやゲーム内のイベント参加、ゲームシナリオに沿った活動、ゲームシナリオなどの更新などを執り行う。ゲームサーバ１００は、さらに計算課題送信手段１０２、クライアントの結果を受信する手段１０３と、クライアントの結果を蓄積する手段１０４を加えた手段にて構成される。
【００１４】
クライアントであるゲーム機１０６において、従来から備えている手段は、既存のロールプレイングゲーム（以下、ＲＰＧという）１０７である。さらに、進行状況監視手段１０８は、プレイヤのゲームシナリオにおける進行状況やプレイヤの位置を監視する。履歴蓄積手段１０９は、進行履歴を蓄積する。照合手段１１０は、進行履歴とサーバの計算課題送信手段１０２から提供された計算課題に対する照合情報とを照合する。結果送信手段１１１は、照合結果の中で計算課題の正答となる進行履歴をクライアントの結果として送信する。ゲーム機１０６は以上の手段にて構成される。
【００１５】
以上が本実施の形態におけるオンラインゲームシステムの構成である。
【００１６】
さらに主な構成要素について詳細に説明を行う。ＮＰ完全問題を本実施の形態のオンラインゲームシステムに帰着した例をより具体的に説明するために図３〜９を用いて説明する。
【００１７】
（有向ハミルトン経路問題）
説明の簡単化のために図３に示すようなＮＰ完全問題の一つである有向ハミルトン経路問題を計算課題とする。有向ハミルトン経路問題は、各頂点間の通行制約に従った起点から終点への経路の中で各頂点を１回ずつ通過するような経路があるか否かを決定する問題である。図３の例においては、６つの頂点（０）〜（６）があり、起点は（０）、終点は（６）である。頂点を結んでいる矢印の方向にしか進めない制約がある。正答は（０）から（６）までの数字を順番に辿る経路である。
【００１８】
（オンラインゲームの仮想空間への頂点のマッピング）
次に図４（ａ）は、オンラインゲームの仮想空間を示しており国や町が存在している。図３の有向ハミルトン経路問題の頂点（０）〜（６）を、ゲームシナリオにおける関連する国や町にそれぞれ図４（ｂ）を基に割り当てを行う。町７と国８は、未割り当ての地点である。この図４（ｂ）に示す割り当て情報は、計算課題送信手段１０２から送信される情報に含まれる。
【００１９】
なお、本実施の形態においては、国や町などに頂点をマッピングしているが、プレイヤが移動可能な場所もしくは選択可能な情報であれば頂点はマッピング可能である。
【００２０】
（オンラインゲームの仮想空間への経路のマッピング）
次に有向ハミルトン経路問題における通行制約を示すルックアップテーブルが図５に示すように始点と終点のコードで表されており、オンラインゲームの仮想空間においては、図６に示すような割り当てとなる。この図５にルックアップテーブルは、計算課題送信手段１０２から送信される情報に含まれる。
【００２１】
（オンラインゲームの仮想空間におけるプレイヤの進行履歴）
次に図７は、ゲームシナリオにおけるプレイヤの進行履歴を示している。テーブルの行は、時間軸でプレイヤが辿った仮想空間の地点を示しており、また行には進行状況（シナリオの開始・終了）も含まれる。列は、プレイヤがシナリオを実行した回数を示している。図７の情報は、プレイヤのゲームシナリオにおける進行状況やプレイヤの位置を監視する手段１０８によって取得され、履歴蓄積手段１０９に蓄積される。
【００２２】
（進行履歴の照合）
次に図８（ａ）は、計算課題送信手段１０２から送信された通過回数制約に対する確認処理の過程を示している。行は各地点の通過回数を示しており、列は、プレイヤがシナリオを実行した回数と判定を示している。
【００２３】
判定項目は、有向ハミルトン経路問題において１つの頂点に対して１回の通過回数制約であるため、１回であればＴＲＵＥ，１回以外はＦＡＬＳＥになる。
【００２４】
図８（ｂ）は、有向ハミルトン経路問題における通行制約に対する確認処理の過程を示している。行は、時間軸でプレイヤが辿った経路のコードを示しており、履歴蓄積手段１０９に蓄積された情報を基に生成されるものである。列は、プレイヤがシナリオを実行した回数と判定を示している。判定項目は、行に示されているプレイヤが辿った経路のコードが図５のルックアップテーブルのコードの列に存在していれば、通行制約を満たしているとしてＴＲＵＥ、存在していなければＦＡＬＳＥになる。
【００２５】
図８（ａ）と（ｂ）の履歴蓄積手段１０９への展開と上述の照合処理が照合手段１１０にて行われ、最終的に全ての判定結果がＴＲＵＥのみの進行履歴が結果送信手段１１１によって、サーバに結果が送信される。本実施の形態のおいては、３回目のシナリオの実行が全てTRUEになっているので、図７に示す３回目の結果を送信する。
【００２６】
以上が、本実施の形態における主な構成要素の詳細な説明である。
【００２７】
次に本実施の形態における処理フローを示す図２を各構成要素と対応をとりながら説明する。
【００２８】
（ステップＳ２００）  ゲームサーバ１００は、有向ハミルトン経路のコード化手順提供及びゲームシナリオ提供のために図４（ｂ）と図５に示すようなオンラインゲームの仮想空間への頂点と経路のマッピング情報と各頂点の通過回数制約とを計算課題送信手段１０２を介してゲーム機１０６へ送信する。またゲームシナリオ作成者は、あらかじめ有向ハミルトン経路問題における通行制約に合わせて、各地点間におけるプレイヤの移動手段の制約やシナリオによる誘導を設定しておくことで、有効な解を導く確率を高くすることが可能である。
【００２９】
（ステップＳ２０１）  プレイヤは、ゲーム機１０６にてＲＰＧ１０７を実行する。
【００３０】
（ステップＳ２０２）  サーバ１００は、ゲーム進行指示及び情報送受信手段１０１を介してゲーム機１０６のＲＰＧ１０７に対して、ゲーム進行指示及び情報送受信を行う。
【００３１】
（ステップＳ２０３）  進行状況監視手段１０８は、プレイヤの進行状況を監視する。進行状況監視手段１０８は、RPG１０７よりシナリオの開始・終了イベントを受けて、図７に示しているように進行状態を更新する。
【００３２】
（ステップＳ２０４）  進行状況監視手段１０８は、プレイヤがシナリオを開始もしくは進行中かどうかを確認する。進行中を示す状態は、図７の２行目にあるような状態が開始になっていることを確認する。
【００３３】
（ステップＳ２０５）  進行状況監視手段１０８は、プレイヤがシナリオを開始もしくは進行中であれば、図７に示すように通過地点を履歴蓄積手段１０９に蓄積する。
【００３４】
（ステップＳ２０６）  照合手段１１０は、通過回数制約を確認し、履歴蓄積手段１０９に展開した図８（a）に示すような通過回数情報を更新する。履歴蓄積手段１０９に少なくとも２箇所の地点が蓄積されていれば、通行制約を確認し、履歴蓄積手段１０９に展開した図８（ｂ）に示すような通行制約情報を更新する。
【００３５】
（ステップＳ２０７）  照合手段１１０は、通過回数と通行制約を満足しているかどうか確認する。
【００３６】
（ステップＳ２０８）  通過回数と通行制約を満足していなければ、照合手段１１０は、履歴蓄積手段１０９に蓄積された履歴の破棄と状態をリセットする。処理ステップは、S２０１のRPGへ復帰する。
【００３７】
（ステップＳ２０９）  照合手段１１０は、シナリオ終了であるかどうか確認する。
【００３８】
（ステップＳ２１０）  終了であれば、結果送信手段１１１は、結果をサーバ１００に送信し、履歴蓄積手段１０９に蓄積された履歴の破棄と状態をリセットする。終了でなければ、S201のRPGへ復帰する。
【００３９】
（ステップＳ２１１）  クライアント結果受信手段１０３は、ゲーム機１０６の結果送信手段１１１から送信された情報をクライアント結果蓄積手段１０４に蓄積する。
【００４０】
以上が、本実施の形態における処理フローの説明である。
【００４１】
本実施の形態によれば、既存のオンラインゲームに対してＮＰ完全問題を帰着させることが可能となり、ゲーム機がＲＰＧを実行している最中においても計算資源を徴収することが可能となるため、計算資源を有効活用することが可能となる。
【００４２】
なおオンラインゲーム運営会社は、企業、研究機関などから計算課題を受託することで、システムの増強や、プレイヤの会費負担の軽減やサービス向上などによって会員数を増やすことが可能となる。
【００４３】
なお本実施の形態においては、オンラインゲーム対する適用例であるが、サーバとクライアントにて実現するオンラインショッピングモールのような非ゲームの仮想空間においても適用可能である。
【００４４】
（実施の形態２）
図９は、本発明の実施の形態２におけるＷＥＢシステムを示す図である。
【００４５】
ＷＥＢシステムにおけるユーザ数は、実施の形態１におけるオンラインゲームのプレイヤ人口をはるかに超えており、さらに大規模な計算機資源を確保しているネットワークシステムである。
【００４６】
図９において、計算課題委託サーバ９００とＷＥＢサーバ９０１とパーソナルコンピュータ（以下ＰＣという）９０６は、ネットワーク９０５を介して相互の情報通信を行う。
【００４７】
計算課題委託サーバ９００は、計算課題送信手段９０２、クライアントの結果を受信する手段９０３と、クライアントの結果を蓄積する手段９０４を加えた手段にて構成される。
【００４８】
クライアントであるＰＣ９０６において、従来から備えている手段は、既存のＷＥＢブラウザ９０７である。ＵＲＬ監視手段９０８は、ユーザのＷＥＢアクセスにおけるＵＲＬを監視する。履歴蓄積手段９０９は、履歴を蓄積する。照合手段９１０は、履歴とサーバの計算課題送信手段９０２から提供された計算課題に対する照合情報とを照合する。結果送信手段９１１は、照合結果の中で計算課題の正答となる履歴をクライアントの結果として送信する。
【００４９】
以上が本実施の形態におけるＷＥＢシステムの構成である。
【００５０】
さらに主な構成要素について詳細に説明を行うが、簡略化するために実施の形態１との相違点を示すことで説明を行う。
【００５１】
実施の形態１においては、オンラインゲームの仮想空間内に存在する国や町に有向ハミルトン経路問題の頂点をマッピングした。本実施の形態のＷＥＢシステムにおいては、Uniform Resource Locator（以下ＵＲＬという）にマッピングする。また実施の形態１におけるアプリケーションサーバと計算課題等を提供するサーバは、ゲームサーバであったのに対し、ＷＥＢシステムにおいては、計算課題委託サーバ９００とＷＥＢサーバ９０１の２つのサーバ群に分かれる点のみが異なる。
【００５２】
以上が、本実施の形態における主な構成要素の詳細な説明である。
【００５３】
次に本実施の形態における処理フローを示す図１０を各構成要素と対応をとりながら説明する。実施の形態１との説明が重複する箇所は説明を省略する。
【００５４】
（ステップＳ１０００）  計算課題委託サーバ９００は、有向ハミルトン経路のコード化手順提供のために、頂点と経路のマッピング情報と、各頂点の通過回数制約とを計算課題送信手段９０２を介してＰＣ９０６へ送信する。
【００５５】
（ステップＳ１００１）  ユーザは、ＰＣ９０６にてＷＥＢブラウザ９０７を実行する。
【００５６】
（ステップＳ１００２）  ＷＥＢサーバ９０１は、ＷＥＢブラウザ９０７に対して情報送受信を行う。
【００５７】
（ステップＳ１００３）  ＵＲＬ監視手段９０８は、ユーザがアクセスしているＵＲＬを監視している。
【００５８】
（ステップＳ１００４）  ＵＲＬ監視手段９０８は、起点となるＵＲＬをアクセスしたことがあるかを確認する。
【００５９】
（ステップＳ１００５）  ＵＲＬ監視手段９０８は、起点となるＵＲＬにアクセス済であれば、ＵＲＬをコード化した情報を履歴蓄積手段９０９に蓄積する。
【００６０】
（ステップＳ１００６）  照合手段９１０は、通過回数の更新と経路の確認を行う。
【００６１】
（ステップＳ１００７）  照合手段９１０は、通過回数と通行制約を満足しているかどうか確認する。
【００６２】
（ステップＳ１００８）  通過回数と通行制約を満足していなければ、照合手段９１０は、履歴蓄積手段９０９に蓄積された履歴の破棄と状態をリセットする。処理ステップは、S９０１のＷＥＢブラウザへ復帰する。
【００６３】
（ステップＳ１００９）  照合手段９１０は、終点ＵＲＬにアクセスしたかどうか確認する。
【００６４】
（ステップＳ１０１０）  終点ＵＲＬにアクセスしていれば、結果送信手段９１１は、結果をサーバ９００に送信し、履歴蓄積手段９０９に蓄積された履歴の破棄と状態をリセットする。終了でなければ、S９01のＷＥＢブラウザへ復帰する。
【００６５】
（ステップＳ１０１１）  クライアント結果受信手段９０３は、ＰＣ９０６の結果送信手段９１１から送信された情報をクライアント結果蓄積手段９０４に蓄積する。
【００６６】
以上が、本実施の形態における処理フローの説明である。
【００６７】
本実施の形態によれば、既存のＷＥＢシステムに対してＮＰ完全問題を帰着させることが可能となり、ＰＣがＷＥＢアクセスを行っている最中においても計算資源を徴収することが可能となるため、計算資源を有効活用することが可能となる。
【００６８】
なお、本実施の形態におけるクライアントがＰＣであることを想定しているが、ＷＥＢアクセス機能を搭載している端末、例えば携帯電話機、テレビ、ビデオ、カーナビゲーションなどのネット家電に対しても適用範囲を広げることができる。
【産業上の利用可能性】
【００６９】
本発明にかかるネットワークサービスを利用した計算機システムおいては、位置情報を扱う既存のネットワークサービスに対してＮＰ完全問題を帰着させることが可能となるため、計算機資源の有効活用を図ることができる。従って省エネルギー化と計算機資源への投資削減に有用である。
【図面の簡単な説明】
【００７０】
【図１】本発明の実施の形態１におけるオンラインゲームシステムを示す図
【図２】本発明の実施の形態１における処理フロー図
【図３】本発明の実施の形態１における有向ハミルトン経路問題の例を示す図
【図４】（ａ）本発明の実施の形態１におけるオンラインゲーム内の仮想空間を示す図（ｂ）本発明の実施の形態１における有向ハミルトンの頂点とオンラインゲームの仮想空間の対応を示す図
【図５】本発明の実施の形態１における有向ハミルトン経路のコード化と通行制約の照合情報を示す図
【図６】本発明の実施の形態１における有向ハミルトン経路コードを割り当てたオンラインゲームの仮想空間を示す図
【図７】本発明の実施の形態１における監視手段より出力される進行経路の履歴を示す図
【図８】（ａ）本発明の実施の形態１における照合手段での通過回数確認処理を示す図（ｂ）本発明の実施の形態１における照合手段での通行制約確認処理を示す図
【図９】本発明の実施の形態２におけるＷｅｂシステムを示す図
【図１０】本発明の実施の形態２における処理フロー図
【符号の説明】
【００７１】
１００    ゲームサーバ
１０１    ゲーム進行指示及び情報送受信手段
１０２，９０２    計算課題送信手段
１０３，９０３    クライアント結果受信手段
１０４，９０４    クライアント結果蓄積手段
１０５，９０５    ネットワーク
１０６    ゲーム機
１０７    ＲＰＧ
１０８    進行状況監視手段
１０９，９０９    履歴蓄積手段
１１０，９１０    照合手段
１１１，９１１    結果送信手段
９００    計算課題委託サーバ
９０６    ＰＣ
９０７    ＷＥＢブラウザ
９０８    ＵＲＬ監視手段
【図１】
2010227163.tif 000003
【図２】
2010227163.tif 000004
【図３】
2010227163.tif 000005
【図４】
2010227163.tif 000006
【図５】
2010227163.tif 000007
【図６】
2010227163.tif 000008
【図７】
2010227163.tif 000009
【図８】
2010227163.tif 000010
【図９】
2010227163.tif 000011
【図１０】
2010227163.tif 000012