データ構造・15パズル・Algebra

通信大学で、データ構造を専攻中なのですが、
添付した画像部分が具体的に何を意味しているのかよく分かりません。

{(Ptile, blank), (Pblank, t)}
∪{(p',t') | (p',t') ∈ b ∧ p' ∉ {Ptile, Pblank}}

この(p',t')は何を表しているんでしょうか。どうぞ宜しくお願い致します。

-----------------------------
Algebra puzzle 15
sorts tile, position, board, bool
ops
init: tile16 -> board
move: board x tile -> board
solved: board -> bool
pos: board x tile -> position
sets
tile = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,blank}
position = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,error}
board = {c ⊂ (position \ {error}) x tile |c| = 16
∧∀c = (p,t) ∈ c:
c’ ≠ c -> p‘ ≠ p ∧ t‘ ≠ t
} ∪ {error}

No.3 ベストアンサー 回答者： stomachman 回答日時： 2012/03/24 07:28

ま、ま、一応、答も書いちゃいますか。

> {(Ptile, blank), (Pblank, t)}
> ∪{(p',t') | (p',t') ∈ b ∧ p' ∉ {Ptile, Pblank}}



(p',t')は数学の書き方なら順序対<p', t'>。ANo.1で説明した「タイルと空きの配置」cの要素である<マス, タイル>を指していて、p: position, t: tileである。ここで、
　　{(p',t') | (p',t') ∈ b ∧ p' ∉ {Ptile, Pblank}}
とは、そのまま読めば、ある「タイルと空きの配置」bについて、(p',t') ∈ b かつ p'≠Ptileかつp'≠Pblank であるような(p',t')の集合、ということですね。
　PtileとPblankは何かというと、ある「タイルと空きの配置」bにおいて、特定のマスPblankとマスPtileが指定されているんです。もちろんこれは、move（指し手）においてあるタイルと空きとを入れ替える、その場所を表しているに違いありません。ですから、
　　{(p',t') | (p',t') ∈ b ∧ p' ∉ {Ptile, Pblank}}
とは、
bにおける16個の<マス, タイル>のペアの中で、PblankでもPtileでもないマスp'とそのマスにあるタイルt'のペア<p', t'>の集合
すなわち、（Pblankにある空きとPtileにあるタイルを入れ替えるという）指し手によって影響を受けない（変化しない）ペア全部の集合に他なりません。

　となると、
　　{(Ptile, blank), (Pblank, t)}
とは、タイルtと空きblankとを入れ替える指し手(move)において、moveの直前には<Ptile, t>, <Pblank, blank> (つまり、マスPtileにはタイルtがあり、マスPblankには空きがあった）のを、入れ替えた、という状態を表している。ですから、

> {(Ptile, blank), (Pblank, t)}

> ∪{(p',t') | (p',t') ∈ b ∧ p' ∉ {Ptile, Pblank}}


とは結局、

「タイルと空きの配置」bにおいて、空きがあるマスPblankと、それに隣接するマスPtile（そこにはタイルtがある）について、タイルtをマスPblankへ移動させる（従って、空きはマスPtileへ移動する）という指し手(move)を行ったあとに生じる「タイルと空きの配置」

に他なりません。

この回答へのお礼

理解出来ました！

本当に丁寧に書いて下さりありがとうございました。
また分からない時には宜しくお願い致します。

お礼日時：2012/03/24 08:22

No.2 回答者： stomachman 回答日時： 2012/03/24 07:06

ANo.1、一番肝心なとこミスプリしました。

>> board ={ c ⊂ (position\{error})×tile ∧ |c|=16 ∧ ∀c=(p,t)∃c'=(p',t'): c’ ≠ c → p‘ ≠ p ∧ t‘ ≠ t } ∪ {error}


じゃなくて、


board ={ c ⊂ (position\{error})×tile ∧ |c|=16 ∧ ∀c=(p,t)∀c'=(p',t'): c’ ≠ c → p‘ ≠ p ∧ t‘ ≠ t } ∪ {error}

です。

No.1 回答者： stomachman 回答日時： 2012/03/24 07:01

何かの高級プログラミング言語で書いてあるようで（何語ですか？もしかして「Algebra」という言語なんでしょうか。

知らんけど。）、数学の表記としては「？」な部分も散見されます。が、ともあれ、

> Algebra puzzle 15

「15パズル」は大昔からあるけど今でもポピュラー。1～15の番号が付いた15個のタイルと空きひとつをボード上に4×4マスに並べておいて、空きに隣接しているマスにあるタイルを空きと交換する、という操作を繰り返して、1～15までのタイルが所定の配置になるようにする。ご質問では、ボード上のマスにも1～16の番号を付けてあるんですね。

> sorts tile, position, board, bool

分からんが、これらが順序集合だ、ということを言っているのかもしれないな。だとすると、15パズルにおいてはまるきりどうでもいい話ですね。


> ops

知らんけど、以下関数の定義域と値域の話が来ますね。関数は実装を見なくちゃ正確なことは言えないわけですが、15パズルを解くためのプログラムだ、ということと名称から、何をする関数なのか見当がつきます。


> init: tile16 -> board

initは tile16からboardへの関数である。boardは「タイルと空きの配置」の集合ですね。この関数は、ある「タイルと空きの配置」、つまり解くべき問題をセットする関数なのでしょう。tile16が何の事かは分かりません。

> move: board x tile -> board

数学の記号としては"x"じゃなくて"×"であるべきでしょう。move（日本語なら「指し手」）はboardとtileからboardへの関数である。ある「タイルと空きの配置」において、「どのタイル」を空きと交換するか、を指定すると、(もし可能なら）次の「タイルと空きの配置」が得られる関数。もちろん、指定したタイルが空きに隣接していなければダメで、だからboardにはダメを表すerrorという要素が含まれている。


> solved: board -> bool

solvedはboardからbool（真偽値）への関数である。これは「解けた」ということを表す関数ですね。


> pos: board x tile -> position

posはboardとtileからpositionへの関数。positionはボード上のマスですね。ある「タイルと空きの配置」において、あるタイルがどのマスにあるか、を答えてくれる関数。


> sets

ここからは集合の定義ですな。


> tile = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,blank}

1～15までの番号が付いたタイルと、空きひとつ。空きもタイルの一種と考えるわけですね。


> position = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,error}

ボード上の1～16までのマスの集合ですが、「error」というのも入れてありますね。（何に使うんだろ？）


> board = {c ⊂ (position \ {error}) x tile |c| = 16

> ∧∀c = (p,t) ∈ c:

> c’ ≠ c -> p‘ ≠ p ∧ t‘ ≠ t

> } ∪ {error}

　ここはいろいろ変です。もう、かなりおかしいです。そこで、15パズルの「タイルと空きの配置」を表すためにはどうあればいいか、ということから逆に正しい記述を再構成してみると、おそらくこうでしょう：
　boardという集合は、「集合positionから要素errorを除いたものとtileとの直積集合の部分集合」c（すなわち「集合positionから要素errorを除いたものの要素とtileの要素との対」を集めた集合c）の集合に、要素errorを加えた集合である。ただし、cの要素の個数は16であり、どのc（c=(p,t)とする）についても、c'（c'=(p',t')とする）が存在して、c'≠cならばp‘ ≠ p ∧ t‘ ≠ t である。
　つまり、
　　board ={ c : c ⊂ (position\{error})×tile ∧ |c|=16 ∧ ∀c=(p,t)∃c'=(p',t'): c’ ≠ c → p‘ ≠ p ∧ t‘ ≠ t } ∪ {error}
でしょ。どういう意味かというと、boardはボード上のタイルと空きの配置cのあらゆるものを集めたもの、およびerrorから成る集合である。さて、boardの要素である「タイルと空きの配置」cは<マス, そのマスにあるタイル>という対の集合である。ただし、cは、16個のマス全部について、また（空きを含めた)16個のタイル全部についての対を含んでいる。つまり、マスもタイルも重複してはダメ(これを表すのがc’ ≠ c → p‘ ≠ p ∧ t‘ ≠ t）、抜けていても駄目（|c|=16）。

　添付写真にあるのは、どのマスが空きに隣接しているか（つまりどのタイルが動かせるか）という判定をやる部分ですね。

この回答へのお礼

stomachmanさん、

早速のお返事ありがとうございます！
とても詳しく書いてくださったお陰で、理解してきました。

あと一つ気になるのですが、画像の3行目、
∪{(p',t') | (p',t') ∈ b ∧ p' ∉ {Ptile, Pblank}} にある、

p' ∉ {Ptile, Pblank}

で　∉　となる点がよく分かりません。
度々申し訳ありませんが、どうぞ宜しくお願い致します。

お礼日時：2012/03/24 08:06