問題タブ [triangular]

いくつかの基本的な線形代数演算を実装しようとしていますが、これらの演算の 1 つは三角 (上および/または下) 行列の反転です。それを行うための簡単で安定したアルゴリズムはありますか?

ありがとうございました。

次のようなベクトルがあるとします。

これは本当に：

そして、行列を生成するためにベクトル/行列関数と演算子のみを使用したいと思います:

または次のマトリックス:

アイデアはありますか？

（私はMATLABの初心者ですが、このようなことに悩まされてきました...）

読み込んだ画像に三角形を描く必要があります。三角形は次のようになります。

しかし、私が抱えている主な問題は、そのようなマトリックスを作成する方法がわからないことです。この行列に画像を掛けたいのですが、画像行列は3つのパラメータ（W、H、RGB）で構成されています。

序章

より大きなプログラム（ボリュームグラフィックスのレンダリングに関連する）の​​一部として、任意の（ただし有限の）三角形の2Dメッシュに特定の方法でラベルを付ける必要がある、小さいがトリッキーなサブ問題があります。少し前に、その時点で使用していたテストメッシュに十分なソリューション（以下を参照）を作成しましたが、考えられるすべてのメッシュに対してこのアプローチがうまく機能しない可能性があることに気付きました。今、私はついに現在のソリューションがまったくうまく機能しないメッシュに遭遇しました-そして私はまったく異なる種類のアプローチを考え出すべきであるように見えます。残念ながら、自分の考え方をリセットすることはできないようです。そのため、ここで質問したいと思いました。

問題

下の写真を考えてみましょう。（色は問題の一部ではありません。視覚化を改善（？）するために色を追加しただけです。また、エッジ幅の変化はまったく関係のないアーティファクトです。）

すべての三角形（たとえば、オレンジ色のABCと緑色のABD）について、3つのエッジのそれぞれに、「0」または「1」などの2つのラベルのいずれかを付ける必要があります。要件は2つだけです。

1. 三角形のすべてのエッジに同じラベルを付けることができるわけではありません。つまり、三角形ごとに2つの「0」と1つの「1」、または2つの「1」と1つの「0」が必要です。
2. エッジが2つの三角形で共有されている場合は、両方で同じラベルを付ける必要があります。つまり、画像のエッジABが三角形ABCの​​場合は「0」とラベル付けされている場合、ABDの場合も「0」とラベル付けされている必要があります。

メッシュは本物の2Dメッシュであり、有限です。つまり、メッシュはラップせず、明確に定義された外側の境界があります。明らかに、境界線では要件を満たすのは非常に簡単ですが、内部ではさらに難しくなります。

直感的には、証明できなくても、少なくとも1つの解決策が常に存在する必要があるように見えます。（通常、いくつかあります-それらのいずれか1つで十分です。）

現在のソリューション

私の現在の解決策は本当にブルートフォースの解決策です（完全を期すためにここで提供されています-このセクションをスキップしてください）：

• 三角形の4つのセットを維持します-ラベル付けされる残りのエッジの可能なカウント（0..3）ごとに1つ。最初は、すべての三角形がセット内にあり、3つのエッジにラベルが付けられたままになっています。
• ラベルのないエッジを持つ三角形がある限り：
  まだ三角形が残っている、割り当てられていないエッジのゼロ以外の最小数を見つけます。言い換えれば、いつでも、ラベル付けが部分的に完了している三角形の数を最小限に抑えるように努めています。残りのエッジの数は1から3の間です。次に、この特定の数のエッジが割り当てられるように、そのような三角形を1つ選択します。この三角形に対して、次のようにします。
  • 残りのエッジのラベル付けが、他の三角形のラベル付けによってすでに適用されているかどうかを確認します。その場合は、上記の要件2で示されているようにラベルを割り当てます。
  • これにより行き止まりになる場合（つまり、現在の三角形で要件＃1を満たせなくなる場合）、プロセス全体を最初からやり直します。
  • 次のように残りのエッジを割り当てます。
    • これまでにラベル付けされたエッジがない場合は、最初のエッジをランダムに割り当てます。
    • 1つのエッジがすでに割り当てられている場合は、反対のラベルが付けられるように2番目のエッジを割り当てます。
    • 2つのエッジが割り当てられた場合：同じラベルが付いている場合は、3番目のエッジに反対のラベルを割り当てます（明らかに）。2つのラベルが異なる場合は、3番目のラベルをランダムに割り当てます。
  • 未割り当てのエッジの数が異なる場合は、三角形のセットを更新します。
