3

私は数学が苦手なので、これを理解することはできません。画像には、隣接するk個のピクセルの組み合わせがいくつありますか。画像内の合計n*n個のピクセルのうちk個のピクセルの組み合わせ。ただし、2からn * nまでの各kについて、隣接する必要があるという制限があります。推論しているセット内の多くの要素を考慮に入れなければならないプログラムのkのすべての値の合計が必要です。

ネイバーは4接続されており、ラップアラウンドしません。

4

3 に答える 3

2

サイズkのピクセルのブロブ（ここに参照）の個別の形状の数を取得すると、次の2つになります。

  • このブロブを画像上にいくつの方法で配置できますか？
  • （対称性のために）二重に数えないように、これらのうちいくつが同じですか？

正確な答えを得るのは膨大な計算作業です（k=56で10^30以上の異なる形状を見ています。k=10,000の場合を想像してください）が、 kの最初の50個の値。

（注：ウィキペディアの記事の参照は、A_kの定義との重複を処理します。）

于 2010-07-08T19:31:02.477 に答える
2

マルコフウォークにマッピングできる問題に取り組んでいるようです。

私があなたの質問を理解しているなら、あなたは次のように長さkのパスを数えようとしています：

Start          (end)-> any pixel after visiting k neighbours
*     - - - - -*
|     |
|     |
- - - -

チェス盤に似た構造で、垂直方向と水平方向の隣人だけを接続したい。

パスを自己回避する必要があると思います。つまり、ピクセルが1回の歩行で2回トラバースされないようにする必要があります（ループがないことを意味します）。この状態は、SAW（自己回避歩行）と呼ばれる古典的な問題につながります。

さて、今悪いニュース：問題は未解決です！まだ誰もそれを解決していません。

ここでは、54ページ（または16ページ）から始まる問題の概要を見つけることができます。ドキュメント内でページ番号が繰り返されているため、カウントが混乱します。しかし、論文全体は非常に興味深く、読みやすいです。数学的背景、歴史的な逸話、マルコフ連鎖の科学的重要性をいくつかのスライドで説明しています。

これが問題を回避するのに役立つことを願っています。

于 2010-07-08T21:46:47.157 に答える
1

考えられるすべてのポリオミノを反復処理することを計画している場合は、長い間待っていることになると思います。ポリオミノに関するウィキペディアのサイトから、少なくともO（4.0626 ^ n）になり、おそらくO（8 ^ n）に近くなります。n = 14までに、カウントは50億を超え、intに収まらないほど大きくなります。時間n=30までに、カウントは17千億を超え、長いものに収めることができなくなります。すべての世界政府がリソースをプールして、32 x 32のアイコンですべてのポリオミノを反復処理する場合、太陽が超新星になる前にそれを実行することはできません。

今、それはあなたがやりたいことが手に負えないという意味ではありません。あるポリオミナルで行うほとんどすべての作業は、他のポリオミナルで部分的に行われた可能性があります。動的計画法を使用して指数関数的に高速化するのは楽しい作業かもしれません。あなたが達成しようとしていることは何ですか？

于 2010-07-08T21:48:04.983 に答える