効率の良いアルゴリズムをつくる方法を教えて頂けないでしょうか。

Question

効率の良いアルゴリズムをつくる方法を教えて頂けないでしょうか。
ノードで三角形を作っていき、全ての点を結んで行ったり、三角形を作ったりするアルゴリズムです。

以下のようなグラフについて、

行列Eと行列N があります。

行列Eは、それぞれの三角形１、２、３、....１６においての３点を結んだものです。
行列Nは、それぞれの青い点１、２、３、...１６に、隣接する、三角形の数字を並べたものです。

それぞれ、一番小さい数字からはじまり 、半時計周りです。

例えば、Eは６行目に、三角形６を作る３点、１０、１１、１５があります。
また、Nは、１０行目に、点１０に隣接する三角形、５、７、８、６があります。

---

この行列において、
（１）
Nのみが与えられたとき、Eの行列を作り上げる
（Eの行列の中身の順番には、特に指定はありません）
ことができるプログラミングのアルゴリズム１
(教えて頂きました。本当にありがとうございました。)

1. N を読み込み、行数Nnを数える
2. N の一番大きな数字を見つける　#（１６）
3. 16行x3列のEという空の行列を作る。
1. For i 1:Nn　# N行のループ
   1. For j 1: len(N[i]) #Nそれぞれの行の要素数の分だけループ
     1. E[ N[i ][j] ]に i を ストック

（２）
Eのみが与えられたとき、点と点を結ぶ線の数（黒線）を求める、
ことができるアルゴリズム２

1.

を考えています。

---

O(N)のあるアルゴリズムをつくっているのですが、
アルゴリズムがどうしても思いつかなくなり、質問をさせて頂きました。

ちなみに、

E行列からN行列を求めるO(N)アルゴリズムは、

(Eの行列から、N行列を求める)
1. EからNe行をの行数を数える
2. Nn = Eで一番大きい数をストックする
3. Counter ベクトル　c=0　を、サイズNnで作る
4. N=0 空の行列
5. For e = 1: N
    1. for i 1:3 #3つエントリーがあるから
    2. n = E[e,i]
    3. c[n] = c[n] +1
    4. N[n,cn] = e

と導き出せたのですが、
上の（２）の効率の良いアルゴリズムが思いつきませんでした。

どなたか、効率の良いアルゴリズムを教えて頂けないでしょうか。
どうか、宜しくお願い致します。

（２）のアルゴリズム

1. EからNe行をの行数を数える
2. Nn = Eで一番大きい数をストックする
3. Counter ベクトル　C=0 ＃三角形の辺の数
4. B=0 空の行列　＃三角形の辺を保存する
5. A  0 空の行列　＃現在みているの三角形辺を保存する
6. For e = 1: Nn
    1. For i  1:3 #3つエントリーがあるが、
        1. C = C + 3

        1. テーブルの作成
            1. If i == 3:
                1. B[ i ] = [ E[e,i], E[e,i-2]]
                2. A[ i ] = [ E[e,i], E[e,i-2]]
            2. else:
                1. B[ i ] = [ E[e,i], E[e,i+1]]
                2. A[ i ] = [ E[e,i], E[e,i+1]]


        1. num=A ∩ B をして、重なった数字をCから消す
        2. C = C-num
        3. 
        4. A を空にする。

Comments

[think49]

> それぞれ、一番小さい数字からはじまり 、半時計周りであるというルールがあります。

と

> Nのみが与えられたとき、Eの行列を作り上げる
> （Eの行列の中身の順番には、特に指定はありません）

の条件が矛盾していませんか。
要件は一カ所にまとめてリストすると、間違いがないと思います。

---
tamago_yaki さんが提案したアルゴリズムは全て反時計周りではないので、必要なら座標計算を入れて下さい。

[tamago_yaki]

説明がわかりずらく、申し訳ありません。
E,N行列が半時計周り、小さい数字から始まるものであり、

（１）（２）のアルゴリズムでの制約は、　O(N)のみです。
編集しておきます。申し訳ありません、

Answer 1

線の数は、三角形の数×3 - 二つの三角形に共有されている辺の数　で出ます。
共有されてる辺の数はハッシュで管理すれば辺の数に比例する計算量で数えられます。

---

ハッシュで辺を管理する場合の頂点が入れ替わっただけの辺について

一つは正規化をするという方法
つまり、(i, j)という辺があったとき i > j ならiとjを入れ替えるというような操作を加えて順番による影響がないようにできます。

もう一つは今回の問題限定で、E行列において頂点は反時計回りに現れるので同じ辺が2度現れるなら、必ず頂点の順番は逆になります。なので、そのコードでいうとAに逆順で辺を入れると以前に現れた同じ辺だけカウントできます。

