トレースバックアプローチ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/06/22 05:55 UTC 版)
「最長共通部分列問題」の記事における「トレースバックアプローチ」の解説
最長共通部分列のテーブルにおいて、最長共通部分列の行の計算に唯一要求されるのは、現在の行と次の行である。なお、長い配列の場合、それらの配列はおびただしく長くなるので、たくさんの記憶領域が要求される。記憶領域を節約するには、実際の部分列を保存しない事である。しかし、部分列の長さと方向矢印は保存する必要がある。それは、以下のテーブルのようにである。 Storing length, rather than sequences012345ØAGCAT0Ø0 0 0 0 0 0 1G0 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 0 ↖ {\displaystyle {\overset {\nwarrow }{\ }}} 1 ← {\displaystyle {\overset {\ }{\leftarrow }}} 1 ← {\displaystyle {\overset {\ }{\leftarrow }}} 1 ← {\displaystyle {\overset {\ }{\leftarrow }}} 1 2A0 ↖ {\displaystyle {\overset {\nwarrow }{\ }}} 1 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1 ↖ {\displaystyle {\overset {\nwarrow }{\ }}} 2 ← {\displaystyle {\overset {\ }{\leftarrow }}} 2 3C0 ↑ {\displaystyle {\overset {\ \uparrow }{\ }}} 1 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1 ↖ {\displaystyle {\overset {\nwarrow }{\ }}} 2 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 2 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 2 実際の部分列は、”トレースバック”手順で推測する。それは続く逆向き矢印であり、テーブルの最後のセルから開始する。トレースバックでは長さは減少する。配列に必須なのは共通の要素である。いくつかの経路が可能であり、その場合、セルに二つの矢印がある。以下は、その解析のためのテーブルである。セルの色の付いた数字は減少についての長さである。太字の数字はトレースした配列 (GA) である。 Traceback example012345ØAGCAT0Ø0 0 0 0 0 0 1G0 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 0 ↖ {\displaystyle {\overset {\nwarrow }{\ }}} 1 ← {\displaystyle {\overset {\ }{\leftarrow }}} 1 ← {\displaystyle {\overset {\ }{\leftarrow }}} 1 ← {\displaystyle {\overset {\ }{\leftarrow }}} 1 2A0 ↖ {\displaystyle {\overset {\nwarrow }{\ }}} 1 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1 ↖ {\displaystyle {\overset {\nwarrow }{\ }}} 2 ← {\displaystyle {\overset {\ }{\leftarrow }}} 2 3C0 ↑ {\displaystyle {\overset {\ \uparrow }{\ }}} 1 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 1 ↖ {\displaystyle {\overset {\nwarrow }{\ }}} 2 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 2 ← ↑ {\displaystyle {\overset {\ \ \uparrow }{\leftarrow }}} 2
※この「トレースバックアプローチ」の解説は、「最長共通部分列問題」の解説の一部です。
「トレースバックアプローチ」を含む「最長共通部分列問題」の記事については、「最長共通部分列問題」の概要を参照ください。
- トレースバックアプローチのページへのリンク
