ดูต้นฉบับสำหรับ วิธีมอนเตการ์โล

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

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

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

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

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

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

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

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

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

: <math>X_{i,j},\quad 1\leq i \leq n, 1\leq j \leq N</math>

แล้วให้

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

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

== การเรียนรู้แบบเสริมกำลัง ==
{{หลัก|การเรียนรู้แบบเสริมกำลัง}}
ในบริบทของ[[การเรียนรู้แบบเสริมกำลัง]] ในสาขา[[การเรียนรู้ของเครื่อง]] วิธีมอนเตการ์โลหมายถึงวิธีการประมาณค่าสถานะและมูลค่าการกระทำโดยอาศัยประสบการณ์การได้รางวัลซึ่งมาจากแค่การกระทำ<ref>{{Cite book|last=Sutton|first=Richard S.|url=http://incompleteideas.net/book/RLbook2018trimmed.pdf|title=Reinforcement Learning: An Introduction|year=1998|isbn=978-0262039246|page=91}}</ref>

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

== อ้างอิง ==
{{รายการอ้างอิง}}

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