シーケンスが特定の順序に従うというテキストがいくつかあります。通過したトレイルの結果、一部のテキストが変更されます。私の目標は、ページごとに静的ページを生成し、リンクを介してそれらを相互接続することです。
問題は、印刷された本のテキストを生成するツールの問題を解決することです (これは明らかに静的です)。例 1 (下の画像) に示されている本を読んでいるとします。最初はノード A にいて、このページのテキストは「ページ B またはページ C に移動」です。ノード C を選択し、続いて F -> B -> E -> H を選択すると、A -> B -> D によってトラバースされた場合とは異なるノード H のコンテンツが表示されます。 →例えばH。これは印刷された本であるため、通過したパスに応じて一部のノードの内容を変更できるように、いくつかのパスを複製する必要があります。
例：
この例では、トラバースに 2 つの可能性があります。
A -> B -> D
A -> C -> D
期待される結果：
Page 1: A (link to page 2 and 3)
Page 2: B (link to page 4)
Page 3: C (link to page 5)
Page 4: D
Page 5: DD'
この単純な例では、読み取りがページ 3 を通過する場合にのみ表示されるテキストの一部がページ 4 に含まれると、5 ページが生成されます。
この問題をモデル化するために、グラフ理論を使用することにしました。理解を深めるために、以下のグラフに、解決しようとしている問題の 2 つの例を示しました。
赤い破線のエッジは、実際にはエッジではないことに注意してください。これらは、ノード Y にアクセスした結果、特定のノード X のコンテンツが変化したときに表現するために使用した方法です (「X に到達するパスが Y を通過すると、ノード X のコンテンツが変化する」と読みます)。
グラフ、トラバース戦略 (BFS と DFS)、およびその他のトピックについてよく読んでいます。私の目標は、前述のページを生成できるように特定のグラフを再配置するアルゴリズムを開発することです。この問題を解決するよく知られた問題は見つかりませんでしたが、既に存在しているはずです。私の研究では何も役に立たなかったので、自分で解決しようとしました。
私の成功したアプローチは、グラフを上に移動して、他のノードに依存するコンテンツを含むノードを見つけることでした。このノードが見つかると、依存ノードから現在のノードまでのすべてのパスが検索されます。これらのパスをトラバースして、複数の着信エッジを含むすべてのノードを複製し、以前の接続を削除して現在のノードを複製されたノードに接続し、パスのすべてのノードを消費するまで同様に繰り返します。このアルゴリズムはうまく機能しますが、このアプローチは効率的ではなく、長いテキストでは非常に遅くなる可能性があります。
私の質問は、この問題を解決するための他のより良い方法を知っていますか? この種の問題を解決できる理論や既知のアルゴリズムはありますか?
前もって感謝します。