Just algorithm!

คณิตศาสตร์การหาคู่ 37% ไม่ใช่กลยุทธ์ที่ดีที่สุด!

เรื่องมันเริ่มจากหนังสือชื่อ CHANCE โดย Amir D Aczel
แนะนำสูตรการหาคู่แท้
สูตรนี้ไม่มีปัญหาอะไร ผู้แต่งก็บอกอยู่แล้วว่าเป็นสูตรสำหรับหาคู่ครองที่ดีที่สุด

สูตรนี้ง่าย ๆ บอกว่าให้คุณประมาณการจำนวนคนที่คุณสามารถคบเป็นแฟน
ให้คุณคบไปจำนวน 37% ของจำนวนเป้าหมาย โดยไม่เลือกใครเลย
แล้วจึงเลือกคนถัดไป ที่ดีกว่าคนทั้ง 37% ที่คบผ่านมา

ข้อพิสูจน์สนุกดี อ่านบทพิสูจน์ได้ที่ Blog คุณศล
นอกจากนี้ยังมีตัวเลขที่น่าสนใจคือ
ถ้าคุณคบโดยไม่เลือกใครจำนวน 37%
คุณจะมีโอกาส 37% ที่จะพบคนที่ดีที่สุด
และนอกจากนี้อีก 37% คือ คุณจะไม่ได้ใครเลย Smiley
(37% นี้คือ 1/e)

ซึ่งไอ้ 37% ที่จะไม่ได้ใครเลยมันเยอะเกินไป
เพราะกลยุทธ์นี้ ไม่ได้ให้คุณค่าของคนที่ดีรองลงมา สนใจเพียงคนที่ดีที่สุดเท่านั้น
ดังนั้นเราลองมาดูกันว่า ถ้าคุณลองเปิดโอกาสให้คนที่ดีรองลงมาด้วย
ผลจะเป็นอย่างไร Smiley

เริ่มจากจำนวนคนที่คบโดยตั้งใจว่าจะเลิกแน่นอน
ถ้าคนที่เราคบด้วยแต่ละคน เราสามารถให้คะแนนได้สูงสุด 100 คะแนน
ถ้าให้ x คือ จำนวนคนที่คบและตั้งใจว่าจะเลิก
วิธีหาคะแนนสูงสุดของคนที่เราคบแล้วเลิก คือ (x*100) / (x + 1) --- [1]

ถ้าให้ y คือ คะแนนสูงสุดจากการคบ x คน
คะแนนคาดหมายของคนถัดไปที่มีคะแนนมากกว่า y คือ (100 + y) / 2 --- [2]

สุดท้าย เราอาจโชคร้าย คนที่ดีที่สุด เราอาจเคยคบแล้วเลิกไปแล้ว
ถ้าให้ n คือ คนที่เรามีโอกาสเจอทั้งหมด
และให้ z คือ คะแนนคาดหมายของคนถัดไปที่มีคะแนนมากกว่า y
คะแนนคาดหมายของกลยุทธ์นี้คือ 
z * (1 - x / n) 

สุดท้ายเราต้องการค่า x ที่สูงที่สุดของกลยุทธ์นี้
ก็เอาสูตรด้านบนไปหา Differentiation
ถอดไป ถอดมาจะได้
n = 2x2 + 4x + 1 --- [3]

ตารางด้านล่างแสดง หากคุณคบคนได้ 100 คน
โดยเปรียบเทียบกับกลยุทธ์ 37%

กลยุทธ์ 37% หาเนื้อคู่ ไม่สนเนื้อคู่ 
จำนวนคนที่คบ
แล้วต้องเลิก [4]
 37 คน 6 คน
คิดเป็นเปอร์เซ็นต์ 37% 6%
โอกาสเจอเนื้อคู่
ที่ดีที่สุด [5]
 36.79% 16.88%
โอกาสแต่งงานกับ
คนที่ดีรองลงมา
 26.21% 77.12%
คะแนนคาดหมาย
หากไม่โสด [6]
 98.68 คะแนน 92.86 คะแนน
โอกาสเป็นโสด 37% 6%
คะแนนคาดหมาย [7] 62.17 คะแนน 87.29 คะแนน

เห็นไหมครับ กลยุทธ์แบบยอมคบคนที่ดีรองลงมา
คะแนนเป้าหมายกลับสูงกว่า
หากดูที่คะแนนคาดหมายเมื่อไม่โสด จะเห็นว่าคะแนนฉีกกันไม่ถึง 6 คะแนนดี
แต่ความเสี่ยงกลับเพิ่มขึ้นถึง 6 เท่า!

ถ้าใครสนใจกลยุทธ์นี้ คำตอบของกลยุทธ์นี้ไม่เป็นเส้นตรง
จำนวนคนที่จะคบแปรผันตามจำนวนคนทั้งหมด ตามตารางนี้ครับ

