樹莓派、樹莓派之學習、樹莓派之教育

勇闖新世界︰ 《 pyDatalog 》 導引《八下》

假使我們換個『觀點』來考察『HASHTAG**』的問題，也許能體會同一『抽象關係』可以擁有『眾多詮釋』，或將可以『觸類旁通』的吧。

PyCon 2013 Coding Challenge Final

在新的『觀點』下，我們將『所有』由『HAAHS*T*G』之『字串』依據合法移動產生的『字串』構成一個『集合』。由於『九宮格』最多不超過 9! 的『排列數』，所以這個『字串集合』也是有限的。在新的『詮釋』裡，那些『字串集合』稱之為『地名集合』，如此所謂的『合法移動』 valid movement ，就是連接兩個『可通達地』之間的『交通網』 。雖說此『交通網』是有限的，然而用著之前

《勇闖新世界︰ 《 pyDatalog 》 導引《七》》文本中所講之

『台北捷運網』的『連接』述詞來定義︰

連接( □, ○) 代表 □ 捷運站，僅經過 □ 站，直通 ○ 捷運站，方向是 □ → ○。

，顯然是有些不切實際的哩！因此我們用著『有車』── 兩地間有『 * 』 ── 這樣的述詞來『捕捉』這個『交通網』的『性質』︰

有車(X地, N1月台, N2月台)  <=  (X地[N1月台] == ‘*’)
有車(X地, N1月台, N2月台)  <=  (X地[N2月台] == ‘*’)

於是『坐上車』者，或將能由此地『直達』彼地，或者尋路『能通 』另一處的 吧！如是把 Pcarbonn 先生的程式『再譯』如下︰

 

from pyDatalog import pyDatalog, pyEngine
import time

pyDatalog.create_terms('有車, 直達,能通,X地,Y地,N月台,N1月台,N2月台')
pyDatalog.create_terms('X1,X2,X3,X4,X5,X6,X7,X8,X9')
pyDatalog.create_terms('Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9')
pyDatalog.create_terms('P1月台,P2月台')

# X地在 N1月台 或 N2月台處有一顆星 "*"
有車(X地,N1月台,N2月台) <= (X地[N1月台]=='*')
有車(X地,N1月台,N2月台) <= (X地[N2月台]=='*')

# 可能的直達法 1<->2, 1<->4, ... 
X處 = (X1,X2,X3,X4,X5,X6,X7,X8,X9) # short hand
直達(X處, 1, 2, Y地) <= 有車(X處, 0, 1) & (Y地 == (X2,X1,X3,X4,X5,X6,X7,X8,X9))
直達(X處, 1, 4, Y地) <= 有車(X處, 0, 3) & (Y地 == (X4,X2,X3,X1,X5,X6,X7,X8,X9))

直達(X處, 2, 3, Y地) <= 有車(X處, 1, 2) & (Y地 == (X1,X3,X2,X4,X5,X6,X7,X8,X9))
直達(X處, 2, 5, Y地) <= 有車(X處, 1, 4) & (Y地 == (X1,X5,X3,X4,X2,X6,X7,X8,X9))

直達(X處, 3, 6, Y地) <= 有車(X處, 2, 5) & (Y地 == (X1,X2,X6,X4,X5,X3,X7,X8,X9))

直達(X處, 4, 5, Y地) <= 有車(X處, 3, 4) & (Y地 == (X1,X2,X3,X5,X4,X6,X7,X8,X9))
直達(X處, 4, 7, Y地) <= 有車(X處, 3, 6) & (Y地 == (X1,X2,X3,X7,X5,X6,X4,X8,X9))

直達(X處, 5, 6, Y地) <= 有車(X處, 4, 5) & (Y地 == (X1,X2,X3,X4,X6,X5,X7,X8,X9))
直達(X處, 5, 8, Y地) <= 有車(X處, 4, 7) & (Y地 == (X1,X2,X3,X4,X8,X6,X7,X5,X9))

直達(X處, 6, 9, Y地) <= 有車(X處, 5, 8) & (Y地 == (X1,X2,X3,X4,X5,X9,X7,X8,X6))

