creatio ex nihilo

ศล
Location :
กรุงเทพ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 85 คน [?]




Group Blog
 
All Blogs
 
Friends' blogs
[Add ศล's blog to your web]
Links
 

 

schrödinger's Cat

วันที่ 7 เดือนมิถุนายน ปี 1935 แอร์วิน ชเรอดิงเง่อร์ (Erwin Schroedinger) เขียนจดหมายแสดงความยินดีถึงอัลเบิร์ต ไอน์สไตน์ (Albert Einstein) เกี่ยวกับการตีความปัญหาสำคัญประการหนึ่งในกลศาสตร์ควอนตัม (ต่อมาเป็นที่รู้จักกันในนาม EPR) หลังจากนั้นไม่นาน (พฤศจิกายน 1935) เขาก็ตีพิมพ์บทความปัญหาขัดแย้งที่สำคัญอีกอันของทฤษฎีควอนตัม




ใส่แมว อะตอมกัมมันตรังสี (radioactive atom) เครื่องตรวจกัมมันตรังสี (ตรวจจับอนุภาคเอลฟ่า-alpha particle) ขวดยาพิษ และกลไกอีกเล็กน้อยลงในกล่องเดียวกัน ถ้านิวเคลียสอะตอมกัมมันตรังสีสลายตัว จะปล่อยอนุภาคเอลฟ่าออกมา ถ้าเครื่องตรวจกัมมันตรังสี ตรวจพบอนุภาคเอลฟ่า จะเปิดกลไกทุบขวดยาพิษให้แตก ถ้าขวดยาพิษแตก แมวตาย (100%) ถ้านิวเคลียสของอะตอมกัมมันตรังสีไม่สลายตัว แมวยังมีชีวิตรอด (100%)

การวางเงื่อนไขปัญหา paradox อันนี้ของชเรอดิงเง่อร์นับว่าหลักแหลมทีเดียว เพราะเชื่อมโยงกันทั้งโลกของควอนตัมและโลกของฟิสิกส์ยุคเก่า ก่อนที่ผู้สังเกตจะเปิดกล่อง ชะตากรรมของเจ้าแมวน้อยขึ้นอยู่กับฟังก์ชั่นคลื่น (wave function) ของอะตอม ซึ่งมีทั้ง 2 สถานะ ณ เวลาหนึ่ง ๆ คือสถานะสลายตัว และไม่สลายตัว ดังนั้นชเรอดิงเง่อร์จึงบอกกับเราว่า เจ้าแมวน้อยนี้ก็จะมี 2 สถานะเช่นเดียวกัน (superposition) มันทั้งเป็นแมวตายและไม่ตายในเวลาเดียวกัน จนกระทั่งผู้สังเกตการณ์เปิดกล่อง เพื่อสังเกตแมวตัวนั้น ขณะเดียวกันก็เข้าไปแทรกแซงฟังก์ชั่นคลื่นของมัน เขาจึงสังเกตเห็นสถานะใดสถานะหนึ่ง ระหว่างศพแมวกับแมวหงุดหงิด (เพราะจับมันมาขัง) Curiosity may have killed a whole cat, but Schroedinger only killed half...







 

Create Date : 10 ธันวาคม 2550    
Last Update : 29 เมษายน 2551 2:05:07 น.
Counter : 1332 Pageviews.  

นินจาพูดเท็จ↔นินจาพูดจริง

ฮาคุ "นินจาพูดจริง"
นินจา "พี่ฮาคุพูดโกหก"




• นินจาพูดจริง → ฮาคุพูดโกหก → นินจาพูดไม่จริง หรือ นินจาโกหก
• นินจาพูดจริง → นินจาพูดโกหก
• นินจาพูดโกหก → ฮาคุพูดจริง → นินจาพูดจริง
• นินจาพูดโกหก → นินจาพูดจริง

นินจาพูดจริง ↔ นินจาพูดไม่จริง











 

Create Date : 06 ธันวาคม 2550    
Last Update : 7 ธันวาคม 2550 13:12:15 น.
Counter : 1078 Pageviews.  

informed search № 1

f(n) = evaluation function ใช้เป็นข้อมูลช่วยสำหรับกระจาย node
         f(n) ยิ่งน้อย ยิ่งดี
h(n) = heuristic function คือ cost ของเส้นทางที่ถูกที่สุดจาก n ถึง goal

ตัวอย่าง h(n)


• ต้องการจัดรูปจากสถานะ n ให้เป็นรูป goal

h1(n) = จำนวนหมายเลขที่วางผิดตำแหน่ง
h1(n) = 6

h2(n) = ผลรวมของจำนวนครั้งต่ำสุดที่ต้องเลื่อนแต่ละเลข
h2(n) = 3 + 1 + 3 + 0 + 2 + 1 + 0 + 3 = 13

Robot Navigation


• ต้องการเดินจากสีแดงไปยังสีเขียว มีช่องแรเงาคือสิ่งกีดขวาง

h(n) = จำนวนช่องที่ต้องเดินจากช่องที่ n ไปจนถึงสีเขียว แสดงดังรูป



º Greedy Best-First Search

• f(n) = h(n)

เราต้องการเดินทางจาก Arad ไปยัง Bucharest



1. ถ้ากำหนดให้ h(n) = ระยะทางที่สั้นที่สุด (straight-line distance) จากเมือง n ถึงเมือง Bucharest สามารถสรุป h(n) ได้ดังนี้



2. กระจายเฉพาะ node ที่ f(n) ต่ำที่สุด



• การใช้ hSTRAIGHT-LINE DISTANCE เพื่อหา solution กรณีนี้ไม่ Optimal ดูได้จาก costs ที่เกิดขึ้น Arad → Sibiu → Fagaras → Bucharest = 140 + 99 + 211 = 450 ในขณะที่ costs จากเส้นทาง Arad → Sibiu → Rimnicu → Pitesti → Bucharest = 140 + 80 + 97 +101 = 418

• ถ้าเปลี่ยนโจทย์ โดยให้จุดเริ่มต้นอยู่ที่ Isai และมี Fagaras เป็นปลายทาง



hSLD แนะนำ Iasi → Neamt → Iasi → Neamt → ... (loop) ดังนั้นไม่วิธีนี้ไม่รับประกันผลสำเร็จ

• Time/ Space Complexity = O(bm)

º A* Search

• f(n) = g(n) + h(n)
         เมื่อ g(n) = cost รวมจากจุดเริ่มต้นจนถึง n



จากตัวอย่างหาเส้นทาง Arad → Bucharest หลังจากเมือง Sibiu ลำพัง h SLD แนะนำให้เลือก Fagaras เพราะ h(Fagaras) = 176 ซึ่งเป็นค่าต่ำสุด แต่เมื่อนำ g(n) มาคิดร่วม เราเลือก f(Rimnicu) = g(Rimnicu) + h(Rimnicu) = 220+193 = 413 ซึ่งต่ำกว่า f(Fagaras) = g(Fagaras) + h(Fagaras) = 239 + 176 = 415 สุดท้ายได้เส้นทาง Arad → Sibiu → Rimnicu → Pitesti → Bucharest ซึ่งรวม cost = 418 (ถูกที่สุด)



ตัวอย่าง จาก Robot Navigation เราเขียน f(n) = g(n) + h(n) ได้ดังนี้




»•« Admissible Heuristic
กำหนดให้ h*(n) = cost of optimal path จาก n ถึง goal
เราเรียก h(n) ว่า admissible ถ้า 0 ≤ h(n) ≤ h*(n)

• ถ้า h(n) มีคุณสมบัติ admissible แล้ว A* ให้คำตอบเป็น Optimal

พิสูจน์
สมมติมีเป้าหมาย 2 ตัวคือ G กับ G2 โดยที่ G เป็น optimal goal และกำหนดให้ C* คือ cost ของเส้นทางไปสู่ G (หรือ C* = f(G)) เราได้ความสัมพันธ์



‣ f(G2) = g(G2) เพราะ h(G2) = 0
‣ f(G) = g(G) = C* เพราะ h(G) = 0
‣ g(G2) > g(G) เพราะ G เป็น optimal goal
‣ f(G2) > f(G) เพราะ G เป็น optimal goal

ถ้า n เป็น node บน optimal path

‣ h(n) ≤ h*(n) เพราะ h(n) มีลักษณะ admissible
‣ g(n) + h(n) ≤ g(n) + h*(n)
‣ f(n) ≤ C*
‣ f(n) < f(G2) #

ลองพิจารณาตัวอย่างต่อไปนี้



search ด้วย A*



เหตุใด A* จึงไม่ให้คำตอบที่ Optimal ทั้ง ๆ ที่ h(n) มีคุณสมบัติ admissible

»•« Monotonic (Consistent Heuristics)



f(n) เป็น monotonic เมื่อ f(n) ≤ f(n') หรือ h(n) - h(n') ≤ c(n,a,n')

• ถ้า f(n) เป็น monotonic ค่าของ f(n) ตลอดเส้นทางจะไม่ลดลง

f(n') = g(n') + h(n') = g(n) + c(n,a,n') + h(n') ≥ g(n) + h(n) = f(n)

• เราอาจพิสูจน์ว่า A* ให้คำตอบเป็น optimal เมื่อ h(n) มีลักษณะ admissible และ consistent ได้โดยใช้การพิสูจน์ด้วยข้อขัดแย้ง

‣ f(G) = C*
‣ f(G2) > C*
‣ ถ้า A* ให้ผลลัพธ์คือ G2 เมื่อ n เป็น node บน optimal path สู่ G ดังนั้น f(G2) ≤ f(n)
‣ จากคุณสมบัติ monotone เราได้ C* ≥ f(n)
‣ ดังนั้น C* ≥ f(G2) เกิดข้อขัดแย้ง #


A* Search with a Consistent Heuristic Function



A* กระจาย node โดยเพิ่มค่า f(n) รูปนี้แสดงให้เห็น 3 วง คือ f=380, f=400 และ f=420 โดย nodes ที่อยู่ใน contour มี cost น้อยกว่าหรือเท่ากับ f ของเส้น contour เช่นทุก nodes ที่อยู่ในเส้น f=400 มี f(n) ≤ 400 สำหรับกรณี Uniform-cost Search (A* ที่ใช้ h(n) = 0) เส้น contour จะเป็นวงกลมโดยมีจุดเริ่มต้นคือจุดศูนย์กลาง


คุณสมบัติของ A*
• Completeness ?
‣ แน่นอน ถ้าไม่มี nodes จำนวนอนันต์ที่ f(n) ≤ f(G)

• Optimal Solution ?
‣ แน่นอน เพราะ
         A* กระจายทุก nodes ที่ f(n) < C*
         A* กระจายบาง nodes ที่ f(n) = C*
         A* ไม่กระจาย nodes ที่ f(n) > C*

• Time/ Space Complexity ?
‣ เพิ่มขึ้นอย่างเป็น exponential (ประมาณเท่ากับ BFS); bd
‣ เก็บทุก nodes ลงหน่วยความจำ
ยกเว้น |h(n) - h*(n)| ≤ O(log(h*(n))) เมื่อ h*(n) คือ cost ที่แท้จริงจาก n ถึง goal เป็นเงื่อนไขสำหรับ subexponential growth






(มีต่อ № 2)




 

Create Date : 06 ธันวาคม 2550    
Last Update : 6 ธันวาคม 2550 17:25:33 น.
Counter : 2003 Pageviews.  

big O

กำหนดให้ f, T : N → R+ เป็นฟังก์ชั่นจากจำนวนนับถึงจำนวนจริงบวก เราเขียน T(n) = O(f(n)) เมื่อมีจำนวนจริง c และจำนวนเต็ม n0 ซึ่งทำให้เงื่อนไข T(n) ≤ cf(n) เป็นจริง สำหรับทุก n > n0 [ข้อควรระวัง เครื่องหมาย "=" ประโยค T(n) = O(f(n)) ไม่ใช่เครื่องหมาย "เท่ากับ" แต่เป็นการนิยาม T(n) = O(f(n))]

เช่น T(n) = 6n3 + 2n2 + 20n + 45 พหุนามดีกรี 3 ดังนั้น T(n) = O(n3)

• เรานิยมใช้ big-O ในการวัดประสิทธิภาพของอัลกอลิทึม
• ประสิทธิภาพของอัลกอลิทึม (ที่ทำงานได้สำเร็จเท่า ๆ กัน) นิยมดูจาก เวลา และ หน่วยความจำ ที่ใช้ในการทำงานให้ประสบผลสำเร็จ ยิ่งใช้เวลาและหน่วยความจำน้อยเท่าไร ยิ่งเป็นอัลกอลิทึมที่ดี
• มี 2 วิธีในการเปรียบเทียบอัลกอลิทึม
     ก. benchmarking
     ข. analysis of algorithms (asymptotic analysis, big-O)

• big-O เรียงจากประสิทธิภาพสูงสุดไปต่ำสุดได้ดังนี้

O(1), O(log n), O(n), O(n log n), O(n2), O(nK), O(Kn), O(n!)

• วิธีหา big-O อย่างง่ายคือกระจายพหุนาม T(n) แล้วเลือกพจน์ใหญ่สุด
• จากกราฟ เมื่อ n มีค่ามาก เราควรเลือกอัลกอลิทึมที่ O(n) มีประสิทธิภาพสูง หรือ O(n) มีค่าต่ำ









 

Create Date : 04 ธันวาคม 2550    
Last Update : 4 ธันวาคม 2550 20:34:17 น.
Counter : 1770 Pageviews.  

uninformed search

uniformed search = blind search



b = maximum branching factor (no. of children)
d = depth of the shallowest goal node
m = maximum length of any path in the state space

ตัวอย่าง


b = 3, d = 1, m = 2

Uninformed Search Strategies:
» Breadth-First Search
» Uniform-Cost Search
» Depth-First Search
» Depth-Limited Search
» Iterative Deepening Depth-First Search

º Breadth-First Search



Completeness ?
» แน่นอน (ยกเว้น เจอ node ที่มีลูกเป็นอนันต์)

Optimal Solution ?
» ไม่แน่ (ยกเว้น step costs ทุก edge เท่ากัน)

Time Complexity ?
» จำนวน node ทั้งหมดที่ต้องสร้าง (สูงสุดที่เป็นไปได้) x เวลาสร้าง 1 node



TBFS = (b + b2 + b3 + ... + bd + bd+1 - b) x T1NODE ~ O(bd+1)

Space Complexity ?
» Space Complexity = Time Complexity

º Uniform-Cost Search
• Uniform-Cost = Lowest-Cost-First Search
• ลำดับ node ใน frontier จาก costs ต่ำสุด
• ถ้า step costs เท่ากันทั้งหมด: UFS = BFS

Completeness ?
» แน่นอน ตราบเท่าที่ทุก step costs ≥ ε (จำนวนบวกน้อยที่สุด)

Optimal Solution ?
» 100% (ตราบเท่ามันที่ทำงานสำเร็จ)

Time/ Space Complexity ?
» C* = cost of the optimal solution



เมื่อสมมติให้แต่ละ action (หรือ step) มี costs อย่างต่ำเท่ากับ ε
uniform-cost complexity ~ O(b1+C*)

ตัวอย่างปัญหา UCS
• Completeness ? อาจไปไม่ถึงฝั่ง



• Time/ Space Complexity อาจสูงมากกว่าจะถึงฝั่ง (พื้นที่แรเงาคือ cost contours)



º Depth-First Search



Completeness ?
» ไม่แน่ อาจเจอแบบนี้



Optimal Solution ?
» ไม่แน่ เช่นกรณี C กับ J เป็น goal nodes ทั้งคู่ แต่ DFS หยุดที่ J



Time Complexity ?
» O(bm); นานมาก ถ้า m > d มาก ๆ



Space Complexity ?
» O(bm); เนื้อที่มากสุดที่ DFS ต้องการเก็บ node คือ bm+1

• ถ้าเราประหยัดเนื้อที่หน่วยความจำโดยบันทึก explored node ที่เป็น successor เพียง 1 node เรียก Backtracking Search มี Space Complexity ~ O(m)

º Depth-Limited Search
• คือ DFS ที่จำกัด depth = l

Completeness ?
» ไม่สำเร็จแน่ ๆ ถ้า l < d

Optimal Solution ?
» เหมือน DFS (ถ้าสำเร็จ)

Time Complexity ?
» O(bl)

Space Complexity ?
» O(bl)

º Iterative Deepening Depth-First Search
• คือการวนทำ DLS ตั้งแต่ l = 0...∞ หรือทำสำเร็จ

ตัวอย่าง IDS
l = 1


l = 2


l = 3


Completeness/ Optimal Solution ?
» เหมือน BFS

Time Complexity ?
» O(bd)

Space Complexity ?
» O(bd)

º Bi-directional Search
• search พร้อม ๆ กันทั้งจาก start และ จาก goal หยุดเมื่อพบกันที่กึ่งกลาง



Time/ Space Complexity ?
» O(bd/2) จึงทำให้เกิดข้อได้เปรียบเพราะ 2bd/2 << bd


เราต้องตรวจจับการซ้ำสถานะ (Repeated States) เพื่อป้องกันการทำงานเพิ่มโดยไม่จำเป็น

ตัวอย่าง Repeated State


ตัวอย่าง Repeated State
สำหรับ BFS เราไม่จำเป็นต้องกระจาย node ที่วงกลมเอาไว้ (เพราะอะไร ?)










 

Create Date : 04 ธันวาคม 2550    
Last Update : 5 มกราคม 2551 18:13:01 น.
Counter : 2049 Pageviews.  

1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  
 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.