จำนวนคนที่คบได้ จำนวนคนที่คบแล้วต้องเลิก
(แล้วหาคนถัดไปที่ดีกว่า)
1-3 คน0 คน! (หมายความว่าใครมาต้องรีบคว้า)
4-11 คน1 คน (มี Puppy love ซักคน)
12-23 คน2 คน
24-39 คน3 คน
40-59 คน4 คน
60-83 คน5 คน

คงพอแค่นี้ ใครเลือกได้เกิน 20 คนจริง ๆ ก็ถือว่าเทพละ (สำหรับคนธรรมดาอย่างผม)

พอเขียนจบก็พอสรุปได้ดังนี้ครับ
  1. คนที่คบแล้วเลือกเยอะ ๆ เค้ากำลังหาคู่แท้อยู่ก็เป็นไปได้
  2. คนที่โสด คือ หาคนคบไม่ได้ หรือ หาคู่แท้ไม่เจอ
  3. จริง ๆ เรื่องพวกนี้มันก็ Common Sense ตรูจะคำนวนทำไมให้วุ่นวาย (วะ)


[1] คำนวนจากการกระจายตัวของการสุ่ม
สมมติว่ามี 4 คน คะแนนคาดหวังจากการกระจายคือ 20, 40, 60 และ 80
ดังนั้น คะแนนสูงสุด คือ 80

[2] คำนวนจากคะแนนคาดหมายที่สูงกว่า y
ถ้า y เป็น 80 คะแนนกึ่งกลางระหว่าง 80 ถึง 100 คือ 90

[3] ก็แค่ถอด Diff ต้องอธิบายด้วยหรือครับ :)
ถ้าลองถอดเองให้ n เป็น constant นะครับ เพราะไม่ต้องการหา n

[4] n = 2x2 + 4x + 1 เอามาหา Quadratic Equation
ได้ x = [-4 + sqrt(16 - 8 * (1 - n))] / 4

[5] เอามาจาก Blog คุณศลเลยครับ = (-x/100) * ln(x/100)

[6] ตอนแรกหา y = (x*100) / (x + 1)
แล้วผลลัพธ์คือ = (100 + y) / 2

[7] เอาคำตอบจากข้อ [6] มาคูณด้วยโอกาสไม่เป็นโสด




 

Create Date : 23 กรกฎาคม 2554    
Last Update : 23 กรกฎาคม 2554 0:48:48 น.
Counter : 2497 Pageviews.  

มีอะไรใหม่ใน C#5.0

2 ปีที่แล้ว ผมเพิ่งเขียนบทความเกี่ยวกับ C#4.0
ตอนนี้ C#5.0 กำลังออกมาอีกละ

ผมมีโอกาสได้ดู Video เกี่ยวกับ C#5.0 มาสักพักใหญ่
แต่คิดว่ายังไม่สายไป หลายคนยังไม่รู้
วันนี้เลยเอามาบอกกล่าวเล่ากันครับ

ก่อนอื่น Download ไฟล์ presentation ไปดูประกอบกันก่อนครับ

ก่อนอื่นย้อนเวลาคร่าว ๆ
C#1.0 คือ จุดเริ่มต้นของภาษา C แบบ Managed Code
C#2.0 หลัก ๆ ก็ Generics
C#3.0 Linq กับพรรคพวก (อ่านเพิ่มที่นี่)
C#4.0 Dynamic (อ่านเพิ่มที่นี่)

และ C#5.0 ตอนนี้ส่วนใหญ่จะเป็นเรื่อง async กับ Compiler as a services มานิดหน่อย
วันนี้เรามาดูกัน

ตัวอย่างผมเอามาจาก CTP นะครับ

สมมติคุณเขียนโปรแกรมสำหรับค้นหาหนังในปีต่าง ๆ
คุณอาจจะสร้างปุ่มมาหนึ่งปุ่ม
ปุ่มนั้นมีคำสั่งตามนี้

var first = 0;
var pageSize = 10;
while (true) {
var movies = QueryMovies(year, first, pageSize);
if (movies.Length == 0) break;
DisplayMovies(movies);
first += movies.Length;
} 
จากโค้ดก็ง่าย ๆ สั่งค้นหาหนังไปเรี่อย ๆ ทีละ 10 เรื่อง
แล้วก็แสดงออกมา
แต่ปัญหาคือ ถ้าเขียนอย่างนี้หน้าจอจะ Freeze ไม่ขยับจนกว่าจะ Download หนังเสร็จทั้งหมด