• 私たちがここに着いたら、解決策があります-やったー！

通常、このアプローチは数回の反復で解決策を見つけますが、最近、アルゴリズムが1〜2千回の再試行後にのみ終了する傾向があるメッシュに遭遇しました...これは明らかに、終了しないメッシュが存在する可能性があることを示唆しています。

今、私は常に解決策を見つけることが保証されている決定論的アルゴリズムが欲しいです。メッシュはそれほど大きくなく、ラベル付けは基本的に新しいメッシュがロードされたときにのみ実行する必要があるため、計算の複雑さはそれほど大きな問題ではありません。これは常に発生するわけではありません。したがって、（たとえば）指数関数を使用するアルゴリズムそれが機能する限り、複雑さは問題ないはずです。（しかしもちろん：より効率的であるほど良いです。）

ここまで読んでいただきありがとうございます。さて、どんな助けでも大歓迎です！

編集：提案された解決策に基づく結果

残念ながら、Dialecticusによって提案されたアプローチを機能させることができません。うまくいかなかったかもしれません...とにかく、開始点が緑色の点で示されている次のメッシュを考えて みましょう。少しズームインしてみましょう... それでは、アルゴリズムを開始しましょう。最初のステップの後、ラベル付けは次のようになります（赤=「スター付きパス」、青=「リング状パス」）： これまでのところ良好です。2番目のステップの後： そして3番目： ... 4番目： しかし今、私たちは問題を抱えています！もう1ラウンドやりましょう。ただし、マゼンタでプロットされた三角形に注意してください。 私の現在の実装によると、マゼンタの三角形のすべてのエッジはリングパス上にあるため、青色である必要があります。これは事実上反例になります。どういうわけか間違っているかもしれません...しかし、いずれにせよ、開始ノードに最も近い2つのエッジを赤にすることはできません。3番目のラベルが赤で表示されている場合、そのソリューションはもはやアイデアに実際には適合していないようです。

ところで、これが使用されたデータです。各行は1つのエッジを表し、列は次のように解釈されます。

1. 最初のノードのインデックス
2. 2番目のノードのインデックス
3. 最初のノードのx座標
4. 最初のノードのy座標
5. 2番目のノードのx座標
6. 2番目のノードのy座標

開始ノードは、インデックス1を持つノードです。

次に、RafałDowgirdによって提案された方法を試してみるべきだと思います...しかし、おそらくしばらくの間、まったく異なることをする必要があります:)

三角行列を表す非常に大きな配列にメモリを割り当てる必要があります。私は次のコードを書きました：

問題は、マトリックスのサイズが大きくなると、（メモリを割り当てるために）それを実行するのに必要な時間が急速に長くなることです。誰かがこの問題のより良い解決策を知っていますか？

ありがとう。

私は 2 つの部分からなる宿題に取り組んでいます。1 つ目は、特定のペア X、Y がhttp://en.wikipedia.org/wiki/Triangular_numberに属しているかどうかをチェックする Prolog プログラムを作成することです。例: (2, 3) = true; (4, 10) = true など。

最初の解決策は「通常の」再帰を使用し、私はこれを次のように解決しました:

2 番目の部分は、三角形/3 述語を使用して、末尾再帰/アキュムレータを使用してこれを解決することです。私は別の割り当てでアキュムレータを使用しましたが、その使用は非常に明白でした。そのため、アキュムレータの一般的な使用方法については理解していますが、このコンテキストでの使用方法については非常に困惑しています。

