โจทย์
ห่วงโซ่มาร์คอฟ เปลี่ยนสถานะแบบสุ่ม และสถานะถัดไปขึ้นกับสถานะปัจจุบันเท่านั้น transition[i][j] คือความน่าจะเป็นที่จะย้ายจากสถานะ i ไปสถานะ j ดังนั้นผลรวมของแต่ละแถวเท่ากับ 1
ถ้า p คือความน่าจะเป็นที่จะอยู่ในแต่ละสถานะตอนนี้ การแจกแจงหลังจากหนึ่งก้าวคือ:
p_next[j] = Σ เหนือ i ของ p[i] × transition[i][j]
จง implement markov_distribution(transition, start, steps) และใช้การอัปเดตนี้ steps ครั้ง
อินพุต
transition: เมทริกซ์ n × n ที่ผลรวมแต่ละแถวเท่ากับ 1
start: การแจกแจงเริ่มต้น (n ค่าที่รวมกันได้ 1)
steps: จำนวนก้าวที่จะเดิน
เอาต์พุต
คืนการแจกแจงหลังจาก steps ก้าว
เงื่อนไข
1 ≤ n ≤ 50, 0 ≤ steps ≤ 1,000
0 ≤ แต่ละความน่าจะเป็น ≤ 1
ตัวอย่าง
อินพุต:
start = [1.0, 0.0]
steps = 2
transition = [
[0.9, 0.1],
[0.5, 0.5]
]
ผลลัพธ์ที่คาดหวัง:
expected = [0.86, 0.14]อินพุต:
std::vector<double> start = {1.0, 0.0};
long long steps = 2;
std::vector<std::vector<double>> transition = {
{0.9, 0.1},
{0.5, 0.5}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<double> expected = {0.86, 0.14};อินพุต:
double[] start = new double[] {1.0, 0.0};
long steps = 2;
double[][] transition = new double[][] {
new double[] {0.9, 0.1},
new double[] {0.5, 0.5}
};
ผลลัพธ์ที่คาดหวัง:
double[] expected = new double[] {0.86, 0.14};คำอธิบาย
ลองนึกถึงวันแดดออก (0) และวันฝนตก (1) โดยเริ่มจากวันแดดออก หลังหนึ่งก้าว: [0.9, 0.1] หลังสองก้าว: แดดออก = 0.9 × 0.9 + 0.1 × 0.5 = 0.86 และฝนตก = 0.9 × 0.1 + 0.1 × 0.5 = 0.14
อินพุต:
start = [0.25, 0.75]
steps = 3
transition = [
[0.0, 1.0],
[1.0, 0.0]
]
ผลลัพธ์ที่คาดหวัง:
expected = [0.75, 0.25]อินพุต:
std::vector<double> start = {0.25, 0.75};
long long steps = 3;
std::vector<std::vector<double>> transition = {
{0.0, 1.0},
{1.0, 0.0}
};
ผลลัพธ์ที่คาดหวัง:
std::vector<double> expected = {0.75, 0.25};อินพุต:
double[] start = new double[] {0.25, 0.75};
long steps = 3;
double[][] transition = new double[][] {
new double[] {0.0, 1.0},
new double[] {1.0, 0.0}
};
ผลลัพธ์ที่คาดหวัง:
double[] expected = new double[] {0.75, 0.25};คำอธิบาย
ห่วงโซ่นี้เปลี่ยนสถานะทุกครั้ง แต่ละก้าวจึงสลับความน่าจะเป็นทั้งสองค่า หลังสลับ 3 ครั้ง: [0.75, 0.25]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
หาการแจกแจงถัดไปโดยส่ง probability mass ผ่านทุก transition จาก distribution ปัจจุบัน
คำใบ้ 2
ให้นึกว่าเป็น matrix-vector multiplication ซ้ำ ๆ ทีละ step
คำใบ้ 3
ถ้า steps เป็น 0 ให้คืนค่า starting distribution เดิมโดยไม่เปลี่ยน
ความซับซ้อนที่คาดหวัง
เวลา O(steps * n^2), หน่วยความจำเพิ่ม O(n)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน