出願番号 |
特願2008-196952 |
出願日 |
2008/7/30 |
出願人 |
日本放送協会 |
公開番号 |
特開2010-033461 |
公開日 |
2010/2/12 |
登録番号 |
特許第5174574号 |
特許権者 |
日本放送協会 |
発明の名称 |
グラフにおけるノード通過回数決定装置およびそのプログラム |
技術分野 |
情報・通信 |
機能 |
機械・部品の製造、制御・ソフトウェア |
適用製品 |
ノード通過回数決定装置およびそのプログラム |
目的 |
グラフにおけるノードの通過回数を決定する処理の処理時間を低減することのできる技術を提供する。 |
効果 |
各ノードでの通過回数を確定していくことができ、シンプレックス法のように条件式を記述する必要がなく、有向グラフにおけるノードの通過回数を解として安定に求め、かつ、通過回数を決定する処理の処理時間を低減することができる。
ルートノードの通過回数を最小にするように各ノードの通過回数を暫定的に決定することができる。したがって、ノード通過回数を決定するための処理時間を確実に低減できる。 |
技術概要
|
ノード通過回数決定装置10は、有向グラフと各ノードに与えられた最小通過回数とを受け付ける入力部30と、有向グラフの分岐の開始を判定する分岐開始判定部51と、有向グラフの分岐のマージを判定する分岐マージ判定部52と、有向グラフの分岐状態と最小通過回数とに基づいてルートノードの通過回数を最小にするように各ノードの通過回数を始点から終点に向けて逐次的に暫定値として決定し、ルートノードの通過回数を確定するルートノード通過回数決定部53と、分岐前後の差分値を共用通過回数として記憶部40に保持して管理する共用通過回数管理部55と、有向グラフの分岐状態と通過回数の暫定値とルートノードの通過回数とに基づいて各ノードの通過回数を終点から始点に向けて逐次的に確定するトレースバック部56とを備える。 |
実施実績 |
【無】 |
許諾実績 |
【無】 |
特許権譲渡 |
【否】
|
特許権実施許諾 |
【可】
|