問題タブ [decomposition]

そのため、凸多角形の最小加重三角形分解を見つけるための動的計画法アルゴリズムを理解しようとしています。ご存じない方のために説明すると、三角形分割とは、凸多角形を三角形に分割することです。最小加重三角形分割は、すべてのエッジ (またはすべての三角形の周囲) の合計が最小になるポリゴンの三角形分割です。

それは実際にはかなり一般的なアルゴリズムですが、私には理解できません。私が理解しようとしているアルゴリズムは次のとおりです。

http://en.wikipedia.org/wiki/Minimum-weight_triangulation#Variations

これが私が従おうとしている別の説明です（5.2最適な三角形分割までスクロールダウン）：

http://valis.cs.uiuc.edu/~sariel/teach/notes/algos/lec/05_dprog_II.pdf

ですから、ここまではよくわかりました。すべての頂点を取得し、それらが元のポリゴンの周囲を時計回りに配置されていることを確認します。頂点 i から始まり頂点 j に向かう多角形の MWT(i, j) と呼ばれる最小重み三角形分割を返す関数を作成します。この関数は再帰的であるため、最初の呼び出しは MWT(0, n-1) である必要があります。n は頂点の総数です。MWT は、ポイント i、j、および k で構成されるすべての三角形をテストする必要があります。ここで、k はそれらの間の任意の頂点です。これまでの私のコードは次のとおりです。

ただし、実行するとスタックがオーバーフローします。私は完全に迷っており、誰かが私を正しい方向に導くのを手伝ってくれれば幸いです.

さらに情報が必要な場合は、お尋ねください。

そのため、凸多角形の最小重量三角形分割を見つける Python のプログラムに取り組んできました。これは、重み (すべての三角形の周囲の合計) と弦 (境界ではなく三角形に分割するポリゴンを通過する線) のリストを見つけることを意味します。

私は動的計画法アルゴリズムを使用しているという印象を受けましたが、もう少し複雑なポリゴンを使用しようとすると、永遠にかかります(完了していないため、どれくらいかかるかわかりません)。

10 面のポリゴンで問題なく動作しますが、25 面を試しているため、機能が停止しています。先生がポリゴンをくれたので、25 ポリゴンでも問題ないと思います。

このアルゴリズムは であると想定されているためO(n^3)、25 辺の多角形の計算には約 15.625 倍の時間がかかるはずですが、10 辺の多角形は瞬時に見えるため、時間がかかります。

私が気付いていない、ある種の n 操作を行っていますか? リストをセットに変換して重複を取り除く最後の部分を除いて、私がしていることは何も見えませんが、私のプログラムでは、変換が行われる前に分解後にトレースを入れましたが、そうではありませんその点にさえ達します。

これが私のコードです。これ以上情報が必要な場合は、お問い合わせください。そこにある何かがそれよりも時間がかかってO(n^3)いるので、それを見つけてトリミングできるようにする必要があります.

使用しているポリゴンを追加します。最初のポリゴンはすぐに解決されますが、2 番目のポリゴンはこれまでに約 10 分間実行されています。

最初の1つ：

二つ目：

部分ピボットを使用して独自のLU分解を実装しようとしています。[L, U, P] = lu(A)私のコードは以下のとおりで、明らかに正常に機能していますが、一部の行列では、matlabの組み込み関数と比較すると異なる結果が得られます。

誰かがそれがどこで間違っているかを見つけることができますか？

これが私がテストした2つのマトリックスです。最初のものは正しいですが、2番目のものはいくつかの要素が反転しています。

アップデート

コードをチェックしていくつかのバグを修正しましたが、部分的なピボットにはまだ何かが欠けています。最初の列では、最後の2行が常に反転しています（matlabのlu（）の結果と比較して）

これについてはあまり情報が見つからないようですので、ここで取り上げることにしました。私がよく遭遇する問題の 1 つは、リストの処理中に単一のオブジェクトを作成するユニット テストです。たとえば、 のようなメソッド シグネチャがありIEnumerable<Output> Process(IEnumerable<Input> inputs)ます。単一の入力を単体テストするときは、1 つの入力のリストを作成し、単純First()に結果を呼び出して、それが期待どおりであることを確認します。これにより、次のような結果が得られます。