วิธีแก้ปัญหานี้ หากเป็น C#4.0 คุณอาจจะใช้ BackgroundWorker, หรือวิธีอื่น ๆ ก็แล้วแต่
คุณต้องแก้ Logic ของโค้ด จากที่อ่านง่าย ๆ ก็เป็นอ่านไม่รู้เรื่อง

C#5.0 มีวิธีแก้ง่าย ๆ แค่คำว่า async กับ await
async กับ await 2 คำนี้ใช้ด้วยกันเสมอ
async ใช้ตอนประกาศ method บอกว่า method นี้จะมีการใช้ await
ส่วน await ใช้เพื่อบอกว่า ให้รอ แต่ระหว่างรอไปทำอย่างอื่นก่อนก็ได้

โค้ดแก้ใหม่เป็นอย่างนี้

var first = 0;
var pageSize = 10;
var background = new SynchronizationContext();
while (true) {
await background.SwitchTo();
var movies = QueryMovies(year, first, pageSize);
await Application.Current.Dispatcher.SwitchTo();
if (movies.Length == 0) break;
DisplayMovies(movies);
first += movies.Length;
}

แค่เพิ่มบรรทัดที่ขีดเส้นใต้เข้าไป  กับคำว่า async ที่หัว method ไม่ต้องแก้โค้ดใด ๆ ทั้งสิ้น
await ตัวแรกบอกให้ Thread UI รอ แต่ระหว่างรอจะทำอะไรอย่างอื่นก่อนก็ได้
ดังนั้น หน้าจอ UI จะไม่ Freeze จะย่อขยาย กดอะไรต่อก็ได้ตามสบาย
background.SwitchTo เป็นการสั่งให้ย้ายไป Thread background
ดังนั้นคำสั่ง QueryMovies จะทำที่ Thread background

เมื่อ Thread background ทำคำสั่ง QueryMovies เสร็จ
ก็เจอ await ตัวที่ 2 บอกว่าให้ Thread background รอ
Thread UI ที่ก็สลับกลับมาทำต่อจากเดิม
ทำ method ชื่อ DisplayMovies เพื่อแสดงหนังบนหน้าจอ

พอ loop อีกหนึ่งรอบก็สลับเป็น Thread background ใหม่ เพื่อดึงข้อมูลหน้าถัดไป
ทำอย่างนี้ไปเรื่อย ๆ จนจบ

เห็นไหมครับหลักการไม่มีอะไรเลย
ไม่ต้องเปลี่ยนโค้ด แถมจะ Debug ก็ง่าย run เหมือนปกติ

ทีนี้ถ้าคุณอยากให้โค้ดคุณ advance มากขึ้น
ไม่ต้องไปกำหนดว่า คำสั่งไหน run background อันไหน run UI

คุณก็อาจต้องแก้ method นิดหน่อย
โดยปกติ method QueryMovies อาจมี Signature ตามนี้


Movie[] QueryMovies(int year, int start, int pageSize);

ก่อนทำอะไร มาทำความรู้จักกับ keyword async เพิ่มอีกนิดหน่อย
ถ้าประกาศ async เราสามารถคืนค่าได้ 3 แบบ

async void
async Task
และ async Task<T>

method ที่ประกาศ async void ก็คือ method ธรรมดา
เพียงแต่ใน method จะมีคำว่า await อยู่ข้างใน
คนอื่นจะมารอ method ที่ประกาศ async void ไม่ได้

async Task ก็คือ method ที่คนอื่นจะมารอได้ แต่ไม่รับค่าใด ๆ
และ async Task<T> คือ method ที่คนอื่นจะมารอรับค่า T กลับไป 

ในกรณี method QueryMovies มีการคืนค่าจึงต้องแก้เป็น


async Task<Movie[]> QueryMovies(int year, int start, int pageSize);
ส่วนเนื้อหา method QueryMovies ส่วนที่สั่ง Download ข้อมูล
Microsoft เค้าจะเตรียม Library บางส่วนที่เป็น async ไว้ให้
ซึ่งมีคำสั่งสลับ Thread ให้อยู่แล้ว

เช่น ปกติเวลา Download สั่ง

var data = client.DownloadString(new Uri(url));
ก็เปลี่ยนเป็น

var data = await client.DownloadStringTaskAsync(new Uri(url));
ส่วนการคืนค่า ก็ return เป็น Movie[] ตามปกติ ไม่ต้องแก้อะไร
.NET มันจะแปลงเป็น Task<Movie[]> ให้เอง สำหรับ method ที่เป็น async

ทีนี้การรอคำสั่ง QueryMovies ก็ง่ายขึ้นเยอะ สามารถเขียนเป็นแบบนี้ได้

