問題タブ [graph-algorithm]

私の質問は、正の整数をRGB値に変換するアルゴリズムに関連していますが、実際には同じ質問ではありません。その人は主にデータの正規化の問題を抱えており、実際にはもっと美的な色の選択の問題があります。

-1.0から+1.0までの数字がたくさんあります。テキストをオーバーレイしたヒートマップを作成する必要があります。

PHPを使用して、各数値をHTMLカラー（#rrggbb）に変換する最も簡単な方法は、結果の色が直観的に温度に関連するだけでなく（つまり、最も寒い場合は最も青く、最も暑い場合は最も赤く、滑らかな色になります）間の遷移）だけでなく、黒色のテキストの背景色としても適していますか？

私は立ち往生している問題があり、どこから始めても見つからないので、どうしようもなくスタックオーバーフローに目を向けています。

この問題は、それが np-hard か多項式かを調べ、np-hard が np-completeness を証明する場合、そうでない場合はアルゴリズムを提供することを求めています。

問題は次のとおりです。

n 個のモジュールからなる製品が存在します。各モジュールを構築できる会社が 2 つありますが、費用はかかります (c_ij、i: モジュール番号、j: 会社番号)。モジュール a と b が別の会社によって構築されている場合は、追加コスト (p_ab) もかかります。モジュール a と b は連続している必要はありません。a と c にも同じ追加コストが適用されます。予想どおり、この問題は、総コストが最小になるように、企業へのモジュールの割り当てを見つけることを望んでいます。

何か案は ？

ツリーのようなネットワーク、つまり、シンク (およびそれに関連するエッジ) を削除するとツリーが残るようなネットワークの最大フローを (線形時間で) 計算するアルゴリズムを見つけることができますか?

3D で n 個の開いた幾何学的な線があります。線の端点間の追加の線の最小長という基準に基づいて、単一の線に結合する必要があります。複雑さが最小限のアルゴリズムを提案してください。

今日、ラボで（2時間で）完了する課題がありました。質問は：

• m*n行列が与えられます。
• マトリックスには、「h」の寮と「b」の本館の入り口があります。
• これらの「h」ホールと「b」入口の位置は既知です（（x、y）座標に関して）。
• すべての寮が「b」の入り口の1つに到達するための少なくとも1つの方法を持つように経路を敷設する必要があります。
• そのような切断された経路はせいぜい「b」である可能性があります。
• 経路の長さは最小でなければなりません。
• 上、下、左、または右にのみ移動できます。
• 解決策はブルートフォース攻撃であってはなりません。

割り当ては終了しました。しかし、私はまだこれがどのように解決されるかを考えています。そのような問題の標準的な用語はありますか？何を読めばいいですか？

人々はそのようなアルゴリズムを都市に道路を敷設するためにも使用していますか？

方向付けされた重み付けされていないグラフが与えられ、問題は最大長の単純なパスを見つけることです (開始頂点と終了頂点は固定されていません)。もちろん O(n^2 * 2 ^n) で解けますが、O(n * 2 ^ n) というアルゴリズムがあると聞きましたが、これは私が知りません。では、O(n * 2 ^n) でそれを解決するにはどうすればよいでしょうか。//n = |V|

Povray を使用して、クラスター上で画像をレンダリングしています。各ワーカー ノードは、部分的なイメージをレンダリングします。この質問の主題は、適切な分割アルゴリズムを見つけることです。

Povray は、ピクセル単位でレンダリングします。ただし、各ピクセルには固有の複雑さがあるため、レンダリングにかかる​​時間は異なります。

画像を多くの領域に分割しました。たとえば、2x2 ピクセルの領域です。そして、これらの領域のいくつかをレンダリングしました。これらの領域の複雑さは、周囲の領域の複雑さに影響を与えるため、領域の配列全体が複雑さの値で満たされます。

画像を領域に分割します。各リージョンは次を定義します。

• 開始列、終了列。
• 開始行、終了行。
• そのゾーンの複雑さ。

目的は、マージされたときにすべての地域をカバーするジョブのリストを作成することです。ジョブは同様の複雑さを持つ必要があります。

各ジョブは次を定義します。

• 開始列、終了列。
• 開始行、終了行。

制約:

• ジョブの有効なマクロ領域は、長方形または正方形です。
• ジョブの数は N です。

CART (Classification and Regression Tree) アルゴリズムで連続属性を分割する方法がわかりません。CART はカテゴリ属性と連続属性の両方を分割できることがわかっているためです。

私は多くの論文を読みましたが、分割ポイントになる値はシーケンスの中間値であると書かれています。私はそれについて理解していません。それが何を意味するのか説明して、いくつかの例を挙げてもらえますか?

ありがとう

私自身のベンチマークとなる C++ Kruskal の実装を探しています...良いものをいくつか知っている場合は、共有してください!

有向グラフが与えられた場合、すべてのノードが正確に1つの入力エッジと正確に1つの出力エッジを持つように、エッジのランダムなサブセットを見つけるために使用できるアルゴリズムは何ですか？

たとえば、これは私が与えられたグラフである可能性があります：

そして、これは有効な出力グラフになります。

これは次の理由で有効です。

• 入力グラフ上のすべてのノードが含まれています
• そのすべてのエッジも入力グラフ上にあります
• すべてのノードには、ノードを離れるエッジとそこに来るエッジが1つだけあります（同じエッジにすることはできません。ループは許可されません。すべてのノードは、少なくとも1つの他のノードに接続する必要があります）。

検出すべき解決策がない場合。

これを解決するための効率的なアルゴリズムはありますか？

ありがとう！