ผู้ใหญ่บ้าน Hamburg

someone in Hamburg who try to be expert in something

เทคนิคการเล่น Restaurant City แบบไม่ให้เสียเวลาเปล่า

with 3 comments

Restaurant City เกมแบบที่ใช้ยุทธการแมลงหวี่ที่หาเล่นได้จาก facebook จะว่าไปแล้วมันก็คือเกม Pizza Tygoon ที่เล่นกันเมื่อสิบกว่าปีก่อนนั่นเอง ซึ่งเกมหลังเล่นไปเล่นมากลายเป็นมาเฟียไปเฉย ความสนใจในการทำร้าน Pizza ให้ได้ดีก็หมดไป ค้าอาวุธลูกเดียว ส่วนเกมที่มาทีหลังอย่าง Restaurant City นั้นมีวิธีการง่าย ๆ ที่เข้าใจได้ไม่ยาก ดังนี้

  1. คนปรุงอาหารต้องเพียงพอเสมอ สูตรตายตัวคือ 3 คนต่อพนักงานเสริฟ 1 คน
  2. ลูกค้าจะต้องใช้เวลาไปกลับให้นานที่สุด
  3. คนเสริฟจะต้องเดินทางให้สั้นที่สุด

ข้อสามนี้เองที่เป็นจุดสุดยอดของเกมนี้ กล่าวคือนี่คือปัญหา min max โดยมีเงื่อนไขที่ยากที่สุดคือคนต้องเ้ข้าไปนั่งได้ด้วย วันก่อนพึ่งนั่งเรียน Convex Optimization เรื่องการ Place ทำให้คิดว่าปัญหาข้อสามที่เราเจอบนเกมนี้สามารถหาค่าที่ดีที่สุดได้

ถ้าสังเกตุดี ๆ ปัญหาที่เกมนี้ในข้อสามคือ มันจะมีเหตุการณ์ที่คนเสริฟมักจะเดินจากมุมสุดของเตาไปยังอีกมุมของลูกค้าที่อยู่ไกลมาก ๆ อยู่เสมอ  ๆ ซึ่งเป็นเรื่องไม่พึงประสงค์เพราะมีลูกค้าหลายคนรอให้เก็บโต๊ะ และพร้อมที่จะเดินหนี ถ้าเป็นคนเล่นก็คงเก็บโต๊ะก่อนแล้วค่อยไปเสริฟ กรณีอย่างนี้ถ้าเราเฝ้าดูจะพบว่าพนักงานเสริฟจะมีคิวของงาน กล่าวคืออะไรมาก่อนทำก่อน นั่นคือไม่ว่าคนเสริฟจะอยู่ตำแหน่งไหนก็ตามเมื่อเสร็จงานนั้น ๆ แล้วก็จะไปทำงานในคิวต่อไป โดยไม่สนใจว่างานนั้นจะอยู่ไกลเท่าไร่ ดังนั้นเพื่อให้การจัดโต๊ะเป็นไปอย่างดีที่สุดตำแหน่งของโต๊ะต้องทำให้พนักงานเสริฟเดินใกล้ที่สุด นั่นคือเราต้องหาวิธีการคิดที่จะทำให้ระยะทางที่ไกลที่สุดสั้นที่สุด และระยะทางนั้นต้องเป็นบวกด้วย ยังไม่พอเราต้องมีการคิดด้วยว่าถ้าคำตอบได้ระยะทางที่ไม่ไกลมาก แต่มีหลาย ๆ อัน ก็น่าจะเกิดผลเสียมากกว่าผลดี ดังนั้นต้องมีการชั่งน้ำหนักว่าผลรวมของระยะทางต้องไม่มากเกินไปหรือต้องน้อยที่สุด มาลองเขียนปัญหานี้ดู

\text{minimize } \max x_i + \gamma\max x^T\bold{1}
\text{ subject to } x_i \geq 0, \quad y_j > 0

ในกรณีนี้ \gamma เป็นค่าน้ำหนักว่าเราสนใจกรณีไหนมากกว่ากัน ส่วน y_j เป็นโอกาสที่ลูกค้าจะเข้าถึงที่นั่ง ส่วนตัวแปรที่จะใช้ในการ minimize นั้นต้องคิดเอาเองนะครับ เพราะกรณีนี้ต้องมีโต๊ะที่คงที่กับโต๊ะที่เลือกวางได้ สมการของ x_i ก็จะหลากหลายแตกต่างกันออกไป

อาจารย์คณิตศาสตร์อาจจะใช้โอกาสนี้ในการสร้างโจทย์ปัญหาให้นักศึกษาแก้โดยมีสนามจริงให้พิสูจน์ นั่นคืออาจารย์ก็เล่น Restaurant City พอไปถึงสถานการณ์ที่คนเสริฟจำกัด 2 คน คนปรุงอาหาร 5 คน ร้านมีพื้นที่จำกัด (แน่หละสิ) ก็จะเกิดปัญหานี้ขึ้นพอดี ก็ให้นักศึกษาเข้าไปแก้ไข แล้วก็เปิดเว็บลองเล่นกันดูเลยว่าของใครดีกว่าใคร อนึ่งปัญหานี้มันไม่ convex คำตอบจึงไม่เป็นคำตอบเดียว นักศึกษาสามารถแก้ปัญหาด้วยการเปลี่ยนปัญหาให้เป็นปัญหาแบบ convex หรือใช้วิธีการแบบ nonconvex แต่ไปแก้ปัญหาเรื่องค่าตั้งต้น หรือลดจำนวนตัวแปรเอา ก็น่าจะสนุกดี กรณีตัวอย่างนี้น่าสนุกเพราะโดยปกติปัญหาที่ยกขึ้นมาในวิชาต่าง ๆ มันเป็นตัวอย่างง่าย ๆ พิสูจน์ความเข้าใจได้ด้วยการพยักหน้า แต่แก้ไขสถานการณ์จริงไม่ได้ ครั้นจะลองกับปัญหาจริง ๆ ก็ไม่มีใครกล้าลงทุนลงแรง อย่างนี้น่าจะสนุกกว่า

สิ่งที่ต้องระวังอย่างเดียวคืออาจารย์กับลูกศิษย์จะไม่ทำอะไรนอกจากแข่งกันเล่นเกมโดยใช้คณิตศาสตร์เข้าช่วยหรือเปล่าก็เท่านั้น

Written by tsvhh

มิถุนายน 14, 2009 ที่ 9:48 am

เขียนใน การศึกษา, ขำ

Tagged with

3 Responses

Subscribe to comments with RSS.

  1. ผมสนใจมากคราบในการแก้ปัญหาโดยconvexแตผมยังงงอยู่ช่วยแนะนำหน่อย
    วิเคราะห์โจทย์และวิธีการแก้ปัญหาให้หน่อยได้ไหมคราบ

    Convex function

    ตุลาคม 7, 2009 at 9:06 am

  2. asfsdfawerwetr

    sdfsdgfesgrg

    กุมภาพันธ์ 13, 2010 at 7:18 am

  3. ช่วยแนะนำหน่อย ผมอายุ13 อีเมล์ Lek_9991@hotmail.com

    วิธีการเปิดการแลดเปลียนวัดทุดิป แล้วก็ เอาคนนอนทีละคน คราฟ

    best

    เมษายน 16, 2011 at 2:42 am


ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

%d bloggers like this: