(57)【要約】  システムを構成する属性間に依存関係が存在するシステムの変更手順を適切に生成できる変更手順生成システム等を提供する。かかる変更手順生成システムは、所定の状態のシステムを構成する属性の属性値の変更目的の状態の前記システムを構成する前記属性の属性値への変更に要する属性ごとの手順数の総和に対して前記変更において他の属性の属性値が変更される所定値未満の属性の数を加算し前記所定値を減算することによって到着推定距離を計算する計算手段を含む。
2017138506.tif 000002
【特許請求の範囲】
【請求項１】
所定の状態のシステムを構成する属性の属性値の変更目的の状態の前記システムを構成する前記属性の属性値への変更に要する属性ごとの手順数の総和に対して前記変更において他の属性の属性値が変更される所定値未満の属性の数を加算し前記所定値を減算することによって到着推定距離を計算する計算手段を備える
ことを特徴とする変更手順生成システム。
【請求項２】
前記計算手段は、所定の状態のシステムを表す隣接頂点と変更目的の状態の前記システムを表す終了頂点とを入力とし、属性ごとの手順数の総和に相当する前記隣接頂点から前記終了頂点までのマンハッタン距離を用いて前記隣接頂点に関する到着推定距離を計算する
請求項１記載の変更手順生成システム。
【請求項３】
最短距離頂点を選択する選択手段を備え、
前記計算手段は、初期状態のシステムを表す開始頂点から隣接頂点までの確定距離を計算し、
前記選択手段は、前記隣接頂点と前記隣接頂点に関する前記確定距離および前記到着推定距離とを入力とし、入力された前記隣接頂点の中で前記確定距離と前記到着推定距離の和が最短の隣接頂点を前記最短距離頂点に選択する
請求項２記載の変更手順生成システム。
【請求項４】
前記選択手段により選択された複数の前記最短距離頂点で構成された経路を最短経路として取得する取得手段を備える
請求項３記載の変更手順生成システム。
【請求項５】
前記取得手段により取得された前記最短経路を表示する表示手段を備える
請求項４記載の変更手順生成システム。
【請求項６】
前記所定値は、２である
請求項１から請求項５のうちのいずれか１項に記載の変更手順生成システム。
【請求項７】
所定の状態のシステムを構成する属性の属性値の変更目的の状態の前記システムを構成する前記属性の属性値への変更に要する属性ごとの手順数の総和に対して前記変更において他の属性の属性値が変更される所定値未満の属性の数を加算し前記所定値を減算することによって到着推定距離を計算する
ことを特徴とする変更手順生成方法。
【請求項８】
所定の状態のシステムを表す隣接頂点と変更目的の状態の前記システムを表す終了頂点とを入力とし、属性ごとの手順数の総和に相当する前記隣接頂点から前記終了頂点までのマンハッタン距離を用いて前記隣接頂点に関する到着推定距離を計算する
請求項７記載の変更手順生成方法。
【請求項９】
コンピュータに、
所定の状態のシステムを構成する属性の属性値の変更目的の状態の前記システムを構成する前記属性の属性値への変更に要する属性ごとの手順数の総和に対して前記変更において他の属性の属性値が変更される所定値未満の属性の数を加算し前記所定値を減算することによって到着推定距離を計算する計算処理
を実行させるプログラムを記録するプログラム記録媒体。
【請求項１０】
コンピュータに、
所定の状態のシステムを表す隣接頂点と変更目的の状態の前記システムを表す終了頂点とを入力とし、属性ごとの手順数の総和に相当する前記隣接頂点から前記終了頂点までのマンハッタン距離を用いて前記隣接頂点に関する到着推定距離を計算する計算処理を実行させる
請求項９記載のプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、変更手順生成システム、変更手順生成方法および変更手順生成プログラムに関し、特にシステム構成の変更手順を高速に生成できる変更手順生成システム、変更手順生成方法および変更手順生成プログラムに関する。
【背景技術】
【０００２】
コンピュータ、およびコンピュータ同士を通信可能に接続する通信ネットワークで構成されたICT(Information and Communication Technology)システムの構成は、要求の変化や外部環境の変化に伴って変更される。【０００３】
例えば、ICTシステムに対する負荷が高くなれば、ICTシステムにサーバが追加される。また、ソフトウェアのライブラリのバージョンが更新されれば、更新されるライブラリを使用するアプリケーションプログラムが搭載されたコンピュータに導入されているライブラリのバージョンも更新されることが求められる。【０００４】
特許文献１には、上記のようなICTシステムを更新する一般的なシステム構成変更装置が記載されている。図１１は、一般的なシステム構成変更装置の構成例を示すブロック図である。【０００５】
図１１に示すシステム構成変更装置では、システム変更指示手段からシステム変更指示が出力されると、指示が示すシステム変更を実現するために、機能間依存ルール部が依存関係を有する手順を探索し、探索された手順を実行する。例えば、ソフトウェアライブラリのバージョンの更新処理が実行されるとき、更新されるライブラリが依存する他のライブラリのバージョンの更新処理も実行される。【０００６】
上記のようなソフトウェアライブラリ等のシステムを構成するコンポーネント間に存在する依存関係が単純であれば、システム構成の変更手順は、容易に求められる。システム構成は、求められた変更手順に基づいて変更される。しかし、システムが多数のソフトウェア、サーバ、または通信ネットワーク等のコンポーネントで構成されていると、コンポーネント間に存在する各依存関係を検討しつつ変更手順を求めることは困難である。【０００７】
図１２は、Webシステムにおける依存関係の例を示す説明図である。図１２における（ａ）は、Webシステムの構成例を示す説明図である。図１２における（ａ）に示すように、Webサーバは、OS(Operating System)において起動する。また、Webサーバは、OSに搭載されているバージョンがv1のライブラリlib（以下、lib v1と呼ぶ。）を利用している。また、WebサーバにおいてWebアプリケーションである、バージョンがv1の複数のAP（以下、AP v1と呼ぶ。）が稼働している。【０００８】
また、図１２における（ｂ）は、図１２における（ａ）に示す各コンポーネントの状態の遷移と、状態間に存在する依存関係を示す説明図である。図１２における（ｂ）に示す実線の矢印は、状態の遷移を表す。例えば、AP v1の状態は、「稼働」、「停止」、「非搭載」の順に遷移する。【０００９】
また、図１２における（ｂ）に示す破線の矢印は、状態間に存在する依存関係を表す。例えば、AP v1の状態「停止」および「非搭載」は、Webサーバの状態が「起動」である時に実現される。【００１０】
上記を踏まえて、図１２における（ａ）に示すWebシステムにおいて、WebアプリケーションであるAPのバージョンをv1からv2に更新する場合、すなわちAP v1をAP v2に置換する場合の作業手順を、図１２における（ｂ）を参照して考える。なお、AP v2は、図１２における（ｂ）に示すように稼働する際にlib v1の代わりにバージョンがv2のlibであるlib v2を使用する。【００１１】
AP v1をAP v2に置換するために、Webシステムの管理者は、最初にAP v1を停止させる。停止させた後、管理者は、WebサーバからAP v1をアンインストールし、Webサーバの状態をAP v1が搭載されていない状態にする。なお、図１２における（ｂ）に示すように、上記の作業は、Webサーバが起動状態であるという条件下で実行される。【００１２】
次いで、Webシステムの管理者は、ライブラリをlib v1からlib v2に更新するために、Webサーバを停止させる。Webサーバを停止させた後、管理者は、lib v1を停止させ、OSからlib v1をアンインストールする。アンインストールした後、管理者は、OSにlib v2をインストールする。【００１３】
次いで、Webシステムの管理者は、Webサーバを再び起動させる。起動させた後、管理者は、WebサーバにAP v2をインストールする。以上の作業が実行されることによって、図１２における（ａ）に示すWebシステムにおいて、AP v1がAP v2に置換される。【００１４】
コンポーネントの状態が変更されるシステムの構成変更は、頂点と向きを持つ辺とで構成されたグラフである有向グラフで表される。図１３は、システムの構成変更を表す有向グラフの例を示す説明図である。以下、図１３に示すような有向グラフを状態グラフとも呼ぶ。【００１５】
図１３に示す状態グラフの頂点は、システムの状態を表す。図１３に示す状態グラフの頂点は、システムを構成する各コンポーネントの状態で構成される。具体的には、図１３に示す左の頂点は、AP v1の「起動」、AP v2の「非搭載」、Webサーバの「起動」、lib v1の「起動」、lib v2の「非搭載」の各状態で構成される。また、図１３に示す右の頂点は、AP v1の「起動」、AP v2の「非搭載」、Webサーバの「停止」、lib v1の「起動」、lib v2の「非搭載」の各状態で構成される。【００１６】
また、図１３に示す状態グラフの辺は、システムの構成変更を表す。具体的には、図１３に示す左の頂点から右の頂点に向かう辺は、Webサーバの状態が「起動」から「停止」に変更されるシステムの構成変更を表す。【００１７】
ICTシステムの現在の構成を要求される構成に変更する作業手順を作成することは、有向グラフにおけるICTシステムの現在の状態を表す頂点を始点にし、ICTシステムの要求される状態を表す頂点を終点にする経路を検出することに相当する。経路の長さが作業手順の多さに対応することを踏まえると、検出される経路は、経路候補の中の最短経路であることが好ましい。【００１８】
よって、システムの構成変更の定義が有向グラフで表される場合、構成変更の作業手順を作成する問題は、有向グラフにおける変更前の状態を表す始点と変更後の状態を表す終点を結ぶ最短経路を発見する問題になる。【００１９】
有向グラフ内の最短経路を発見する方法には、非特許文献１に記載されているダイクストラ法や、探索処理が高速化されたダイクストラ法である非特許文献２に記載されているA*探索法がある。ダイクストラ法はA*探索法の一実施形態であると考えられるので、A*探索法を以下に説明する。【００２０】
図１４は、一般的なシステム構成変更手順生成装置１００の構成例を示すブロック図である。システム構成変更手順生成装置１００は、A*探索法を用いて最短経路を発見する装置である。【００２１】
システム構成変更手順生成装置１００は、隣接頂点取得手段１０１と、到着推定距離計算手段１０２と、最短距離頂点選択手段１０３と、検索中頂点表記憶手段１０４と、検索済頂点表記憶手段１０５と、経路樹情報記憶手段１０６と、最短経路取得手段１０７とを備える。【００２２】
隣接頂点取得手段１０１は、有向グラフ（状態グラフ）を入力とし、入力された頂点に隣接する次の頂点である隣接頂点を取得する機能を有する。隣接頂点は、状態グラフにおいて指定された頂点と辺で結ばれている頂点である。隣接頂点取得手段１０１は、取得された隣接頂点を到着推定距離計算手段１０２と最短距離頂点選択手段１０３に入力する。【００２３】
到着推定距離計算手段１０２は、隣接頂点取得手段１０１が出力した隣接頂点と、変更目的のシステム構成を表す終了頂点とを入力とし、隣接頂点から終了頂点までの状態グラフにおける距離である到着推定距離を算出する機能を有する。到着推定距離計算手段１０２は、例えば、状態グラフにおける重み付きホップ数を見積もることによって、到着推定距離を算出する。到着推定距離計算手段１０２は、算出された到着推定距離を最短距離頂点選択手段１０３に入力する。【００２４】
到着推定距離計算手段１０２は、終了頂点までの到着推定距離を算出する関数であると考えられるため、ヒューリスティック関数と呼ばれる。また、到着推定距離が常に終了頂点までの距離（到着距離）以下である場合、開始頂点から終了頂点までの経路が存在すれば、A*探索法で必ず最短経路が発見されることが知られている。常に終了頂点までの距離以下である到着推定距離は、Admissibleな到着推定距離と呼ばれている。【００２５】
最短距離頂点選択手段１０３は、隣接頂点取得手段１０１が出力した隣接頂点と、隣接頂点に関する到着推定距離計算手段１０２が出力した到着推定距離とを入力とし、隣接頂点の中から次の検索対象の頂点を選択する機能を有する。【００２６】
検索中頂点表記憶手段１０４は、状態グラフにおける頂点のうち検索中の頂点が登録される検索中頂点表を記憶する機能を有する。また、検索済頂点表記憶手段１０５は、状態グラフにおける頂点のうち検索済の頂点が登録される検索済頂点表を記憶する機能を有する。【００２７】
図１５は、検索中頂点表の例を示す説明図である。なお、検索済頂点表の形式も、図１５に示す例と同様の形式である。【００２８】
図１５に示す検索中頂点表には、検索中の頂点に関する到着推定距離および確定距離の計算結果が登録される。例えば、図１５は、頂点v2に関する到着推定距離が２、確定距離が７であることを示す。【００２９】
経路樹情報記憶手段１０６は、検索中の頂点および検索済の頂点で構成される経路の情報である経路樹情報を記憶する機能を有する。経路樹情報は、開始頂点が根である木データ構造で記憶される。すなわち、経路樹情報記憶手段１０６には、ツリー型のデータが格納される。【００３０】
最短距離頂点選択手段１０３は、検索中頂点表記憶手段１０４に記憶されている検索中頂点表、検索済頂点表記憶手段１０５に記憶されている検索済頂点表、および経路樹情報記憶手段１０６に記憶されている経路樹情報を参照しながら、次の検索対象の頂点を選択する。【００３１】
最短距離頂点選択手段１０３は、最初に検索中頂点表に登録されている頂点の隣接頂点を取り出す。次いで、最短距離頂点選択手段１０３は、取り出された隣接頂点の中で到着推定距離計算手段１０２が計算した終了頂点までの見込み距離である到着推定距離が最も短い頂点を、次の検索対象の頂点に選択する。【００３２】
上記のような最短距離頂点選択手段１０３による探索法は、最良優先探索法と呼ばれる。到着推定距離計算手段１０２が算出する見込み距離（到着推定距離）の精度が高ければ、最短距離頂点選択手段１０３は、次の検索対象の頂点を高速で探索できる。なお、次の検索対象の頂点を選択した後、最短距離頂点選択手段１０３は、検索中頂点表、検索済頂点表、および経路樹情報をそれぞれ更新する。【００３３】
最短経路取得手段１０７は、終了頂点が検索された後、経路樹情報記憶手段１０６に記憶されている経路樹情報に基づいて状態グラフにおける最短経路を取得する機能を有する。【００３４】
最短経路取得手段１０７が経路樹情報に基づいて状態グラフにおける最短経路を取得する例を図１６に示す。図１６は、経路樹情報記憶手段１０６に記憶されている経路樹情報の例を示す説明図である。【００３５】
図１６に示す経路樹において、開始頂点はv0、終了頂点はveである。また、図１６に示す経路樹は、「v0→v2→v5」、「v0→v1→v4」、「v0→v1→v3→ve」の３つの経路で構成されている。また、図１６に示す破線の矢印は、最短経路を表す。【００３６】
終了頂点であるveが検索された場合、最短経路取得手段１０７には、終了頂点であるveが入力される。図１６に示す例の場合、最短経路取得手段１０７は、最短経路として「v0→v1→v3→ve」を取得する。【００３７】
以下、一般的なシステム構成変更手順生成装置１００の動作を図１７を参照して説明する。図１７は、一般的なシステム構成変更手順生成装置１００による変更手順生成処理の全体動作を示すフローチャートである。【００３８】
最初に、最短距離頂点選択手段１０３は、システムの初期状態を表す開始頂点に関する到着推定距離を、到着推定距離計算手段１０２から得る（ステップS1000）。次いで、最短距離頂点選択手段１０３は、得られた到着推定距離と、開始頂点からの距離である確定距離０と共に、検索中頂点表に始点である開始頂点を登録する（ステップS1010）。すなわち、頂点検索ループに入る（ステップS1020）。【００３９】
次いで、最短距離頂点選択手段１０３は、検索中頂点表に登録されている頂点のうち、共に登録されている到着推定距離と確定距離の和が最短の頂点である最短距離頂点eを取り出す（ステップS1030）。次いで、最短距離頂点選択手段１０３は、取り出された最短距離頂点eが終了頂点の集合に含まれているか否かを確認する（ステップS1040）。【００４０】
最短距離頂点eが終了頂点の集合に含まれている場合（ステップS1040におけるYes）、システム構成変更手順生成装置１００は、頂点検索ループを抜け、ステップS1180に処理を進める。【００４１】
最短距離頂点eが終了頂点の集合に含まれていない場合（ステップS1040におけるNo）、最短距離頂点選択手段１０３は、取り出された最短距離頂点eを、検索中頂点表から削除し、検索済頂点表に登録する（ステップS1050）。【００４２】
次いで、最短距離頂点選択手段１０３は、隣接頂点取得手段１０１から、最短距離頂点eに関する隣接頂点の集合を得る（ステップS1060）。すなわち、隣接頂点処理ループに入る（ステップS1070）。【００４３】
最初に、最短距離頂点選択手段１０３は、得られた最短距離頂点eに関する隣接頂点の集合から、未処理の隣接頂点fを取り出す。取り出された隣接頂点fに関して、最短距離頂点選択手段１０３は、開始頂点から隣接頂点fまでの状態グラフにおける距離である仮の確定距離df’を求める。最短距離頂点選択手段１０３は、検索中頂点表から取り出された最短距離頂点eの確定距離deと、隣接頂点fと最短距離頂点eの間の距離d(e,f)の和であるDeをdf’にする（ステップS1080）。【００４４】
次いで、到着推定距離計算手段１０２は、隣接頂点fに関する仮の到着推定距離hf’を計算する（ステップS1090）。仮の到着推定距離hf’が計算された後、最短距離頂点選択手段１０３は、隣接頂点fが検索中頂点表に登録されているか否か、または検索済頂点表に登録されているか否かを確認する（ステップS1100）。【００４５】
隣接頂点fが検索中頂点表と検索済頂点表のいずれにも登録されていない場合（ステップS1110における条件［検索中頂点表にも検索済頂点表にも存在しない］）、隣接頂点fは、未検索の頂点である。隣接頂点fが未検索の頂点である場合、最短距離頂点選択手段１０３は、ステップS1120に処理を進める。【００４６】
隣接頂点fが検索中頂点表に登録されている場合（ステップS1110における条件［検索中頂点表に存在］）、最短距離頂点選択手段１０３は、ステップS1130に処理を進める。また、隣接頂点fが検索済頂点表に登録されている場合（ステップS1110における条件［検索済頂点表に存在］）、最短距離頂点選択手段１０３は、ステップS1140に処理を進める。
なお、本例において、同一の頂点が検索中頂点表および検索済頂点表に同時に登録されることはない。【００４７】
システム構成変更手順生成装置１００は、最短距離頂点eに関する隣接頂点の集合の中で処理されていない隣接頂点が存在する間、ステップS1080〜ステップS1140の処理を繰り返し実行する。ステップS1080〜ステップS1140の処理は、最短距離頂点eに関する隣接頂点ごとに、隣接頂点の数だけ繰り返し実行される。【００４８】
最短距離頂点eに関する全ての隣接頂点が処理されたとき、システム構成変更手順生成装置１００は、隣接頂点処理ループを抜ける（ステップS1150）。【００４９】
システム構成変更手順生成装置１００は、検索中頂点表に頂点が登録されている間、ステップS1030〜ステップS1150の処理を繰り返し実行する。ステップS1030〜ステップS1150の処理は、検索中頂点表に登録される頂点ごとに、登録される頂点の数だけ繰り返し実行される。【００５０】
なお、本例のステップS1030〜ステップS1150の繰り返し処理において、最短距離頂点eが終了頂点の集合に含まれているというステップS1040の条件が満たされない限り、すなわち変更目的のシステム構成を表す終了頂点が検索されない限りステップS1180に処理は進まない。【００５１】
検索中頂点表に頂点が登録されておらず、かつステップS1180に処理が進まなかった場合、最短経路取得手段１０７は、頂点検索ループを抜け、開始頂点と終了頂点を結ぶ経路が存在しないと判断する（ステップS1170）。判断した後、システム構成変更手順生成装置１００は、変更手順生成処理を終了する。【００５２】
最短距離頂点eが終了頂点の集合に含まれている場合（ステップS1040におけるYes）、現在のシステム構成を表す開始頂点から変更目的のシステム構成を表す終了頂点までの状態グラフにおける最短経路が存在する。最短経路取得手段１０７は、終了頂点の集合に含まれている最短距離頂点eを取り出す。【００５３】
次いで、最短経路取得手段１０７は、経路樹情報が示す経路樹を最短距離頂点eからさかのぼることによって、最短経路を取得する（ステップS1180）。取得した後、システム構成変更手順生成装置１００は、変更手順生成処理を終了する。【００５４】
以下、変更手順生成処理を構成する副処理を説明する。最初に、ステップS1120の検索中頂点表登録処理を説明する。図１８は、最短距離頂点選択手段１０３による検索中頂点表登録処理の動作を示すフローチャートである。【００５５】
最短距離頂点選択手段１０３は、隣接頂点f、ステップS1080で算出された隣接頂点fの仮の確定距離df’、およびステップS1090で算出された仮の到着推定距離hf’を、検索中頂点表に登録する（ステップS1121）。登録した後、最短距離頂点選択手段１０３は、ステップS1150に処理を進める。【００５６】
次に、ステップS1130の親頂点置き換え処理を説明する。図１９は、最短距離頂点選択手段１０３による親頂点置き換え処理の動作を示すフローチャートである。【００５７】
最短距離頂点選択手段１０３は、検索中頂点表に登録されている隣接頂点fの確定距離dfと到着推定距離hfの和Dfを求める。同様に、最短距離頂点選択手段１０３は、ステップS1080で算出された隣接頂点fの仮の確定距離df’とステップS1090で算出された仮の到着推定距離hf’の和Df’を求める。次いで、最短距離頂点選択手段１０３は、DfとDf’を比較する（ステップS1131）。【００５８】
隣接頂点fのDfがDf’よりも長い場合（ステップS1132におけるYes）、最短距離頂点選択手段１０３は、検索中頂点表に登録されている隣接頂点fの確定距離dfを仮の確定距離df’に、隣接頂点fの到着推定距離hfを仮の到着推定距離hf’にそれぞれ置き換える（ステップS1133）。置き換えた後、最短距離頂点選択手段１０３は、ステップS1150に処理を進める。【００５９】
隣接頂点fのDfがDf’以下の場合（ステップS1132におけるNo）、最短距離頂点選択手段１０３は、隣接頂点fの確定距離dfおよび到着推定距離hfが検索中頂点表に登録された状態のままにし、ステップS1150に処理を進める。【００６０】
次に、ステップS1140の検索済頂点表移し替え処理を説明する。図２０は、最短距離頂点選択手段１０３による検索済頂点表移し替え処理の動作を示すフローチャートである。【００６１】
最短距離頂点選択手段１０３は、検索済頂点表に登録されている隣接頂点fの確定距離dfと到着推定距離hfの和Dfを求める。同様に、最短距離頂点選択手段１０３は、ステップS1080で算出された隣接頂点fの仮の確定距離df’とステップS1090で算出された仮の到着推定距離hf’の和Df’を求める。次いで、最短距離頂点選択手段１０３は、DfとDf’を比較する（ステップS1141）。【００６２】
隣接頂点fのDfがDf’よりも長い場合（ステップS1142におけるYes）、最短距離頂点選択手段１０３は、検索済頂点表に登録されている隣接頂点fを、検索中頂点表に移し替える（ステップS1143）。隣接頂点fが検索中頂点表に移し替えられることによって、隣接頂点fに関する隣接頂点が検索される。【００６３】
次いで、最短距離頂点選択手段１０３は、検索中頂点表に登録されている隣接頂点fの確定距離dfを仮の確定距離df’に、隣接頂点fの到着推定距離hfを仮の到着推定距離hf’にそれぞれ置き換える（ステップS1144）。【００６４】
次いで、最短距離頂点選択手段１０３は、経路樹情報が示す隣接頂点fの親頂点を、最短距離頂点eに張り替える（ステップS1145）。張り替えた後、最短距離頂点選択手段１０３は、ステップS1150に処理を進める。【００６５】
隣接頂点fのDfがDf’以下の場合（ステップS1142におけるNo）、最短距離頂点選択手段１０３は、隣接頂点fの確定距離dfおよび到着推定距離hfが検索済頂点表に登録された状態のままにし、ステップS1150に処理を進める。【００６６】
上述した図１７〜図２０に示す各処理の動作は、非特許文献２に記載されているA*探索法に基づいた動作として知られている。
【先行技術文献】
【特許文献】
【００６７】
【特許文献１】特表２０１４−５０６４０９号公報
【００６８】
【特許文献２】特開平４−４７３５６号公報
【非特許文献】
【００６９】
【非特許文献１】「ダイクストラ法」、[online]、ウィキペディア、[２０１６年１月２９日検索]、インターネット<https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95>
【非特許文献２】「A*」、[online]、ウィキペディア、[２０１６年１月２９日検索]、インターネット<https://ja.wikipedia.org/wiki/A*>
【発明の概要】
【発明が解決しようとする課題】
【００７０】
A*探索法が用いられる変更手順生成処理には、ICTシステム構成の変更手順の生成に適切な到着推定距離の計算方法が自明でないという問題がある。一般的にA*探索法において、解く対象の問題に合わせて到着推定距離の計算方法が適切に定められると、探索効率が上がる。しかし、各問題に適切な到着推定距離の計算方法は自明でない。【００７１】
また、上記の例のように、ICTシステムの構成変更では、Webアプリケーションのバージョンの更新に他のモジュールのバージョンの更新が求められたり、モジュールのバージョンの更新に他のモジュールの状態の一時的な変更が求められたりする。【００７２】
すなわち、複雑な依存関係が考慮された上で、ICTシステム構成の変更手順は生成されることが求められる。ICTシステム構成の変更手順の生成の問題を解くA*探索法において、探索が効率的に行われるような適切な到着推定距離の計算方法は自明でない。【００７３】
また、ICTシステム構成の変更手順の生成の問題では最短経路の発見が最終目的であるため、適切な到着推定距離の計算方法は、Admissibleな計算方法であることが求められる。さらに、到着推定距離の計算に係る時間は、可能な限り短いことが好ましい。【００７４】
そこで、本発明は、システムを構成する属性間に依存関係が存在するシステムの変更手順を適切に生成できる変更手順生成システム、変更手順生成方法および変更手順生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００７５】
本発明による変更手順生成システムは、所定の状態のシステムを構成する属性の属性値の変更目的の状態のシステムを構成する属性の属性値への変更に要する属性ごとの手順数の総和に対して変更において他の属性の属性値が変更される所定値未満の属性の数を加算し所定値を減算することによって到着推定距離を計算する計算手段を備えることを特徴とする。【００７６】
本発明による変更手順生成方法は、所定の状態のシステムを構成する属性の属性値の変更目的の状態のシステムを構成する属性の属性値への変更に要する属性ごとの手順数の総和に対して変更において他の属性の属性値が変更される所定値未満の属性の数を加算し所定値を減算することによって到着推定距離を計算することを特徴とする。【００７７】
本発明による変更手順生成プログラムは、コンピュータに、所定の状態のシステムを構成する属性の属性値の変更目的の状態のシステムを構成する属性の属性値への変更に要する属性ごとの手順数の総和に対して変更において他の属性の属性値が変更される所定値未満の属性の数を加算し所定値を減算することによって到着推定距離を計算する計算処理を実行させることを特徴とする。
【発明の効果】
【００７８】
本発明によれば、システムを構成する属性間に依存関係が存在するシステムの変更手順を適切に生成できる。
【図面の簡単な説明】
【００７９】
【図１】本発明によるシステム構成変更手順生成システム１０の第１の実施形態の構成例を示すブロック図である。
【図２】本実施形態のシステム構成変更手順生成装置１００による変更手順生成処理の全体動作を示すフローチャートである。
【図３】到着推定距離計算手段１０９による到着推定距離計算処理の動作を示すフローチャートである。
【図４】図１２に示すWebシステムを構成するコンポーネント間に存在する依存関係を示す説明図である。
【図５】システムの構成変更の定義を表す有向グラフの例を示す説明図である。
【図６】図５に示す開始頂点と終了頂点を結ぶ最短経路の例を示す説明図である。
【図７】図６に示す最短経路の探索処理の例を示す説明図である。
【図８】図６に示す最短経路の探索処理の他の例を示す説明図である。
【図９】各方式に基づいて実行された最短経路の探索処理の評価結果を示す説明図である。
【図１０】本発明による変更手順生成システムの概要を示すブロック図である。
【図１１】一般的なシステム構成変更装置の構成例を示すブロック図である。
【図１２】Webシステムにおける依存関係の例を示す説明図である。
【図１３】システムの構成変更を表す有向グラフの例を示す説明図である。
【図１４】一般的なシステム構成変更手順生成装置１００の構成例を示すブロック図である。
【図１５】検索中頂点表の例を示す説明図である。
【図１６】経路樹情報記憶手段１０６に記憶されている経路樹情報の例を示す説明図である。
【図１７】一般的なシステム構成変更手順生成装置１００による変更手順生成処理の全体動作を示すフローチャートである。
【図１８】最短距離頂点選択手段１０３による検索中頂点表登録処理の動作を示すフローチャートである。
【図１９】最短距離頂点選択手段１０３による親頂点置き換え処理の動作を示すフローチャートである。
【図２０】最短距離頂点選択手段１０３による検索済頂点表移し替え処理の動作を示すフローチャートである。
【発明を実施するための形態】
【００８０】
実施形態１．
［構成の説明］
以下、本発明の実施形態を、図面を参照して説明する。図１は、本発明によるシステム構成変更手順生成システム１０の第１の実施形態の構成例を示すブロック図である。
【００８１】
図１に示すように、本実施形態のシステム構成変更手順生成システム１０は、システム構成変更手順生成装置１００と、表示手段２００とを含む。なお、システム構成変更手順生成システム１０は、表示手段２００を含まなくてもよい。また、システム構成変更手順生成装置１００は、単体で使用可能な装置である。
【００８２】
図１に示すシステム構成変更手順生成装置１００は、状態グラフ展開手段１０８と、到着推定距離計算手段１０９と、最短距離頂点選択手段１０３と、検索中頂点表記憶手段１０４と、検索済頂点表記憶手段１０５と、経路樹情報記憶手段１０６と、最短経路取得手段１０７とを含む。状態グラフ展開手段１０８および到着推定距離計算手段１０９以外の図１に示すシステム構成変更手順生成装置１００の構成は、図１４に示すシステム構成変更手順生成装置１００の構成と同様である。
【００８３】
状態グラフ展開手段１０８は、システム構成および構成変更に関する情報を示す状態モデルを入力とし、入力された頂点に隣接する次の頂点である隣接頂点を取得する機能を有する。
【００８４】
到着推定距離計算手段１０９は、状態グラフ展開手段１０８が出力した隣接頂点と、変更目的のシステム構成を表す終了頂点とを入力とし、隣接頂点から終了頂点までの状態グラフにおける距離である到着推定距離を算出する機能を有する。図１４に示す到着推定距離計算手段１０２と異なり、本実施形態の到着推定距離計算手段１０９の計算性能は、計算対象の状態グラフに依存する。
【００８５】
本実施形態において、到着推定距離計算手段１０９は、属性の値が変更される際に他の属性の値も変更される関係、すなわちコンポーネント（属性）間に存在する依存関係を表すペナルティpを、到着推定距離の計算に使用する。
【００８６】
例えば、図１２における（ｂ）に示すように、Webシステムの属性「Webサーバ」の状態が「起動」であると、Webシステムの属性「lib v1」の状態は「起動」から「非搭載」に変更されない。すなわち、属性「Webサーバ」と属性「lib v1」の間に依存関係が存在する。
【００８７】
また、属性「Webサーバ」の状態が既に「停止」であれば、属性「lib v1」の状態は「起動」から「非搭載」に変更される。すなわち、属性「Webサーバ」と属性「lib v1」の間に依存関係が存在しない。
【００８８】
ペナルティpは、非負の整数である。また、本実施形態のペナルティpの最大値をpmaxとする。すなわち、ペナルティpは、必ずpmax以下になる。
【００８９】
システム構成変更手順生成装置１００の各手段は、状態モデルが表すシステム構成と更新要求の内容を状態グラフにモデル化する。また、図１４に示すシステム構成変更手順生成装置１００と同様に、最短経路取得手段１０７が開始頂点と終了頂点を結ぶ最短経路を求めることによって、開始頂点が表す現在のシステム構成から終了頂点が表す変更目的のシステム構成への構成変更手順が生成される。構成変更手順が生成される際、到着推定距離計算手段１０９が適切にグラフ距離を見積もることによって、頂点が高速に探索される。
【００９０】
表示手段２００は、最短経路取得手段１０７により取得された、開始頂点と終了頂点を結ぶ最短経路を表示する機能を有する。表示手段２００は、例えば液晶ディスプレイ装置等の表示装置である。
【００９１】
［動作の説明］
以下、本実施形態のシステム構成変更手順生成装置１００の動作を図２を参照して説明する。図２は、本実施形態のシステム構成変更手順生成装置１００による変更手順生成処理の全体動作を示すフローチャートである。
【００９２】
ステップS2000〜ステップS2050の処理は、図１７に示すステップS1000〜ステップS1050の処理と同様である。
【００９３】
最短距離頂点選択手段１０３は、状態グラフ展開手段１０８から最短距離頂点eに関する隣接頂点の集合を得る（ステップS2060）。すなわち、隣接頂点処理ループに入る（ステップS2070）。
【００９４】
ステップS2080〜ステップS2180の処理は、図１７に示すステップS1080〜ステップS1180の処理と同様である。
【００９５】
以下、変更手順生成処理を構成する副処理のうち、本実施形態独自の処理であるステップS2090の到着推定距離計算処理を説明する。図３は、到着推定距離計算手段１０９による到着推定距離計算処理の動作を示すフローチャートである。
【００９６】
最初に、到着推定距離計算手段１０９は、隣接頂点fに関する仮の到着推定距離hf’とペナルティpを、それぞれ０に初期化する。また、到着推定距離計算手段１０９は、pmaxを自然数の定数に初期化する（ステップS2091）。すなわち、属性変更ループに入る（ステップS2092）。
【００９７】
図１３に示すように、所定の状態のシステム構成を表す隣接頂点fは、複数の属性を含む。到着推定距離計算手段１０９は、隣接頂点fに含まれる属性から未処理の属性aを取り出す。次いで、到着推定距離計算手段１０９は、隣接頂点fの取り出された属性aの属性値vの、変更目的のシステム構成を表す頂点gに含まれる属性aの属性値v’への変更に要する操作数dを算出する（ステップS2093）。
【００９８】
次いで、到着推定距離計算手段１０９は、算出された操作数dを仮の到着推定距離hf’に加算する（ステップS2094）。ステップS2094では、構成が変更される対象のシステムを構成するコンポーネント（すなわち、属性）間に存在する依存関係は考慮されない。
【００９９】
次いで、到着推定距離計算手段１０９は、ステップS2093で算出された操作数dに関する属性値の変更において、属性間に依存関係が存在するか否かを確認する（ステップS2095）。
【０１００】
属性間に依存関係が存在する場合（ステップS2095におけるYes）、到着推定距離計算手段１０９は、ペナルティpに１を加算する（ステップS2096）。加算した後、到着推定距離計算手段１０９は、ステップS2097に処理を進める。
【０１０１】
属性間に依存関係が存在しない場合（ステップS2095におけるNo）、到着推定距離計算手段１０９は、ペナルティpを更新せずに、ステップS2097に処理を進める。
【０１０２】
到着推定距離計算手段１０９は、隣接頂点fに含まれる属性の中で処理されていない属性が存在する間、ステップS2093〜ステップS2096の処理を繰り返し実行する。ステップS2093〜ステップS2096の処理は、隣接頂点fに含まれる属性ごとに、含まれている属性の数だけ繰り返し実行される。隣接頂点fに含まれる全ての属性が処理されたとき、到着推定距離計算手段１０９は、属性変更ループを抜ける（ステップS2097）。
【０１０３】
属性変更ループを抜けた後、到着推定距離計算手段１０９は、以下の式（１）に示すように仮の到着推定距離hf’にペナルティpを反映する（ステップS2098）。
【０１０４】
hf’ ← hf’ + min(p, pmax) − pmax  ・・・式（１）
【０１０５】
なお、式（１）におけるmin(p, pmax)は、pとpmaxのうち、小さい方の値を返す関数である。式（１）に従ってhf’を計算した後、到着推定距離計算手段１０９は、以下の式（２）に示すように仮の到着推定距離hf’の戻り値を決定する（ステップS2099）。
【０１０６】
hf’ ← max(0, hf’)  ・・・式（２）
【０１０７】
なお、式（２）におけるmax(0, hf’)は、０とhf’のうち、大きい方の値を返す関数である。すなわち、算出されたhf’が負であれば０が、副処理で求められた仮の到着推定距離の戻り値になる。また、算出されたhf’が正であればhf’が、副処理で求められた仮の到着推定距離の戻り値になる。仮の到着推定距離の戻り値を決定した後、到着推定距離計算手段１０９は、到着推定距離計算処理を終了する。
【０１０８】
なお、到着推定距離は、Admissibleな到着推定距離であることが求められる。すなわち、終了頂点に到着するまでの距離は、到着推定距離以上であることが求められる。上記の到着推定距離計算手段１０９による到着推定距離計算処理で求められる到着推定距離はAdmissibleな到着推定距離になることを以下に示す。
【０１０９】
終了頂点に到着するまでの距離は、少なくともコンポーネント（属性）間に存在する依存関係が全く考慮されずに求められた変更手順の数以上の距離になる。
【０１１０】
また、式（１）に示すように、到着推定距離計算手段１０９は、hf’ + min(p, pmax) − pmaxを計算することによって到着推定距離を求める。式（１）の右辺第１項のhf’は、コンポーネント（属性）間に存在する依存関係が全く考慮されずに求められた変更手順の数に相当する。また、(min(p, pmax) − pmax)は、常に０以下になる。よって、本実施形態において以下の不等式（３）が成立する。
【０１１１】
hf’ + min(p, pmax) − pmax ≦ hf’ ≦ （終了頂点に到着するまでの距離）  ・・・式（３）
【０１１２】
式（３）に示す通り、本実施形態で求められる到着推定距離は、終了頂点に到着するまでの距離以下になるため、Admissibleな到着推定距離である。
【０１１３】
［効果の説明］
本実施形態の到着推定距離計算手段１０９は、システムを構成するコンポーネント（属性）間に存在する依存関係が考慮された到着推定距離を求める。よって、本実施形態のシステム構成変更手順生成装置１００は、一般的なシステム構成変更手順生成装置１００に比べてシステム構成の変更手順を高速で生成できる。
【０１１４】
その理由は、到着推定距離計算手段１０９が依存関係が反映された到着推定距離を計算することによって、より到着距離に近い到着推定距離が計算される。より到着距離に近い到着推定距離が計算されることによって複数の経路における到着推定距離に差が生じるので、最短距離頂点選択手段１０３が選択する最短距離頂点がより絞られるためである。
【０１１５】
また、本実施形態のシステム構成変更手順生成装置１００は、A*探索法を用いて効率的に変更手順生成処理を実行できる。その理由は、効率的に変更手順生成処理が実行されるためには、到着推定距離計算手段１０９が効率的に到着推定距離を計算することが求められる。
【０１１６】
本実施形態の到着推定距離計算手段１０９は、頂点に含まれる属性ごとに独立して到着推定距離を計算でき、属性間に依存関係が存在する時にのみ他の属性を参照する。よって、到着推定距離計算手段１０９は、複数の属性を跨ぐ複雑な探索や計算をせずに済み、効率的に到着推定距離を計算できるからである。
[具体例]
【０１１７】
以下、本発明の実施形態の具体例を、図面を参照して説明する。本具体例では、図１２における（ａ）に示すWebシステムを構成するWebサーバにおいて稼働するアプリケーションAPのバージョンがv1からv2に更新される場合、すなわちAP v1がAP v2に置換される場合を考える。なお、上記の通りAP v2の稼働にはライブラリlib v2が求められる。
【０１１８】
図４は、図１２における（ａ）に示すWebシステムを構成するコンポーネント間に存在する依存関係を示す説明図である。図４に、「AP v1：停止 → 起動 depends WebServer.起動 & lib v1.起動」と記載されている。すなわち、AP v1の起動には、ライブラリであるlib v1が起動状態であることが求められる。
【０１１９】
同様に、「AP v2：停止 → 起動 depends WebServer.起動 & lib v2.起動」と記載されている。すなわち、AP v2の起動には、ライブラリであるlib v2が起動状態であることが求められる。また、AP v1の状態およびAP v2の状態の遷移には、Webサーバが起動状態であることが求められる。AP v1の状態およびAP v2の状態は、「停止」、「起動」、「非搭載」の各状態を取り得る。
【０１２０】
また、図４に、「lib v1|lib v2：起動 → 停止 depends WebServer.停止」と記載されている。すなわち、lib v1およびlib v2の停止には、Webサーバが停止状態であることが求められる。
【０１２１】
本具体例のシステム構成変更に関して、変更前のシステム構成を表す状態グラフの開始頂点と、変更後のシステム構成を表す状態グラフの終了頂点を図５に示す。図５は、システムの構成変更の定義を表す有向グラフの例を示す説明図である。
【０１２２】
図５に示すように、開始頂点におけるAP v1の状態「起動」は、終了頂点において「非搭載」に変更されている。また、開始頂点におけるAP v2の状態「非搭載」は、終了頂点において「起動」に変更されている。
【０１２３】
また、図５に示すように、開始頂点におけるlib v1の状態「起動」は、終了頂点において「非搭載」に変更されている。また、開始頂点におけるlib v2の状態「非搭載」は、終了頂点において「起動」に変更されている。
【０１２４】
本具体例の変更手順生成処理において、システム構成変更手順生成装置１００は、図５に示す開始頂点と終了頂点を結ぶ最短経路を計算する。図６は、図５に示す開始頂点と終了頂点を結ぶ最短経路の例を示す説明図である。本具体例において、システム構成変更手順生成装置１００は、図６に示すような最短経路を算出する。
【０１２５】
図６に示す各頂点において、下線が付された状態は、前の頂点における状態から変更された状態を表す。例えば、開始頂点におけるWebサーバの状態「起動」は、２つ目の頂点において「停止」に変更されている。
【０１２６】
図６に示すように、図５に示す開始頂点と終了頂点を結ぶ最短経路は、１１個の頂点で構成される経路である。図６に示す最短経路の算出処理において到着推定距離に、マンハッタン距離が使用された場合と、本実施形態の到着推定距離計算手段１０９が計算した距離が使用された場合との違いを以下に説明する。
【０１２７】
図７は、図６に示す最短経路の探索処理の例を示す説明図である。図７に示す例は、到着推定距離にマンハッタン距離が使用されるA*探索法が実行された場合の最短経路の探索処理の例である。
【０１２８】
到着推定距離にマンハッタン距離が使用される場合、到着推定距離は、頂点の属性の属性値の、終了頂点の属性の属性値への変更に要する属性ごとの操作数の総和になる。すなわち、図７に示す例における到着推定距離は、pmax=0の条件下で到着推定距離計算手段１０９が計算した距離と同等である。
【０１２９】
図７に示す各頂点には属性および属性の状態が含まれる。各頂点の属性である「A1」、「A2」、「w」、「L1」、「L2」は、それぞれAP v1、AP v2、Webサーバ、lib v1、lib v2を表す。また、属性の各状態である「t」、「f」、「u」は、それぞれ「起動」、「非搭載」、「停止」を表す。
【０１３０】
また、図７に示す各頂点において、下線が付された状態は、前の頂点における状態から変更された状態を表す。例えば、開始頂点における属性「A1」の状態「t」は、２つ目の頂点において「u」に変更されている。
【０１３１】
また、図７に示す各頂点の近傍に記載されているdは、算出された終了頂点までの距離を表す。距離のうち、矩形で囲まれた値は確定距離を表す。また、他の値は到着推定距離を表す。上述したように、図７に示す例における到着推定距離は、マンハッタン距離である。
【０１３２】
また、図７における斜線で示された頂点は、アルゴリズム上検索された頂点を表す。図１７に示すフローチャートに沿って、図１４に示す一般的なシステム構成変更手順生成装置１００は、最短距離頂点が終了頂点に含まれるまで頂点を検索する。図７に示す例では、１８個の頂点が全て検索されている。
【０１３３】
図８は、図６に示す最短経路の探索処理の他の例を示す説明図である。図８に示す例は、到着推定距離に本実施形態の到着推定距離計算手段１０９が計算した距離が使用されるA*探索法が実行された場合の最短経路の探索処理の例である。また、図８は、pmax=2の条件下で実行された最短経路の探索処理の例を示す。
【０１３４】
図８に示す各頂点の近傍に記載されているdは、算出された終了頂点までの距離を表す。距離のうち、矩形で囲まれた値は確定距離を表す。また、他の値は到着推定距離を表す。到着推定距離のうち下線が付された値は、ペナルティ部分、すなわち式（１）におけるmin(p, pmax) − pmaxの値を表す。また、到着推定距離の他の値は、属性ごとの距離を表す。
【０１３５】
図８に示すように、開始頂点のdの到着推定距離には、式「2+2+0+2+2」が含まれる。式「2+2+0+2+2」は、「A1」、「A2」、「w」、「L1」、「L2」の各属性の操作数の和で表された距離である。例えば、開始頂点の「A1」の状態は「t」であり、終了頂点の「A1」の状態は「f」である。よって、開始頂点の「A1」の距離は、状態「t」から状態「f」への変更に要する操作数の２になる。
【０１３６】
すなわち、式「2+2+0+2+2」は、上記のように計算された５つの属性の各距離が足し合わされた式である。なお、図７には、式「2+2+0+2+2」の計算結果である「8」が記載されている。
【０１３７】
d以外の図８における表記の意味は、図７における表記の意味と同じである。図２に示すフローチャートに沿って、図１に示す本実施形態のシステム構成変更手順生成装置１００は、最短距離頂点が終了頂点に含まれるまで頂点を検索する。本具体例では、アルゴリズム上最も距離dが小さい頂点から検索される。
【０１３８】
図８には、白色の頂点が示されている。白色の頂点は、アルゴリズム上検索されなかった頂点を表す。白色の頂点が検索されなかった理由は、検索された頂点のすべてよりも距離dが大きいためである。例えば、図８に示す頂点Aは、距離dが１０である。
【０１３９】
検索された頂点の中で距離dが１０以上である頂点は終了頂点のみであるため、距離dが１０である頂点Aは、他の頂点の距離dが１０より大きくならない限り検索されない。頂点Aが検索されなかったため、同じ経路を構成する他の頂点も全て検索されていない。また、頂点Aと同様の理由で、頂点Bも検索されていない。
【０１４０】
図８に示す例では、開始頂点と終了頂点を含めて１１個の頂点が検索される。すなわち、図８に示す例では、最後まで検索されなかった頂点（白色の頂点）が存在するため、図７に示す例に比べて探索処理が高速に実行される。従って、本実施形態のシステム構成変更手順生成装置１００の方が、一般的なシステム構成変更手順生成装置１００よりも効率的に最短経路を求めることができる。
【０１４１】
図９は、各方式に基づいて実行された最短経路の探索処理の評価結果を示す説明図である。事例１は、検索対象の頂点が多い例である。また、事例２は、検索対象の頂点が少ない例である。また、最短経路長に記載されている数字は、リンク数を表す。リンク数は、（（最短経路を構成する頂点の数）−１）である。
【０１４２】
図９には、事例１および事例２に対して、マンハッタン距離、到着推定距離計算手段１０９が計算した距離、ダイクストラ法が使用された場合に検索されたそれぞれの頂点の数が示されている。到着推定距離計算手段１０９が計算した距離が使用された場合に関して、pmax=1、pmax=2、pmax=3の各条件下で計算された場合がそれぞれ示されている。
【０１４３】
図９には、事例１と事例２共に、pmax=2の条件下で到着推定距離計算手段１０９が計算した距離が使用された場合が最も検索された頂点の数が少なかったという評価結果が示されている。よって、pmax=2に設定された時の本実施形態のシステム構成変更手順生成装置１００が、最も高速で最短経路を探索できる。
【０１４４】
本実施形態のシステム構成変更手順生成システムは、ICTシステムの構成変更手順を生成するために使用される、適切な到着推定距離を効率的に計算する到着推定距離計算手段を有する。到着推定距離計算手段は、ICTシステムの構成変更を表す有向グラフである状態グラフにおける、ICTシステムを構成するモジュール間に存在する依存関係が反映された到着推定距離を計算する。
【０１４５】
本実施形態のシステム構成変更手順生成システムは、現在のシステム構成と変更目的のシステム構成が与えられると、到着推定距離にマンハッタン距離が使用される場合に比べて構成変更手順をより高速に生成できる。
【０１４６】
その理由は、到着推定距離計算手段がICTシステムを構成するモジュール間に存在する依存関係が反映された到着推定距離を計算することによって、より到着距離に近い到着推定距離が計算される。より到着距離に近い到着推定距離が計算されることによって複数の経路における到着推定距離に差が生じるので、システム構成変更手順生成システムが、A*探索法を用いてより高速に最短経路を発見できるためである。
【０１４７】
なお、本実施形態のシステム構成変更手順生成装置１００は、例えば、記憶媒体に格納されているプログラムに従って処理を実行するCPU(Central Processing Unit)によって実現される。すなわち最短距離頂点選択手段１０３、最短経路取得手段１０７、状態グラフ展開手段１０８、および到着推定距離計算手段１０９は、例えば、プログラム制御に従って処理を実行するCPUによって実現される。
【０１４８】
また、検索中頂点表記憶手段１０４、検索済頂点表記憶手段１０５、および経路樹情報記憶手段１０６は、例えばRAM(Random Access Memory)で実現される。
【０１４９】
また、本実施形態のシステム構成変更手順生成装置１００における各部は、ハードウェア回路によって実現されてもよい。
【０１５０】
次に、本実施形態の概要を説明する。図１０は、本実施形態による変更手順生成システムの概要を示すブロック図である。本実施形態による変更手順生成システム２０は、所定の状態のシステムを構成する属性の属性値の変更目的の状態のシステムを構成する属性の属性値への変更に要する属性ごとの手順数の総和に対して変更において他の属性の属性値が変更される所定値未満の属性の数を加算し所定値を減算することによって到着推定距離を計算する計算手段２１（例えば、到着推定距離計算手段１０９）を備える。
【０１５１】
そのような構成により、変更手順生成システムは、システムを構成する属性間に依存関係が存在するシステムの変更手順を適切に生成できる。
【０１５２】
また、計算手段２１は、所定の状態のシステムを表す隣接頂点と変更目的の状態のシステムを表す終了頂点とを入力とし、属性ごとの手順数の総和に相当する隣接頂点から終了頂点までのマンハッタン距離を用いて隣接頂点に関する到着推定距離を計算してもよい。
【０１５３】
そのような構成により、変更手順生成システムは、変更対象のシステムの状態を表す状態グラフを入力としてシステムの変更手順を生成できる。
【０１５４】
また、変更手順生成システム２０は、最短距離頂点を選択する選択手段（例えば、最短距離頂点選択手段１０３）を備え、計算手段２１は、初期状態のシステムを表す開始頂点から隣接頂点までの確定距離を計算し、選択手段は、隣接頂点と隣接頂点に関する確定距離および到着推定距離とを入力とし、入力された隣接頂点の中で確定距離と到着推定距離の和が最短の隣接頂点を最短距離頂点に選択してもよい。
【０１５５】
そのような構成により、変更手順生成システムは、システムを構成する属性間に存在する依存関係が考慮された上で計算された到着推定距離に基づいて、最短距離頂点を選択できる。
【０１５６】
また、変更手順生成システム２０は、選択手段により選択された複数の最短距離頂点で構成された経路を最短経路として取得する取得手段（例えば、最短経路取得手段１０７）を備えてもよい。
【０１５７】
そのような構成により、変更手順生成システムは、システムを構成する属性間に存在する依存関係が考慮された上で計算された到着推定距離に基づいて、最短のシステムの変更手順を取得できる。
【０１５８】
また、変更手順生成システム２０は、取得手段により取得された最短経路を表示する表示手段（例えば、表示手段２００）を備えてもよい。
【０１５９】
そのような構成により、変更手順生成システムは、取得されたシステムの変更手順を利用者に分かりやすく提示できる。
【０１６０】
また、所定値は、２でもよい。
【０１６１】
そのような構成により、変更手順生成システムは、より高速でシステムの変更手順を生成できる。
【産業上の利用可能性】
【０１６２】
本発明は、依存関係を有するコンポーネントで構成されたシステムの構成変更手順を求める用途に好適に適用可能である。また、本発明は、依存関係を有する操作で構成されたプロセスの手順を生成する用途にも好適に適用可能である。【０１６３】
この出願は、２０１６年２月８日に出願された日本出願特願２０１６−０２１６０４を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１６４】
１０  システム構成変更手順生成システム
２０  変更手順生成システム
２１  計算手段
１００  システム構成変更手順生成装置
１０１  隣接頂点取得手段
１０２、１０９  到着推定距離計算手段
１０３  最短距離頂点選択手段
１０４  検索中頂点表記憶手段
１０５  検索済頂点表記憶手段
１０６  経路樹情報記憶手段
１０７  最短経路取得手段
１０８  状態グラフ展開手段
２００  表示手段
【図１】
2017138506.tif 000003
【図２】
2017138506.tif 000004
【図３】
2017138506.tif 000005
【図４】
2017138506.tif 000006
【図５】
2017138506.tif 000007
【図６】
2017138506.tif 000008
【図７】
2017138506.tif 000009
【図８】
2017138506.tif 000010
【図９】
2017138506.tif 000011
【図１０】
2017138506.tif 000012
【図１１】
2017138506.tif 000013
【図１２】
2017138506.tif 000014
【図１３】
2017138506.tif 000015
【図１４】
2017138506.tif 000016
【図１５】
2017138506.tif 000017
【図１６】
2017138506.tif 000018
【図１７】
2017138506.tif 000019
【図１８】
2017138506.tif 000020
【図１９】
2017138506.tif 000021
【図２０】
2017138506.tif 000022
【手続補正書】
【提出日】平成30年7月24日(2018.7.24)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９
【補正方法】変更
【補正の内容】
【請求項９】
コンピュータに、
所定の状態のシステムを構成する属性の属性値の変更目的の状態の前記システムを構成する前記属性の属性値への変更に要する属性ごとの手順数の総和に対して前記変更において他の属性の属性値が変更される所定値未満の属性の数を加算し前記所定値を減算することによって到着推定距離を計算する計算処理
を実行させるプログラム。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
コンピュータに、
所定の状態のシステムを表す隣接頂点と変更目的の状態の前記システムを表す終了頂点とを入力とし、属性ごとの手順数の総和に相当する前記隣接頂点から前記終了頂点までのマンハッタン距離を用いて前記隣接頂点に関する到着推定距離を計算する計算処理を実行させる
請求項９記載のプログラム。
【国際調査報告】
2017138506.tif 000023
2017138506.tif 000024
2017138506.tif 000025
2017138506.tif 000026