var first = 0;
var pageSize = 10;
while (true) {
var movies = await QueryMovies(year, first, pageSize);
if (movies.Length == 0) break;
DisplayMovies(movies);
first += movies.Length;
}
เขียนแทบจะเหมือนเดิม เติมแค่คำว่า await เข้าไป
มันง่ายจริง ๆ จนอยากให้มันออก C#5.0 มาเดี๋ยวนี้เลย Smiley

ส่วน Compiler as a Service
ก็ประมาณว่าเค้ายกเครื่อง C# Compiler ใหม่ทั้งหมด
แต่ก่อน Compiler ทำงานอย่างไงเราไม่สนใจ
แต่หลังจากนี้ เราสามารถถอดส่วนประกอบของโค้ดที่จะ Compile ได้ทั้งหมด

ผมคิดว่า ต่อจากนี้เราอาจได้เห็นอะไรแปลก ๆ มากขึ้น
ประมาณว่า สามารถ Log Exception ประเภทที่เก็บตัวแปรจาก method ได้
สร้าง Unit Test แบบ Full Coverage ได้
ทำการ Analyze Code และทำการ Refactor ให้อัตโนมัติ Smiley

จบครับ Smiley




 

Create Date : 16 มกราคม 2554    
Last Update : 16 มกราคม 2554 3:55:26 น.
Counter : 2608 Pageviews.  

คณิตศาสตร์ กับการกระจายงานผลิต

ผมเคยเห็นคำถามมากมายว่าคณิตศาสตร์เอามาใช้ประโยชน์ได้อย่างไร
จริง ๆ มันก็แล้วแต่สายงานที่ทำครับ
อย่างผม งานเกี่ยวกับคอมพิวเตอร์ ก็มีหลาย ๆ Project ที่ต้องใช้คณิตศาสตร์มาช่วย
ล่าสุดมีงานเกี่ยวกับ Application วางแผนการผลิต
แล้วคณิตศาสตร์ได้เข้ามาช่วยให้สามารถจัดตารางงานได้อย่างอัตโนมัติ และคำนวนได้อย่างรวดเร็ว
เลยอยากจะแชร์ประสบการณ์จริงกันครับ Smiley

จริง ๆ โจทย์ซับซ้อนกว่านี้มาก แต่ผมลดปัญหาเรื่องอื่นลง จะได้เข้าใจง่ายขึ้น
โจทย์มีอยู่ว่าแต่ละ Workstation มี Machine หลายเครื่อง
แต่ละเครื่องใช้เวลาในการผลิตต่อหน่วยไม่เท่ากัน (A)
แต่ละเครื่องเริ่มผลิตในเวลาที่ไม่เท่ากัน (B)
ต้องกระจายงานแต่ละเครื่องเท่าไหร่ (X)
ให้งานจบในเวลาที่เท่ากันทุกเครื่อง (Y)

ดังนั้น สูตรแต่ละ Machine ก็เป็นอย่างนี้
Y = AnXn + Bn
ถ้ามี Machine 10 เครื่อง ก็จะมี X1, X2, X3, ..., X10
จะเห็นว่าเป็นปัญหาแบบหลายสมการ หลายตัวแปร
ถ้าใครรู้จัก Gauss-Jordan elimination ก็จะรู้ได้เลยว่าแก้ปัญหานี้ได้แน่ Smiley

ก่อนจะเริ่มต้องจัดสมการใหม่ก่อน
สมการที่ Solve ได้ต้องมีหน้าตาอย่างนี้
A1X1 + A2X2 + A3X3 + ... + AmXm = N

ต้องเปลี่ยน Y = AnXn + Bn ให้อยู่ในรูปด้านบน
ก็จะเป็น AnX+ -1Y = -Bn

ดังนั้น Machine 3 เครื่องก็จะได้เป็นสมการนี้
A1X1 + 0X2 + 0X3 + -1Y = -B1
0X1 + A2X2 + 0X3 + -1Y = -B2
0X1 + 0X2 + A3X3 + -1Y = -B3
1X1 + 1X2 + 1X3 + 0Y = C

บรรทัดสุดท้าย คือ เอางานที่กระจายแต่ละเครื่องบวกกัน
ได้ออกมาเป็นจำนวนงานทั้งหมด (C)

พอรู้ Pattern แล้วก็เริ่มเขียนได้เลยครับ
ก่อนอื่นต้องมี Class Matrix ก่อน
จากนั้นก็ Loop ธรรมดาเลยครับ Smiley

