- 先日、正単体を組み合わせた格子座標系上のある点からもっとも近い格子点ってどうやったらわかる?ということが話題になった
- 多次元立方格子の場合には、各軸の値を四捨五入してやっておしまい
- はて、正単体組合せでは…となった
- どうも、近い格子点を探す方法で良いものはなかなかないなー、と思っていたら、それは「最短ベクトル問題」と呼ばれるNP困難な問題だと言う(こちらやこちら)
- 性質のよい格子の場合にはみつかるけど、ということで、超立方格子はもちろん、性質がものすごくよいものらしい
- 直交している座標系っていうのは、軸の組合せに関する情報が全部0になるので、組合せ発散しないことがその(ある意味での)理由の様だった
- 正単体なら、対称性も完璧だし、「性質が良い」のでは…と思うので、ちょっと考えてみる
- なる実亜空間上の点から最短距離にあるなる亜空間上の格子点を求めたい
- 性質が完璧な超立方格子を利用することとする
- 正単体格子は、超立方格子の部分集合である。原点からのハミング距離が一定である点の集合である
- 従って、実亜空間上の任意の点について、ひとまず、k次元超立方格子点の最短距離のものを探す(これは上述のように簡単)
- このようにして探した立方格子点が亜空間上にあれば、探索は終了
- 不幸にして亜空間上にないときは、その仮の点(仮格子点)から、立方格子を何歩か歩けばたどり着けるだろう
- 何歩あるくかは、仮格子点がとなっていてであるから、歩だけ歩けばよさそう。ここでの符号は歩くべき格子の向きについての情報を持っているので、『符号付き歩数』として取り扱いたい
- ある符号付き歩数を歩くときに、あっちへプラス3歩、こっちへマイナス2歩で結果として的には1歩分となる、という計算もあるが(この歩き方は、(おそらく)最短距離格子点の探索という条件から不適切である(ことが示せると思う)
- また、ある方向に2歩してもよいか、というと、それも「そんなことができるなら、その方向に1歩の点の方が近いからだめ」というようなやり方で、不可であることが示せる(と思われる)
- 従って、ある特定の軸について0か1歩で、総歩数がの絶対値になるような歩き方でたどり着く点が求める最近格子点になるのではないだろうか
- すると、問題は、どの軸についてどちらに、というのが問題になる
- これを解決するのに、総当たりでやることにすると、次元が高いときに、組合せ発散をしそうだ
- 今、亜空間上の点の座標と、仮格子点の座標はわかっているから、その2点を結ぶベクトルもわかる。そのベクトルと遠くないような一歩を選ぶのが、他の一歩を選ぶよりもよいだろう。そんな選び方で歩歩いてたどり着くことにする
- この結果をRで確かめると、最適ではないことが分かった。やはり、ある方向に1歩行くのと、あっちとこっちと合わせて3歩で的に1歩なのとでは、どちらがよいかはそれほど単純ではないことが実例からわかった
- Rでやってみる
- このようにして求めた格子点の周りをランダムに探索して、よりよい点が現れるかどうか、調べてみると、そこそこの回数を酔歩しても、そんな点は現れないようだ…だが、次元を上げると、もっと近い点も表れるようだ…
library(MCMCpack)
k <- 10
v <- 100
n <- 10
R <- rdirichlet(n,rep(1,k))*v
R.rd <- round(R)
hist(apply(R.rd,1,sum))
n.steps <- apply(R.rd,1,sum) -v
R.rd2R <- R- R.rd
drc <- -sign(n.steps)
sign.R <- sign(R.rd2R)
tobeselected.R <- sign.R * drc
Ans <- R.rd
for(i in 1:n){
tmp.select <- which(tobeselected.R[i,] > 0)
tmp <- R.rd2R[i,tmp.select]
tmp.val <- abs(R.rd2R[i,tmp.select])
ord <- order(tmp.val)
if(abs(n.steps[i])>0){
tmp.d <- tmp.select[ord[1:abs(n.steps[i])]]
tmp.v <- rep(0,k)
tmp.v[tmp.d] <- 1*drc[i]
Ans[i,] <- R.rd[i,] + tmp.v
}
}
Ans
apply(Ans,1,sum)
n.iter <- 10000
dist.x <- matrix(0,n,n.iter)
for(i in 1:n){
tmp.dist <- sqrt(sum((Ans[i,]-R[i,])^2))
for(j in 1:n.iter){
g <- sample(1:5,1)
tmpp <- Ans[i,]
for(j2 in 1:g){
g2 <- sample(1:k,2)
tmpp2 <- tmpp
tmpp2[g2[1]] <- tmpp[g2[1]]+1
tmpp2[g2[2]] <- tmpp[g2[2]]-1
tmpp <- tmpp2
}
tmp.dist2 <- sqrt(sum((tmpp-R[i,])^2))
dist.x[i,j] <- tmp.dist2-tmp.dist
}
}
for(i in 1:n){
plot(sort(dist.x[i,]))
}
hist(dist.x)
min(dist.x)
- あるk次元座標のfloorを取ると、それを基準とした辺の長さ1のk次元立方体の中にその点はある
- このk次元立方格子の頂点の数は個
- この個は座標の和の値によって群に分かれる。そのうちの一つが調べている点と同じ亜空間上の点となる
- したがって、[ted:\begin{pmatrix}k \\i \end{pmatrix}]個の点が対象となる
- この数はたかだか個である
- で、結局、これよりは減らせなさそう…
- この方針は、アプローチを色々変えられるけれども、きれいに並んだ点に関するボロノイ図の作成、と同じことのようです。