直達(X處, 7, 8, Y地) <= 有車(X處, 6, 7) & (Y地 == (X1,X2,X3,X4,X5,X6,X8,X7,X9))
直達(X處, 8, 9, Y地) <= 有車(X處, 7, 8) & (Y地 == (X1,X2,X3,X4,X5,X6,X7,X9,X8))

# 能通之法或 X地 到 Y地 直達， 
# 或先經由若干 Z處，再由 Z處 往 Y地 直達。
Z處 = (Z1,Z2,Z3,Z4,Z5,Z6,Z7,Z8,Z9)
(能通[X地, Y地] == N月台) <= 直達(X地, P1月台, P2月台, Y地) & (N月台 == [(P1月台, P2月台)])
(能通[X地, Y地] == N月台) <= (能通[X地, Z處] == N1月台) & 直達(Z處, P1月台, P2月台, Y地) & (N月台 == N1月台 + [(P1月台, P2月台)])

# ?? 到底要花多少時間計算！！
pyDatalog.create_terms('所有路徑, P路徑甲, P路徑乙')
所有路徑(X地, Y地, P路徑甲) <= 直達(X地, P1月台, P2月台, Y地) & (P路徑甲 == [(P1月台, P2月台)])

所有路徑(X地, Y地, P路徑甲) <= 所有路徑(X地, Z處, P路徑乙) & 直達(Z處, P1月台, P2月台, Y地) & (X地 != Y地) & (P路徑甲 == P路徑乙 + [(P1月台, P2月台)])

start_time = time.time()

print((所有路徑[list('HAAHS*T*G'), list('HASHTAG**')] == N月台) >= N月台)
# prints 5-6,2-5,2-3,3-6,5-6,7-8,5-8,8-9,7-8,
print("Computed in %f seconds" % (time.time() - start_time))

 

看來想要搭上車，還得先『計算』出這車之『起』至『止』路徑中之『地名』的呢！在此我們將略為探討一下這個『演算』的性質，歸結到 Pcarbonn 先生選擇『邏輯函式』 Logic Functions 來建置的原因。因而我們將用

Y \ = \ \widehat{move_{(P_{\alpha}, \ P_{\beta})}} \ X 表達

直達(X處,  Pα月台, Pβ月台, Y地)

這個事實。可以推導出如果

Z \ = \ \widehat{move_{(P_{\alpha}, \ P_{\beta})}} \ Y \ , \ Y \ = \ \widehat{move_{(P_{\alpha}, \ P_{\beta})}} \ X ，那麼

Z \ = \ \widehat{move_{(P_{\alpha}, \ P_{\beta})}} \ \widehat{move_{(P_{\alpha}, \ P_{\beta})}} \ X \ = \ X

，這也是最小的『循環路徑』。事實上這個『交通網』有多個循環路徑，舉例說可以發生在九宮格『1, 2, 5, 4,1』、『1,2,3,6,5,4,1』、『1,2,3,6,9,8,7,4,1』……等處，只要其中一個『位置』上『有星』。因此從『此地』往『彼處』的路徑，就可能不只有『一種』走法，要是考察『多個』循環路徑之情況，我們將如何『限制』最長路徑的呢？由於一個最小的『循環路徑』 ── 比方講 ( P1, P4 )  ──，可以藉著 『1, 2, 5, 4,1』來作『表達』，那麼一個『一般路徑』可能是難以想像的『長』吧！如此『所有路徑』『演算法』，只靠著『頭尾』之『不同』── X地 != Y地 ── 可不可能『中止』計算的呢？？

在數學上『有沒有』解答是一種『存在性』的問題。『找到』一個『解答』，可以『證明』了那個『存在性』的問題有解！那要怎麼證明『無解』的呢？意味『所有』的解都『不存在』！就像證明 \sqrt{2} 不是『有理數』一般，我們必須要證明沒有一個『有理數』是 \sqrt{2} 。所以 Pcarbonn 先生選擇『邏輯函式』大概是想先『找到一個解』吧，畢竟『函式』在『定義』上，就只有『唯一值』的啊。更不要說 pyDatalog 語言『最佳化』之『推理引擎』運作方法是怎樣哩！那麼『HAAHS*T*G』裡有『兩顆星』，難到不意味著『至少有兩個 』解嘛！！