var matrix = new Matrix(machines.Count + 1, machines.Count + 2);
int y = machines.Count;
int b = machines.Count + 1;
for (int i = 0; i < machines.Count; i++) {
matrix[i, i] = machines[i].CycleTime;
matrix[i, y] = -1;
matrix[i, b] = -machines[i].StartTime;
matrix[y, i] = 1;
}
matrix[y, b] = total_qty;
matrix = matrix.ReducedEchelonForm();
Code สั้นดีไหมครับ Smiley
ใน Loop ก็แค่เอาเวลาในการผลิต และเวลาเริ่มต้นของแต่ละ Machine ไปหยอดในช่องต่าง ๆ ของ Matrix
หลังจากแปลง Matrix เป็น Reduced Echelon Form แล้ว
จำนวนที่ต้องผลิตของแต่ละ Machine ก็อยู่ที่ matrix[i, b]

แค่นี้ก็แก้ปัญหาได้แล้วครับ Smiley




 

Create Date : 17 ตุลาคม 2553    
Last Update : 17 ตุลาคม 2553 4:17:53 น.
Counter : 988 Pageviews.  

การเขียนโปรแกรมแก้โจทย์ Constraint Satisfaction Problem

Constraint Satisfaction Problem (CSP) เป็นโจทย์ประเภทต้องลองไปเรื่อย ๆ เพื่อค้นหาคำตอบ
โดยรูปแบบที่จะให้ลองมีจำกัด (ไม่ว่าจะมากแค่ไหนก็ตาม)
โดยที่มีข้อกำหนดบางอย่างที่บอกว่าคำตอบนั้นถูกต้อง
ตัวอย่างของ CSP เช่น Sudoku, 8 Queens Puzzle, Einstein's Puzzle

วิธี Solve ปัญหาประเภทนี้แบบง่ายที่สุด เราเรียกว่า Generate and Test (GT)
GT เป็นการสร้างคำตอบก่อน แล้วค่อยทดสอบว่าถูกต้องหรือเปล่า
GT จะเหมาะกับปัญหาประเภท Search space ไม่ใหญ่มาก
ประมาณว่าสั่งแล้วคำตอบต้องออกมาภายในไม่กี่วิ
ผมเคยใช้ GT ตอน Solve 180 IQ
คือ เอาตัวเลขทั้งหมดมาบวก ลบ คูณ หาร กันให้ครบทุกรูปแบบ
แล้วค่อยตรวจดูว่าคำตอบถูกหรือเปล่า

บางที GT ก็ใช้กับ Search space ที่ใหญ่มาก
ถ้าปัญหาไม่สามารถลด Search space ได้ ก็ช่วยไม่ได้ที่ต้องใช้ GT
เช่น จะ Hack password วิธีการที่ลองทีละตัวอักษรเพื่อหาว่า Password ไหนเข้าได้ ก็เป็น GT
ซึ่งบางครั้ง GT มัน Run นานมาก ๆ เค้าเลยเรียกกันว่า Bruteforce (แปลว่า บ้าพลัง Smiley)

GT แบบที่พัฒนาขึ้น เรียกกันว่า Backtracking (BT)
BT ลด Search space โดยการ Test ขณะสร้างคำตอบ
ปัญหา CSP ส่วนใหญ่ จะเหมาะกับ BT เพราะ BT ตัด Search space ได้มากพอแล้วในหลาย ๆ กรณี แถมใช้ Memory น้อย
ผมใช้ BT บ่อยมาก เช่น Solve 8 queens, Impossible puzzle, Knight tour
(BT ในชีวิตจริงก็พวกจัดตารางการผลิต, การวาง Layout เพื่อให้ผลิตได้มากที่สุด, การจัด Package ใส่ Container)
ซึ่งวิธีการหาคำตอบที่ผมเขียนด้วย Linq
ใน 180 IQ ซึ่งเป็น GT ผมมีแค่ Linq Statement เดียวก็ Solve ได้แล้ว
แต่ BT เช่น Impossible puzzle ต้องใช้หลาย Linq ประกอบกัน
หรือใน 8 queens กับ Knight tour ต้องใช้ Recursive Function ในการหาคำตอบ
สรุปคือ BT เร็วกว่า แต่ยุ่งยากกว่า GT
(ผมเคยเขียน Class เพื่อ ลดความยุ่งยากของ BT ลอง Download ไปใช้ดู class ชื่อ Backtracker)


(รูปแบบการใช้ BT solve 4 queens รูปจาก Guide to constraint programming)

รูปแบบที่ Advance กว่า BT เรียกว่า Forward Checking (FC)
ต่างจาก BT ตรงที่ ขณะที่เลือกตัวเลือกเพื่อหาคำตอบ FC จะตัด Choice ที่ไม่ใช่ของตัวที่ยังไม่ได้เลือกทันที
เช่น Sudoku ถ้าคุณอาจจะเขียนเลข 1-9 ตัวเล็ก ๆ ในช่องที่ยังไม่ได้ใส่ตัวเลข
และสมมติคุณเติมเลข 1 เข้าไปในช่องแรก คุณสามารถตัดเลข 1 ออกจากช่องในแถวเดียวกัน
รูปแบบการตัด Search space ของ FC มีหลายแบบ ลองไปอ่านต่อดู ที่นี่
หลัก ๆ คือ ตัดตัวเลือกที่ไม่ใช่ออกให้เร็วที่สุด อาจจะตัดตั้งแต่แรก หรือตัดขณะเลือกตัวเลือกปัจจุบัน