私の現在の考えでは、1 つのクラスがオブジェクトの作成を担当し、別のクラスが入力リストの調整を担当する必要があります。以下の例を参照してください。

Output上に投稿された内容を使用して、指定された の1 つのインスタンスを作成できることを簡単にテストできますInput。SingleCreatorfrom 以外のコード ベース内の他の場所を呼び出す必要がないことに注意してくださいCompositeCreator。作成ICreatorすると、現在のプロジェクトで現在2〜3回行っている同様のタスクを実行する必要がある他の時間に再利用するという利点も得られます

これについて何か光を当てることができる経験がある人はいますか? 私は単にこれを考えすぎていますか？提案は大歓迎です。

コースで提供されているスライドは、説明がなく、推論方法の例を示しているだけだと感じているため、合成アルゴリズムと候補キーの検索に関していくつかの問題があります。

したがって、単一の関係 R[ABCDE] を持つリレーショナル スキーマがある場合、機能的な依存関係: {AB->CD, C->AD, E->B},

これまでのところ、私はここにたどり着きました: 正規のシェルは: C={AB->C, C->D, E->B} で、候補キーは: EB AE と EC です。

1) 合成アルゴリズムを適用して、ロスレスで依存関係を保持する 3NF 分解を見つけます。

分解が実際にロスレスで依存関係が保持されているかどうかを確認する方法は知っていますが、そこに到達する方法は知りません。下記を参照してください：

i) F のカノニカル カバー C を構築する

ii) C'={X 結合 Y | X->Y "所属" Consol(C)} これは私が知っている

iii) C を C' のサブセットと定義し、別の関係に含まれるすべての関係を削除します。これは、私が正しいと思うかどうかを知っています。

iv) C が R のスーパーキーを既に含んでいる場合、C2 を C と定義します。このステップがわかりません。

2) 3) で得られた分解が BCNF にもあるかどうかを徹底的に動機づける。

前もって感謝します！

三重対角行列を表すクラスを作成しています。これらは、対角線上にゼロ以外の値のセットを持ち、上下の対角線上にゼロ以外の値を持ち、それ以外はすべてゼロである正方行列です。

それらを格納するために、3 つの 1D 配列を使用しています。対角線ごとに 1 つです。

次に例を示します。

したがって、a_i 用に 1 つ、u_i 用に 1 つ、l_i 用に 1 つの配列があります。ゼロは保存されません。

LU 分解を実行するアルゴリズムが必要です。LU 分解は通常、次の 2 つの行列を生成します。

ただし、1 はゼロと同様に役に立たず、スペースを浪費するだけなので、LU 分解として機能する次の三重対角行列を返すアルゴリズムが必要です。

私は次の方程式を得ることができました：

しかし、必要な a_i、b_i、および c_i のすべての一般式を見つける方法がわかりません。

私のためにこれを行うための、プログラムしやすいアルゴリズムを知っている人はいますか。私は効率的なものを探しているわけではなく、実際にプログラムするのが最も簡単なものを探しています。

よろしくお願いします。

現在、MPI 並列化を使用して C で記述されたプログラムを使用しています。計算グリッドは、一般的なドメイン分割手法を使用して分割されます。プロセスのレイアウトは、2D 分解 (簡略化) に関して次のとおりです。

コードのある時点で、X 依存のみを持つ一連の方程式を解かなければなりません。現在の形式のトポロジでは、x 依存関係のために一度に 3 つのプロセスでしか並列化できません。これが私の質問につながります...現在のトポロジを別のトポロジにマップする便利で効率的な方法はありますかコード内で、完全な並列化、つまり 9 つのプロセスすべてを使用することを好むのはどれですか? たとえば、次のようなものです。

なぜこれから始めないのかと尋ねる人がいるかもしれません.2Dドメイン分解は全体的な問題に対してはるかに効率的です.さらに、トポロジーで同様のことを行う必要があるy依存関係もあります.したがって、上の画像は次のようになります.転置。

したがって、9 つのプロセスで完全な並列化を可能にするために、いくつかの通信ルーチンを使用してコード内で (オンザフライで) 2D トポロジーを 1D トポロジーにマップする必要がありますが、これを行う効率的で効果的な方法があるかどうかはわかりません。 VSは、3つのプロセスを並行して元の問題を実行しています。どんな提案も役に立ちます。ありがとう！！