問題タブ [clrs]

Floyd Warshall アルゴリズムについて読んで検索しましたが、理解できたと思います。しかし、本「アルゴリズムの紹介（トーマス・H・コーメンの本）」で読んだ例では、ある時点で積み重ねました。私は混乱しました。これは本と同じ図です。私の質問は最後のステップ、つまり π(5) にあります。例を次に示します: http://integrator-crimea.com/images/fig653_01_0.jpg

上記の私の混乱を解決できる人はいますか？それは本に間違って書かれていますか？

次の動的集合操作の漸近的な最悪の場合の実行時間は?

ソートされていない一重および二重にリンクされたリストの場合、Successor(L,x)

ソートされていない二重連結リストの Predecessor(L,x)

L: リスト、x: エントリへのポインタ

（実際には、これは本の質問10-1の一部です：「アルゴリズム入門、第3版」、私は答えを探しました、答えはO（n）ですが、私はそれについての説明を見つけることができませんでした）

ここに完全な質問があります：

有向グラフ G = (V,E) があると仮定し、次のプロパティを持つグラフ G' = (V,E') を見つけたいとします。

1. G' は G と同じ連結要素を持つ
2. G' は G と同じ成分グラフを持つ
3. E' は最小化されます。つまり、E' は可能な限り小さくなります。

これが私が得たものです：

まず、強連結成分アルゴリズムを実行します。これで、強連結成分ができました。次に、各強力な接続コンポーネントに移動し、その SCC 内で単純なサイクルを作成します。つまり、繰り返される唯一のノードが開始/終了ノードであるサイクルです。これにより、各 SCC内のエッジが最小限に抑えられます。

ここで、SCC間のエッジを最小化する必要があります。ああ、これを行う方法が思い浮かびません。

私の 2 つの質問は次のとおりです。(1) SCC間のエッジの最小化に関する部分の前のアルゴリズムは正しく聞こえますか? (2) SCC 間のエッジを最小化するにはどうすればよいですか。

(2) については、これは DAG のエッジの数を最小限に抑えることと同等であることがわかっています。(SCC を頂点と考えてください)。しかし、これは私を助けないようです。

指定: 整数値の配列 K,M

質問: 与えられた配列のすべての K 個の要素サブセットから、合計が値 M 未満になるように取得できる最大合計を見つけますか?

この問題に利用できる非動的プログラミング ソリューションはありますか? または、dp[i][j][k] のみの場合は、このタイプの問題しか解決できません! アルゴリズムを教えてください。

これは、CLRS の数論の章からのものです。

a/b結果qとリマインダ付きのバイナリ「紙と鉛筆」の長除算がビットの操作を行うrことを証明するように求められます。O((1+lgq)lgb)

私の見方ではb、 の各ビットに対して を 1 減算しqます。bしたがって、減算がlgb演算 ( の各ビットに対して 1 つ) を行うと仮定すると、演算bの合計が得O(lgblgq)られますが、これは要求されたものではありません。

最初に行う減算操作の結果が 0 ビットになる可能性があることを考慮すると (たとえば、100b を 11b で割る)、1 をlgq加算してこの減算を補正できます。しかし...減算自体についても同じことが言えます-数値に応じて操作lgbを行うことも、操作を行うこともできます（100bと11bの例では、2番目の減算は100b-11bになり、完了するまでに3回の操作が必要です） lg(b)+1.

したがって、これらのケースを因数分解すると、操作の数は になりますO((1+lgb)(1+lgq))。

問題は、部門がO((1+lgq)lgb)操作を行うことをどのように示すことができるかということです。