FC เอามาอุดช่องว่างของ BT เรื่อง BT พบทางตันช้าเกินไป
เช่น Sudoku หากมีช่องใดโดนตัดจนไม่มีตัวเลือกแล้ว
BT ยังตะบี้ตะบันหาทีละช่อง ไปเรื่อย ๆ จนถึงช่องที่ไม่มีตัวเลือก
ในขณะที่ FC หยุดทำทันที
และเนื่องจาก  FC เก็บตัวเลือกทั้งหมดไว้ คุณสามารถทำ Variable Ordering ได้
โดยส่วนใหญ่จะเอา Variable ที่มีตัวเลือกน้อยที่สุดมาทำก่อน


(รูปแบบการใช้ FC solve 4 queens รูปจาก Guide to constraint programming)

ยังมีที่ Advance กว่า FC คือ Lookahead (LA)
LA จะทำการ Test Consistency ของตัวเลือกถัดไปด้วย
เมื่อ Test แล้ว ก็จะเจอทางตันเร็วขึ้นอีก
และเพราะว่า LA มีการ Test ตัวเลือกด้วย เลยสามารถทำ Value Ordering ได้
โดยส่วนใหญ่จะเลือก Value ที่มี Conflict ที่น้อยที่สุดมาทำก่อน
(ผมเขียน Class สำหรับทำ Lookahead แถมใช้ง่ายด้วย ลองอ่าน Post เก่า ดูครับ Smiley)


(รูปแบบการใช้ FC solve 4 queens รูปจาก Guide to constraint programming)

คุณคิดว่า LA นี่สุด ๆ หรือยังครับ Smiley
สำหรับ Search space ที่กว้างมาก ๆๆๆ
ต่อให้ใช้ LA ก็ไม่สามารถ หาคำตอบได้ในเวลาที่ต้องการ
คุณมี 2.75 วิธีในการหาคำตอบ

1. Heuristics คือ การใช้ Weight ในการจัดลำดับคำตอบ
    ในเวลาที่จำกัด Heuristics จะได้ คำตอบที่ดีที่สุดในตอนนั้นออกมา แต่ไม่ Guarantee ว่าเป็นคำตอบที่ดีที่สุด
    (เรื่องของ Heuristics ยังมีอีกเยอะ ไว้จะเล่าให้ฟัง)
2. Optimization คือ การใช้ Math หรือ Algorithm (ที่เป็น PTIME) ในการช่วย Solve
    ข้อจำกัดคือ คุณต้องสามารถ Reduce ปัญหา ให้เป็น PTIME ให้ได้
    (ไว้จะเล่าให้ฟังเหมือนกัน แล้วคุณจะรู้ว่า Math ที่เรียนมา มันไม่สูญเปล่า Smiley)
2.5 Dynamic Programming คือ การ Reduce ปัญหาเป็น Sub problem แล้วใช้เทคนิค Memoization ในการ Optimize
    ที่ไม่เป็นข้อ 3 เพราะ DP เป็น Subset ของ Optimization
    (เรื่องของ DP ก็อยากเขียนมาตั้งนานละ แต่ในบทความเก่า ๆ ก็มีใช้ DP อยู่หลายตอนนะ 1 2)
2.75 Solve P=NP ก็แค่พิสูจน์ให้ได้ว่า P=NP แค่นี้แหละ คุณก็จะสามารถ Reduce ปัญหาทั้งหมดให้เป็น PTIME
    แล้วก็รับเงิน 1 ล้านเหรียญ เป็นรางวัล Smiley
    (ถ้าคุณ Solve ได้ 1 ล้านเหรียญ นี่แค่ค่าขนมแน่นอน)




 

Create Date : 09 สิงหาคม 2553    
Last Update : 17 ตุลาคม 2553 1:25:42 น.
Counter : 4533 Pageviews.  

