creatio ex nihilo

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

[Profile ทั้งหมด]

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




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

 

stable marriage Theorem

สาว ๆ n คนลิสต์อันดับหนุ่ม ๆ ในดวงใจ n คน หนุ่ม ๆ ทั้ง n คน ก็ลิสต์อันดับสาว ๆ เช่นเดียวกัน David Gale กับ Lloyd Shapley นักคณิตศาสตร์เศรษฐศาสตร์ชาวอเมริกัน บอกเราว่าสามารถสร้างคู่ที่สมดุล (stable) สำหรับทุกคนได้เสมอ คู่ที่สมดุลหมายถึงคู่ที่ไม่มีคู่ใดแตกจากคู่ปัจจุบันเพื่อไปสร้างคู่ใหม่



แนวคิดเรียบง่ายครับ สาว W หมายปองหนุ่ม M ถ้าหนุ่ม M ยังไม่มีคู่ ก็จับคู่ (M,W) เข้าด้วยกัน แต่ถ้าหนุ่ม M มีคู่อยู่แล้วคือ (M,W') ก็ให้ดูว่า M ปรารถนาสาวใดมากกว่ากัน W หรือ W' ถ้าเขาอยากเป็นคู่กับ W มากกว่า ก็จับคู่ (M,W) สำหรับ W' ต้องขีดฆ่าชื่อ M ออกจากลิสต์ แต่ถ้าเขาอยากจับคู่กับ W' มากกว่า ก็คงคู่ (M,W') ไว้ดังเดิม ส่วน W ก็ต้องขีดฆ่าชื่อ M ออกจากลิสต์



ตัวอย่าง ชาย 4 หญิง 4


จากตารางนี้เห็นชัดว่า (M1,W1), (M2,W2), (M3,W3), (M4,W4) เป็นคู่ที่ไม่เสถียร คู่ที่สมดุล หรือเสถียรจากตัวอย่างนี้คือ (M1,W2), (M2,W1), (M3,W4), (M4,W3) คงเป็นโชคร้ายของคู่ (M3,W4) ทั้ง 2 คนไม่ค่อยชอบกัน แต่ก็หมดตัวเลือกอื่น ๆ แล้ว










 

Create Date : 23 ธันวาคม 2550    
Last Update : 23 ธันวาคม 2550 23:06:38 น.
Counter : 1108 Pageviews.  

cantor's Uncountability


Georg Ferdinand Ludwig Philipp Cantor
(March 3, 1845 – January 6, 1918)



มีลำดับของ 0 กับ 1 อยู่นับอนันต์

พิสูจน์
1. มีลำดับของ 0 กับ 1 อยู่จำกัดลำดับ
2. ให้ S1, S2, S3, ... คือลิสต์ของลำดับ และเขียน Si(j) แทนสมาชิกตัวที่ j ของลำดับ Si



3. ให้ S คือ complement ของลำดับเส้นทะแยง Si(i) นั่นคือ S(i) = 1 - Si(i)



4. สำหรับทุกค่า i เราได้ S(i) แตกต่างจาก Si(i)
5. ดังนั้น S ไม่เป็นสมาชิกของ {S1, S2, S3, ... }
6. ข้อ 5 ขัดแย้งกับข้อ 1 # quod erat demonstrandum












 

Create Date : 20 ธันวาคม 2550    
Last Update : 20 ธันวาคม 2550 14:33:21 น.
Counter : 932 Pageviews.  

hill-Climbing search



หลักการ

1. สุ่มเลือกคำตอบจากสเปซคำตอบ 1 state
2. search ดู state (คำตอบ) ที่อยู่ติดกัน ถ้าหากให้ผลตอบแทนที่ดีกว่า ก็ยึดคำตอบใหม่ ทิ้งคำตอบเก่า ถ้าคำตอบเก่าให้ผลดีกว่า ก็คงคำตอบเก่าเอาไว้ แล้วทำข้อ 2 ซ้ำ จนกว่าจะบรรลุผล

ให้สังเกตจุดที่อาจไม่บรรลุผลจากรูปคือ shoulder, local maximum (Ridges) และ flat local maximum (Plateaux)

ตัวอย่าง ปัญหา 8 Queens


ตัวเลขแสดงจำนวนคู่ของควีนที่โจมตีกันและกัน คำตอบปัจจุบัน h(n) = 17 คำตอบถัดไปที่ควรสำรวจคือเคลื่อนควีนไปยังช่องที่มีค่าคู่การโจมตีต่ำสุดคือ 12 (เคลื่อนตัวใดดี ? นิยมใช้วิธีการสุ่ม)

ตัวอย่าง กรณี local minimum


ค่า h(n) ปัจจุบันเท่ากับ 1 ส่วน h(n) ของคำตอบที่อยู่ติดกันไม่มีตัวใดน้อยกว่า 1

ถ้าความน่าจะเป็นในการทำงานล้มเหลวจากวิธีการนี้เท่ากับ PF หากเราลองซ้ำแล้วซ้ำอีก k ครั้ง ความน่าจะเป็นที่ล้มเหลวทุกครั้งเท่ากับ PFk นั่นคือความน่าจะเป็นที่จะสำเร็จเท่ากับ PS = 1-PFk เมื่อ k มีค่ามากขึ้น โอกาสสำเร็จย่อมมากขึ้น เรียก Random-restart hill-climbing









 

Create Date : 20 ธันวาคม 2550    
Last Update : 20 ธันวาคม 2550 13:45:09 น.
Counter : 2174 Pageviews.  

local search

Keywords (สรุปจาก AIMA p.110-p.111)
• the path to the goal is irrelevant
• applications e.g.
— IC design
— factory-floor layout
— job-shop scheduling
— automatic programming
— telecommunications network optimization
— vehicle routing
— portfolio management
• operate using a single current state & generally move only to neighbors of that state
• use very little memory
• can often find reasonable solutions in large or infinite state space
• are useful for solving pure optimization problems



พิจารณา state space landscape มี 2 ส่วนคือ location (กำหนดโดย state) และ elevation (กำหนดโดย heuristic cost function หรือ objective function) ถ้า elevation ถูกกำหนดโดย cost เป้าหมายของเราคือเลือกจุดต่ำสุด แต่ถ้า elevation ถูกกำหนดโดย objective function เป้าหมายของเราคือเลือกจุดสูงสุด

ตัวอย่าง 4 Queens Problem
เรียง Q 4 ตัวบนกระดาน 4 x 4 เพื่อไม่ให้โจมตีซึ่งกันและกัน


ตัวอย่าง Travelling Salesman Problem
เส้นทางวน loop ที่ cost ต่ำสุด

‣ สลับ 2 edges ของ complete tour








 

Create Date : 17 ธันวาคม 2550    
Last Update : 17 ธันวาคม 2550 11:51:48 น.
Counter : 1154 Pageviews.  

informed search № 2

(ต่อจาก № 1)

Heuristic Function
heuristic คือข้อมูลช่วยในการเดาขั้นต่อไปสำหรับแก้ปัญหา

ตัวอย่าง 1


h1(n) = จำนวนหมายเลขที่อยู่ผิดที่ = 6
h2(n) = ผลรวม Manhattan distance = 4+0+3+3+1+0+2+1 = 14

ตัวอย่าง 2 ใช้ A*
f(n) = g(n) + h(n)
เมื่อ h(n) = จำนวนแผ่นสีที่อยู่ผิดที่


ตัวอย่าง 3 Robot Navigation
f(n) = g(n) + h(n)
เมื่อ h(n) = การกระจัดจาก n ถึง goal


‣ ถ้า h2(n) ≥ h1(n) สำหรับทุก n เราเรียก h2(n) dominates h1(n) ใช้ h2(n) ในการ search ดีกว่า h1(n)

‣ h(n) = max{hi(n)}


Relaxed Problems
• Relaxed problem = ปัญหาที่มีข้อบังคับน้อย
• Relaxed problem → Admissible heuristic

จากตัวอย่าง 1มีข้อบังคับ
‣ ช่อง A เลื่อนไปยังช่อง B ได้ก็ต่อเมื่อ A อยู่ติดกับ B และ B เป็นช่องว่าง

Relaxed version 1
‣ A เลื่อนไปยัง B เมื่อ B ว่าง → สามารถใช้ h1(n)
Relaxed version 2
‣ A เลื่อนไปยัง B เมื่อ A อยู่ติดกับ B → สามารถใช้ h2(n)

º Iterative Deepening A*
• Each iteration is depth-first with cutoff on the value of f(n) of expanded nodes

ตัวอย่าง cutoff = 4
f(n) = g(n) + h(n)
เมื่อ h(n) = จำนวนแผ่นสีที่อยู่ผิดที่

STEP 1

STEP 2

STEP 3

STEP 4

STEP 5


• เพิ่ม cutoff = 5









 

Create Date : 13 ธันวาคม 2550    
Last Update : 5 มกราคม 2551 21:16:22 น.
Counter : 1260 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.