あとはぶっちゃけ想定解が何かという話になってくるので、ハッシュってなんだ?って状態なのであれば、おそらく違う方法を使うべきなんだと思います。
例えば連結成分の数が1であることがわかってるだとか、DFSやBFSについて勉強してるという前提であれば、頂点数+三角形の数-連結成分の数 で求めることが想定されてるのかもしれません。

Comments

[tamago_yaki]

ご回答、本当にありがとうございます。
ハッシュテーブルの管理方法が思いつかなかったのですが、新しいベクトルを使えば良いのか、と考え
作らせて頂きました。

1. EからNe行をの行数を数える
2. Nn = Eで一番大きい数をストックする
3. Counter ベクトル　C=0 ＃三角形の辺の数
4. B=0 空の行列　＃三角形の辺を保存する
5. A 0 空の行列　＃現在みているの三角形辺を保存する
6. For e = 1: Nn
＿＿ 1. For i 1:3 #3つエントリーがあるが、
＿＿＿＿1. C = C + 3

＿＿＿ 1. テーブルの作成
＿＿＿＿＿1. If I == 3:
＿＿＿＿＿＿＿1. B[ i ] = [ E[e,i], E[e,i-2]]
＿＿＿＿＿＿＿2. A[ i ] = [ E[e,i], E[e,i-2]]
＿＿＿＿＿2. else:
＿＿＿＿＿＿＿1. B[ i ] = [ E[e,i], E[e,i+1]]
＿＿＿＿＿＿＿2. A[ i ] = [ E[e,i], E[e,i+1]]

＿＿＿1. num=A ∩ B をして、重なった数字
＿＿＿2. C = C-num
＿＿＿3.
＿＿＿4. A を空にする。

（上の質問ページにも追加させて頂きました）

このようなアルゴリズムでしょうか。
たくさんのアイディア、ありがとうございます。
また、もしできましたら、ハッシュテーブルをどのように使えば良いか、少し詳しく教えて頂けると、
大変気になっているので凄く嬉しいです。

本当にありがとうございます。

[tamago_yaki]

また、私の書いたものだと、B行列の数字をいれる順番によっては、Aの行列と比べて調べたときに、
（三角形の数字を入れる）順番が真逆だと、判断できないのではないかと悩んでいます。
元々のE行列が半時計周りなので、この問題では数字の順番は問題ないでしょうか。

[tamago_yaki]

重ねて、ご回答ありがとうございます。
＞一つは正規化をするという方法
つまり、(i, j)という辺があったとき i > j ならiとjを入れ替えるというような操作を加えて順番による影響がないようにできます。

なるほどです。そうすれば、順番など関係なくできますね。
ありがとうございます。

私の書いたアルゴリズムだと、

ループ後に、Bをソートして共通する部分を消して、
Bの行の数を数えれば、合計の辺の数になる、と考えたのですが、

このように、行列に数値を入れ込んだり、ソートをしてしまうのは、O(N)とは言えないのでしょうか、、
初心者の質問で申し訳ないのですが、O(N)はループ一回のみなら何をしても良いのか、、と迷ってしまいました。教えて頂けると本当に助かります。宜しくお願い致します。

[yudedako67]

例えばソートがO(NlogN)ならO(N)ではないです

[fana]

Nの値を増やしていったときにそれに対して計算量（"計算時間"と言った方が想像しやすいか）がどう変化するのか？
計算量がNに比例するならO(N)．

ループが１回だろうが，その内側で N^100 に比例して計算量が爆増するような処理を書いてたりすれば，それは O(N) とは言わない．

Answer 2

「反時計回り」の制約がよくわからず、またそれが一意に定められるかどうかも不明ですが、
アルゴリズム1においてEの順番に制約がないのであれば、非常に簡単です。
Nにおいて、1の点の周りに三角形4，7，5があるという事は、
点1は三角形4，7，5を構成する点の1つであるという事です。
つまり、Eの4行目、7行目、5行目に1を入れればいいのです。
以下同様にしてN全体をなめれば、Eの行列は自然に出来上がります。
1回のループでいいので、O(N)という条件も満たします。

アルゴリズム2はまだわかってないので投げます。

Comments

[tamago_yaki]

お早い解答、本当にありがとうございます。
また、丁寧にアルゴリズムの説明をして頂き、ありがとうございます。
非常にシンプルで、とてもわかりやすく、こんなに簡単にできるのか、と感動しました。
本当にありがとうございます。

swordone 様の アルゴリズム を文字で書いてみました。

1. N を読み込み、行数Nnを数える
2. N の一番大きな数字を見つける　#（１６）
3. 16行x3列のEという空の行列を作る。
1. For i 1:Nn　# N行のループ
＿＿＿1. For j 1: len(N[i]) #Nそれぞれの行の要素数の分だけループ
＿＿＿＿＿1. E[ N[i ][j] ]に i を ストック

swordone様の教えて頂いた通り書けているでしょうか、
確認して頂けると、助かります。

この度は、本当にありがとうございました。
早速コードに書いてみようと思います。