[C#] Solve Einstein's Puzzle ด้วย LINCON

มี Library ตัวนึงชื่อ LINCON
(Language INtegrated CONstraint programming)
ชื่อมันดูเชย ๆ ใช่ไหมครับ
มันเป็นลูกที่ผมทอดทิ้งไปสักพักละ Smiley

คือมีช่วงนึง ประมาณสองปีที่แล้ว
ผมไปติด web ProjectEuler อย่างหนัก (ถ้าอ่าน Post แรก ๆ ของผมก็รู้)
ถึงขนาดไปศึกษา Algorithm ต่าง ๆ มากมาย เพื่อแก้ปัญหา
แล้วก็นำ Algorithm พวกนั้นไปเขียนเป็น Code C#
(นั่นก็เป็นเหตุผลว่าทำไม Blog ของผมมีแต่แนว Algorithm) Smiley

Library ตัวที่ชื่อ LINCON นี้
เป็น Library ที่ผมชอบมากที่สุด แต่ไม่มีเวลามาเขียนให้เสร็จซะที
แต่ไม่รู้ว่าบุญหรือกรรม อาทิตย์ที่แล้วกลับบ้านเร็ว แถมมีวันหยุดพิเศษเนื่องจากเหตุการณ์ไม่สงบ
พอดีอยากเขียนต่อ ก็เลยต่อจนเสร็จซะที Smiley

LINCON เป็น Backtracker ที่มีความสามารถ LookAhead
และพิเศษไปกว่านั้น มันสามารถเขียนด้วย Linq ได้ Smiley

ก่อนอื่นดูตัวอย่างก่อนเลยครับ
คุณรู้จัก Einstein's Puzzle ไหมครับ
เค้าว่ากันว่ามีคนแค่ 2% ที่สามารถแก้โจทย์นี้ได้

โจทย์มีอยู่ว่า

มีบ้านอยู่ 5 หลัง ที่มีสีต่างกันหมด
ในบ้านแต่ละหลังมีคนอยู่หนึ่งคนที่เป็นชนชาติที่ต่างกัน 5 ชนชาติ
ซึ่งทุกคนจะดื่มน้ำที่แตกต่างกัน สูบบุหรี่ยี่ห้อต่างกัน และสัตว์เลี้ยงต่างกัน

คนที่เป็นชาวอังกฤษอยู่บ้านสีแดง
คนที่เป็นชาวสวีเดนเลี้ยงหมา
คนที่เป็นชาวเดนมาร์กดื่มชา
บ้านสีเขียวอยู่ทางซ้ายของบ้านสีขาว
เจ้าของบ้านสีเขียวดื่มกาแฟ
คนที่สูบบุหรี่ยี่ห้อ Pall Mall เป็นคนเลี้ยงนก
เจ้าของบ้านสีเหลืองสูบบุหรี่ยี่ห้อ Dunhill
คนที่อยู่บ้านหลังกลางดื่มนม
คนที่เป็นชาวนอร์เวย์อยู่บ้านหลังแรก
คนที่สูบบุหรี่ยี่ห้อ Blends อยู่ติดกับคนเลี้ยงแมว
คนที่เลี้ยงม้าอยู่ติดกับคนที่สูบบุหรี่ยี่ห้อ Dunhill
คนที่สูบบุหรี่ยี่ห้อ Bulemaster ดื่มเบียร์
คนที่เป็นชาวเยอรมันสูบบุหรี่ยี่ห้อ Prince
คนที่เป็นชาวนอร์เวย์อยู่ติดกับบ้านสีฟ้า
คนที่สูบบุหรี่ยี่ห้อ Blends เป็นเพื่อนบ้านกับคนที่ดื่มน้ำ

คำถามคือ ใครเป็นคนเลี้ยงปลา ?

คุณจะไขปริศนายังไงครับ? แค่คิดก็ยากแล้วใช่ไหมครับ
แต่ LINCON คุณแทบจะไม่ต้องคิดเลยแค่โยนคำถามเข้าไปเท่านั้นเอง

          //มี 5 ชนชาติ
var sol = from n in ArrayExt.Enum<Nationality>().ToConstraintList(5)
          //5 สีบ้าน
          from c in ArrayExt.Enum<HouseColor>().ToConstraintList(5)
          //5 บุหรี่
          from s in ArrayExt.Enum<Smoke>().ToConstraintList(5)
          //5 เครื่องดื่ม
          from d in ArrayExt.Enum<Drink>().ToConstraintList(5)
          //5 สัตว์เลี้ยง
          from p in ArrayExt.Enum<Pet>().ToConstraintList(5)
          //i จะเป็นเลขใดก็ได้ 0-4
          from i in 0.To(4).ToConstraintIndex()
          //ไม่มีชนชาติเดียวกัน
          where Constraint.AllDifferent(n)
          //ไม่มีสีบ้านเดียวกัน
          where Constraint.AllDifferent(c)
          //ไม่มีบุหรี่ยี่ห้อเดียวกัน
          where Constraint.AllDifferent(s)
          //ไม่มีเครื่องดื่มเดียวกัน
          where Constraint.AllDifferent(d)
          //ไม่มีสัตว์เลี้ยงเดียวกัน
          where Constraint.AllDifferent(p)
          //คนที่เป็นชาวอังกฤษอยู่บ้านสีแดง
          where (n[i] == Nationality.British) == (c[i] == HouseColor.Red)
          //คนที่เป็นชาวสวีเดนเลี้ยงหมา
          where (n[i] == Nationality.Swedish) == (p[i] == Pet.Dog)
          //คนที่เป็นชาวเดนมาร์กดื่มชา
          where (n[i] == Nationality.Danish) == (d[i] == Drink.Tea)
          //บ้านสีเขียวอยู่ทางซ้ายของบ้านสีขาว
          where (c[i] == HouseColor.Green) == (c[i + 1] == HouseColor.White)
          //เจ้าของบ้านสีเขียวดื่มกาแฟ
          where (c[i] == HouseColor.Green) == (d[i] == Drink.Coffee)
          //คนที่สูบบุหรี่ยี่ห้อ Pall Mall เป็นคนเลี้ยงนก
          where (s[i] == Smoke.PallMall) == (p[i] == Pet.Bird)
          //เจ้าของบ้านสีเหลืองสูบบุหรี่ยี่ห้อ Dunhill
          where (c[i] == HouseColor.Yellow) == (s[i] == Smoke.DunHill)
          //คนที่อยู่บ้านหลังกลางดื่มนม
          where d[2] == Drink.Milk
          //คนที่เป็นชาวนอร์เวย์อยู่บ้านหลังแรก
          where n[0] == Nationality.Norwegian
          //คนที่สูบบุหรี่ยี่ห้อ Blends เป็นเพื่อนบ้านกับคนที่ดื่มน้ำ
          where ((s[i] == Smoke.Blend) ?
                (d[i - 1] == Drink.Water || d[i + 1] == Drink.Water) : true)
          //คนที่เลี้ยงม้าอยู่ติดกับคนที่สูบบุหรี่ยี่ห้อ Dunhill
          where ((p[i] == Pet.Horse) ?
                (s[i - 1] == Smoke.DunHill || s[i + 1] == Smoke.DunHill) : true)
          //คนที่สูบบุหรี่ยี่ห้อ Bulemaster ดื่มเบียร์
          where (s[i] == Smoke.BlueMaster) == (d[i] == Drink.Beer)
          //คนที่เป็นชาวเยอรมันสูบบุหรี่ยี่ห้อ Prince
          where (n[i] == Nationality.German) == (s[i] == Smoke.Prince)
          //คนที่เป็นชาวนอร์เวย์อยู่ติดกับบ้านสีฟ้า
          where ((n[i] == Nationality.Norwegian) ?
                (c[i - 1] == HouseColor.Blue || c[i + 1] == HouseColor.Blue) : true)
          //คนที่สูบบุหรี่ยี่ห้อ Blends อยู่ติดกับคนเลี้ยงแมว
          where (p[i] == Pet.Cat) ?
                (s[i - 1] == Smoke.Blend || s[i + 1] == Smoke.Blend) : true
          select 0.To(4).Select(x =>
              new {
                        Nationality = n[x],
                        HouseColor = c[x],
                        Smoke = s[x],
                        Drink = d[x],
                        Pet = p[x]
              });

คราวนี้ก็เรียกคำตอบออกมา

solutions.First().ForEach((man, i) =>
    Console.WriteLine("{0}t{1}t{2}t{3}t{4}t{5}",
        i + 1,
        man.Nationality.ToString().PadRight(12),
        man.HouseColor.ToString().PadRight(12),
        man.Smoke.ToString().PadRight(12),
        man.Drink.ToString().PadRight(12),
        man.Pet.ToString().PadRight(12))
);
//    Nationality       HouseColor      Smoke           Drink           Pet
//--------------------------------------------------------------------------------
//1     Norwegian       Yellow          DunHill         Water           Cat        
//2     Danish          Blue            Blend           Tea             Horse      
//3     British         Red             PallMall        Milk            Bird        
//4     German          Green           Prince          Coffee          Fish        
//5     Swedish         White           BlueMaster      Beer            Dog

เห็นไหมครับว่า LINCON เขียนง่ายเข้าใจง่าย
อะไรเป็น Input ก็ใส่เข้าไปใน Syntax from
อะไรที่เป็น Constraint ก็ใส่เข้าไปใน Syntax where
และสุดท้ายจะ Output ก็ใส่ที่ Syntax select

ถ้าสนใจลอง Download ไปเล่นดูได้ครับ
มี Source code ให้ด้วย
ไปที่ chaow.codeplex.com ครับ Smiley




 

Create Date : 22 พฤษภาคม 2553    
Last Update : 22 พฤษภาคม 2553 18:42:50 น.
Counter : 1473 Pageviews.  

1  2  3  4  5  6  

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]





New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.