วิธีมอนเตการ์โล

**วิธีมอนเตการ์โล** (Monte Carlo method, MC) เป็นชื่อเรียกวิธีการที่ใช้เลขสุ่มในการทำการจำลองหรือการวิเคราะห์เชิงตัวเลข เดิมทีมีที่มาจากการที่สตานิสวัฟ มาร์ชิน อูลัมคิดวิธีเพื่อที่จะค้นหารูปแบบของการเคลื่อนวนของนิวตรอนภายในสสาร และได้รับการตั้งชื่อนี้โดยจอห์น ฟอน นอยมันน์ โดยที่มาของชื่อมาจากชื่อเขตมอนเตการ์โลของโมนาโกซึ่งมีชื่อเสียงเรื่องกาสิโน

## ทฤษฎีการคำนวณ
ในสาขาทฤษฎีการคำนวณ วิธีมอนเตการ์โลได้รับการนิยามว่าหมายถึงขั้นตอนวิธีแบบสุ่ม ภายใต้ขอบเขตบนของความน่าจะเป็นที่จะให้คำตอบที่ไม่ถูกต้อง ตัวอย่างเช่น การทดสอบจำนวนเฉพาะแบบมิลเลอร์–ราบิน ขั้นตอนวิธีนี้จะตอบว่าใช่อย่างแน่นอนหากจำนวนที่ให้เป็นจำนวนเฉพาะ แต่ถ้าเป็นจำนวนประกอบก็อาจตอบว่าใช่ ทั้ง ๆ ที่ควรจะตอบว่าไม่ใช่ แม้ว่าจะมีความน่าจะเป็นน้อยมากก็ตาม โดยทั่วไป วิธีมอนเตการ์โลจะทำโดยเลือกแบบสุ่มโดยอิสระแล้ววนซ้ำไปเรื่อย ๆ และความน่าจะเป็นที่จะได้คำตอบที่ไม่ถูกต้องสามารถลดลงได้ด้วยการทุ่มเทเวลามากขึ้น ในบรรดาวิธีมอนเตการ์โล วิธีที่ขอบเขตบนของปริมาณการคำนวณเวลาสูงสุดสำหรับข้อมูลใด ๆ ที่ป้อนเข้าถูกกำหนดโดยพหุนามของขนาดค่าป้อนเข้า เรียกว่าเป็นวิธีมอนเตการ์โลที่มีประสิทธิภาพ

ขั้นตอนวิธีการเลือกแบบสุ่มซึ่งตามทฤษฎีไม่จำเป็นต้องสิ้นสุด แต่จะถูกต้องเสมอหากได้รับคำตอบ เรียกว่า วิธีลาสเวกัส

ทฤษฎีความซับซ้อนในการคำนวณ กำหนด ประเภทความซับซ้อนของปัญหาต่าง ๆ ที่สามารถจำลองได้ด้วยเครื่องทัวริงเชิงความน่าจะเป็น และแก้โดยใช้วิธีมอนเตการ์โล ตัวอย่างทั่วไป ได้แก่ **RP**, **BPP** และ **PP** ด้วยการอธิบายความสัมพันธ์ระหว่างประเภทเหล่านี้กับ **[[พี (ความซับซ้อน)|P]]** และ **[[เอ็นพี (ความซับซ้อน)|NP]]** ช่วงของปัญหาที่สามารถแก้ไขได้โดยอัลกอริธึมที่มีการสุ่มเช่นวิธีมอนเตการ์โลจะขยาย (P ≠ BPP) หรือไม่ หรือจะเพียงแค่ลดลำดับเวลาพหุนามของปัญหาที่สามารถแก้ไขได้ด้วยขั้นตอนวิธีเชิงกำหนด (คือ P=BPP หรือไม่) นี่เป็นหนึ่งในคำถามสำคัญใน ทฤษฎีความซับซ้อนในการคำนวณ ปัจจุบันเรารู้ว่า **NP** ⊂ **PP** และ **RP** ⊆ **NP** แต่ไม่ทราบความสัมพันธ์ระหว่าง **BPP** และ **NP**

## ปริพันธ์
[right|thumb| ตัวอย่างการใช้วิธีมอนเตการ์โล เพื่อประมาณ[พาย (ค่าคงตัว)|ค่า π เมื่อสุ่มวาง 30,000 จุด ค่าประมาณของ π ที่ได้มีความผิดพลาดน้อยกว่า 0.07% จากค่าจริง]]
ในด้านการวิเคราะห์เชิงตัวเลข มักใช้วิธีมอนเตการ์โลเป็นวิธีการประมาณความน่าจะเป็น หากทำการจำลอง *n* ครั้งและมีเหตุการณ์บางอย่างเกิดขึ้น *m* ครั้ง ความน่าจะเป็นของเหตุการณ์นั้นโดยธรรมชาติจะประมาณได้เป็น *m*/*n* ยิ่งจำนวนการทดลองน้อย การประมาณก็จะยิ่งหยาบ และยิ่งการทดลองมากขึ้น การประมาณก็จะยิ่งดีขึ้นเท่านั้น

นอกจากนี้ เมื่อใช้ความน่าจะเป็นนี้ ก็จะสามารถหาคำตอบโดยประมาณของ ปริพันธ์ (พื้นที่) ได้ พื้นที่ *S* ของพื้นที่ *R* สามารถประมาณได้เป็น *S* = *pT* โดยการสุ่มวางจุดภายในพื้นที่ของพื้นที่ *T* ที่รวมพื้นที่ *R* ด้วย และค้นหาความน่าจะเป็นที่ *p* ตกภายในพื้นที่ *R* โดยใช้วิธีมอนเตการ์โล

*n-* อินทิกรัลพับ

: I = \int_0^1\dotsi\int_0^1 f(x_1,x_2,\dotsc,x_n) dx_1\dotsm dx_n

คำนวณโดยใช้วิธีมอนเตการ์โลที่มีขนาดตัวอย่างเป็น *N* โดยสร้างตัวเลขสุ่มชุด *n* &#xD7; *N* ที่มีค่าระหว่าง 0 ถึง 1

: X_{i,j},\quad 1\leq i \leq n, 1\leq j \leq N

แล้วให้

: I_N = \frac{1}{N}\sum_j f(X_{1,j}, X_{2,j}, \dotsc, X_{n,j})

จะได้ *I <sub>N</sub>* เป็นค่าประมาณของอินทิกรัล การแทนที่ตัวเลขสุ่มแบบสม่ำเสมอด้วยลำดับการกระจายแบบสม่ำเสมอยิ่งส่งผลให้เกิดวิธีเสมือนมอนเตการ์โล

## การเรียนรู้แบบเสริมกำลัง

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

## สถิติศาสตร์
วิธีบูตสแตรป เป็นหนึ่งในวิธีมอนเตการ์โลซึ่งใช้ในทางสถิติศาสตร์

## อ้างอิง

หมวดหมู่:วิทยาศาสตร์เชิงคำนวณ
หมวดหมู่:ฟิสิกส์เชิงคำนวณ
หมวดหมู่:กลศาสตร์เชิงสถิติ
หมวดหมู่:ขั้นตอนวิธีแบบสุ่ม
หมวดหมู่:วิธีมอนเตการ์โล