p11271.jpg

XY平面に無限に広がる抵抗ネットワークに対し、任意の両点(格子点)間の抵抗値を求める問題。自分は大学では電子工学を勉強したのに解けない。情けないことかな。

1. 問題
任意の両点だが、無限に広がっているので、原点をどこに取っても同じはず。そこで、両点の片方を原点にし、原点からの抵抗値を求めるというのが本問題。なお、1Ωとは隣接両点間の線分の抵抗値。

ネット上を調べたら、(0,0)と(1,0)間の抵抗値は0.5Ωとなる解説は多いが、ほとんどが事後解釈の領域を出ない。(0,0)と(1,1)間の抵抗値が分かるのであれば、はじめて本物と認めてあげたい気持ちになる。

2. 計算法
自分の知識では全く歯が立たないので、一生懸命ネットを調べた。すごいことにそれを計算した論文をついにみつけた。

(PDF) Infinite resistive lattices

細かい中身はご自身でみてもらうことにして、必要な計算式と計算結果の一部を紹介しておく。

p11271-1.jpg
p11271-2.jpg

変数nとpはそれぞれy座標、x座標と考えてよい。対称性があるから、入れ替えても計算結果は同じになるはず。

p11271-3.jpg

上のテーブルには (5,5)までの抵抗値がリストアップされている。例えば、(0,0)-(1,1)間の抵抗値は2/Phi=0.637Ωになる。円周率Phiがここに出てくる。

ということで、論文を見る限り、数値積分をしないといけなさそう。実際にプログラムを組んで計算してみたら、上記のテーブルに近い値が出てきた。ただ、積分部分のプログラム(シンプソン法)は精度が良くないせいか、xとyの対称性に若干の誤差があったりする。UVaの自動判定システムにもAcceptedされていない。

単純そうに見えた計算問題に大変複雑な定積分が出てくるとはびっくる。漸化式では無理かな。

でも、問題文のヒントがとても気になる。もっとうまい計算法はあるような言い方。
Hint: There is a surprising Dynamic Programming solution, but how do you get it to fit under the memory requirement? 🙂 .

最後に、プログラム内に使っている、計算式に関連するコードをピックアップしておく。

int x, y;  /* 計算したい (x,y) 座標 */
double alpha(double beta)
{
    double t = cos(beta);
    return log(2-t+sqrt(3+t*(t-4)));
}
double func(double beta)
{
    double a = alpha(beta);
    val = (1.0-1/exp(x*a)*cos(y*beta))/sinh(a);
    return val;
}

上のやり方では問題ないように思われるが、確信はまだない。Acceptedされていないし。ちなみに、現時点では問題を解いたひとは二人だけ、出題者本人とUVaシステムの関係者?

Comments are closed.

Post Navigation