したがって、私はアルゴリズムを探しているのではなく、むしろ自分で解決したいと思っていますが、このコンテキストでアキュムレータを適用する方法についてのより実用的なアドバイスです。

重複の可能性:
配列から三角形を見つける

このフォーラムでこのインタビューの質問を見つけました: http://geeksforgeeks.org/forum/topic/check-for-triangular-triplet

以下の説明をコピーしています (礼儀は geeksforgeeks.org と元のポスターのカピル)

N 個の整数からなるゼロ インデックスのベクトル A が与えられます。

トリプレット (P、Q、R) は、次の場合に三角形です。

たとえば、次のようなベクトル A を考えます。

トリプレット (0, 2, 4) は三角形です。

プログラムを書く:

N 個の整数で構成されるベクトル A が与えられた場合、このベクトルに三角トリプレットが存在する場合は 1 を返し、そうでない場合は 0 を返します。

編集: 入力ベクトルは変更しないでください。また、O(1) のスペース要件があるため、配列をコピーすることはできません!

と仮定する：

N は範囲 [0..100,000] 内の整数です。ベクトル A の各要素は、範囲 [-2,147,483,648..2,147,483,647] 内の整数です。

たとえば、次のようなベクトル A が与えられます。

上記で説明したように、関数は 1 を返す必要があります。

もう一つの例：

次のようなベクトル A が与えられた場合

関数は 0 を返す必要があります。

予想される最悪の場合の時間の複雑さ: O(n log n) 予想される最悪の場合の空間の複雑さ: O(1)

明らかに配列をソートすることはオプションではありません。この問題を解決する方法について何かアイデアはありますか?

Python を使用してメッシュを作成したい 3 次元ポイントのデータセットがあります。私が見たすべてのソフトウェアでは、エッジを提供する必要があります。3D の一連の点を入力として取り、一連の三角形メッシュを出力する Python のプログラムはありますか? できればメッシュを均一にしてほしいです。

ありがとう - エリ。

Ax = b 型の希望する 'n' 個の連立方程式を解くための MATLAB コードの問題で、解法に上三角行列の方法が含まれ、A と b の値が x の値と共に Aprime と bprime に展開されます。

問題は、上三角行列を使って Ax = b 型の n 個の連立方程式を解くコードを書くことです。A と b の値は、コマンド ウィンドウで行列として指定されます。プログラムが正常に実行されると、コードは応答として Aprime、bprime、および x の値を返す必要があります。コードはまた、特定の方程式に対して「エラー、行列の次元が一致しません」(または何でも!) として出力を与える必要があります! 上記のエラーメッセージとともにエラーが表示されることを除いて、コードは正常に機能します。

私が使用したコードは次のとおりです。

適切な修正を提供してください....

コマンド ウィンドウで得られた結果、

A = [1 1 0;2 1 1;1 2 3]

A =

b= [3;7;14]

b =

[x, Aprime, bprime] = 解決済み(A, b)

×＝

アプリメ=

bprime =

-0.5000 -11.0000

2番目のタイプは、

A = [1 2 3; 4 5 6]

A =

b = [7;8;9;10]

b =

[x, Aprime, bprime] = solve(A, b) エラー!! 行列の次元は一致する必要があります。解決済みのエラー (2 行目) n = size(A); "C:\Users\Hari\Documents\solved.m>solved" への呼び出し中に、出力引数 "x" (およびおそらくその他) が割り当てられません。

R には非常に大きな (約 9100 万のゼロ以外のエントリ) sparseMatrix() があり、次のようになります。

これを三角行列(上か下)に変換したいのですが、myMatrix = myMatrix * lower.tri(myMatrix) を実行しようとすると、lower.tri() に対して「問題が大きすぎます」というエラーが発生します。誰かが解決策を知っているかどうか疑問に思っています。助けてくれてありがとう！