บทความนี้อธิบายถึงปัญหาการคูณ Java Matrix (การเขียนโปรแกรมแบบไดนามิก) แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
คำอธิบายปัญหา: การกำหนด N เมทริกซ์: A1, A2, ... , AN, ที่ AI และ AI+1 เป็นทวีคูณ, i = 1, 2 ... , N-1 กำหนดลำดับการคำนวณของการคำนวณผลิตภัณฑ์ต่อเนื่องของเมทริกซ์เพื่อให้จำนวนการคูณที่จำเป็นในการคำนวณผลิตภัณฑ์ต่อเนื่องของเมทริกซ์ในลำดับนี้มีน้อยที่สุด ข้อมูลอินพุตคือจำนวนเมทริกซ์และขนาดของแต่ละเมทริกซ์และผลลัพธ์ผลลัพธ์คือลำดับการคำนวณและจำนวนการคูณขั้นต่ำสำหรับผลิตภัณฑ์ต่อเนื่องของเมทริกซ์
การวิเคราะห์ปัญหา: เนื่องจากการคูณเมทริกซ์เป็นไปตามกฎหมายของสมาคมจึงมีคำสั่งการคำนวณที่แตกต่างกันมากมายเพื่อคำนวณผลิตภัณฑ์ต่อเนื่องของเมทริกซ์ คำสั่งการคำนวณนี้สามารถกำหนดได้โดยการเพิ่มวงเล็บ หากคำสั่งของการคำนวณผลิตภัณฑ์ต่อเนื่องของเมทริกซ์ถูกกำหนดอย่างสมบูรณ์นั่นคือผลิตภัณฑ์ต่อเนื่องได้รับการจัดอันดับอย่างสมบูรณ์อัลกอริทึมมาตรฐานสำหรับการคูณของเมทริกซ์สองตัวสามารถเรียกได้ซ้ำ ๆ ในลำดับนี้เพื่อคำนวณผลิตภัณฑ์ต่อเนื่องเมทริกซ์
ผลิตภัณฑ์เมทริกซ์แบบวงเล็บอย่างสมบูรณ์สามารถกำหนดซ้ำได้เป็น:
(1) เมทริกซ์เดี่ยวนั้นถูกยึดอย่างสมบูรณ์
(2) ผลิตภัณฑ์เมทริกซ์ A ได้รับการจัดอันดับอย่างสมบูรณ์จากนั้น A สามารถแสดงเป็นผลิตภัณฑ์ของผลิตภัณฑ์เมทริกซ์ที่มีตัวยึด 2 ตัว B และ C และเพิ่มวงเล็บนั่นคือ A = (BC)
ตัวอย่างเช่นมี 5 วิธีที่แตกต่างกันในการยึดผลิตภัณฑ์เมทริกซ์ A1A2A3A4: (A1 (A2 (A3A4))), (A1 ((A2A3) A4), ((A1A2) (A3A4)) (A1 (A1 (A2A3)) แต่ละวิธีของการถ่ายคร่อมอย่างสมบูรณ์สอดคล้องกับลำดับการคำนวณของผลิตภัณฑ์ที่เชื่อมต่อกับเมทริกซ์ซึ่งกำหนดปริมาณของการคำนวณที่จำเป็นในการสร้างผลิตภัณฑ์
ดูตัวอย่างต่อไปนี้คำนวณการคูณเมทริกซ์ทั้งสาม {a1, a2, a3}; ขนาดคือ 10*100, 100*5, 5*50 ตามลำดับ คำนวณจำนวนครั้งที่ต้องการในลำดับนี้ ((A1*A2)*A3): 10x100x5+10x5x50 = 7500 เท่าคำนวณจำนวนครั้งที่ต้องการในลำดับนี้ (A1*(A2*A3)): 10*5*50+10*100*50 = 75000
ดังนั้นคำถามคือ: วิธีการกำหนดลำดับการดำเนินการเพื่อให้จำนวนการคำนวณสามารถลดลงได้
แนวคิดอัลกอริทึม:
ตัวอย่าง: สมมติว่าคุณต้องการคำนวณผลิตภัณฑ์การคูณเมทริกซ์ A1A2A3A4A5A6 ซึ่งขนาดของเมทริกซ์แต่ละตัวคือ:
A1: 30*35; A2: 35*15; A3: 15*5; A4: 5*10; A5: 10*20; A6: 20*25
ความสัมพันธ์แบบเรียกซ้ำ:
การคำนวณการออกแบบ A [i: j], 1≤i≤j≤nและจำนวนขั้นต่ำของการคูณที่ต้องการ m [i, j] จากนั้นค่าที่เหมาะสมที่สุดของปัญหาดั้งเดิมคือ m [1, n]
เมื่อฉัน = j, a [i: j] = ai ดังนั้น m [i] [i] = 0, i = 1,2, …, n
เมื่อฉัน <j ถ้าคำสั่งที่ดีที่สุดของ A [i: j] ถูกตัดการเชื่อมต่อระหว่าง AK และ AK+1, I <= K <J, จากนั้น: M [i] [J] = M [i] [K]+M [K+1] [J]+PI-1PKPJ เนื่องจากตำแหน่งของจุดตัดการเชื่อมต่อ K ไม่เป็นที่รู้จักในระหว่างการคำนวณ K ยังไม่ได้รับการพิจารณา อย่างไรก็ตามมีเพียง JI ที่เป็นไปได้สำหรับตำแหน่ง K ดังนั้น K คือตำแหน่งที่ตำแหน่ง JI ลดจำนวนการคำนวณให้น้อยที่สุด
โดยสรุปมีความสัมพันธ์แบบเรียกซ้ำดังนี้:
สร้างทางออกที่ดีที่สุด:
หากตำแหน่งขาดการเชื่อมต่อ k ของ m [i] [j] ถูกแสดงว่าเป็น s [i] [j] หลังจากคำนวณค่าที่เหมาะสม m [i] [j] วิธีแก้ปัญหาที่ดีที่สุดที่สอดคล้องกันสามารถสร้างซ้ำได้จาก s [i] [j] จำนวนใน s [i] [j] แสดงให้เห็นว่าวิธีที่ดีที่สุดในการคำนวณห่วงโซ่เมทริกซ์ A [i: j] ควรตัดการเชื่อมต่อระหว่างเมทริกซ์ AK และ AK+1 นั่นคือวงเล็บที่ดีที่สุดควรเป็น (A [I: K]) (A [K+1: J) ดังนั้นจากข้อมูลที่บันทึกโดย S [1] [n] เราจะเห็นได้ว่าวงเล็บที่ดีที่สุดสำหรับการคำนวณ A [1: N] คือ (A [1: S [1] [N]]) (A [S [1] [N] +1: N]) ต่อไปเรื่อย ๆ วงเล็บที่ดีที่สุดสำหรับ [1: S [1] [S [1] [S [1] [N]]) คือ (A [S [1] [S [1] [N]+1: S [1] [S [1] [S [1] [S [1] [N]) ในทำนองเดียวกันก็สามารถพิจารณาได้ว่าวงเล็บที่ดีที่สุดของ A [S [1] [N] +1: N] ถูกทำลายที่ S [S [1] [N] +1] [N] ... ถ้าเรายังคงกลับมาอีกครั้ง
แพ็คเกจเมทริกซ์; เมทริกซ์ระดับสาธารณะ {โมฆะคงที่สาธารณะ matrixchain (int [] p, int n, int [] [] m, int [] [] s) {สำหรับ (int i = 1; i <= n; i ++) {m [i] [i] = 0; } สำหรับ (int r = 2; r <= n; r ++) {สำหรับ (int i = 1; i <= n-r+1; i ++) {int j = i+r-1; m [i] [j] = m [i + 1] [j] + p [i-1]*p [i]*p [j]; s [i] [j] = i; สำหรับ (int k = i+1; k <j; k ++) {int t = m [i] [k]+m [k+1] [j]+p [i-1]*p [k]*p [j]; ถ้า (t <m [i] [j]) {m [i] [j] = t; s [i] [j] = k; }}}}} โมฆะคงที่สาธารณะ traceback (int i, int j, int [] [] s) {ถ้า (i == j) กลับ; traceback (i, s [i] [j], s); traceback (s [i] [j] + 1, j, s); System.out.println ("ทวีคูณ" + i + "," + s [i] [j] + "และ a" + (s [i] [j] + 1) + "," + j); } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {system.out.println ("ผลการทดสอบ wulin.com:"); เมทริกซ์ MC = เมทริกซ์ใหม่ (); int n = 7; int p [] = {30, 35, 15, 5, 10, 20, 25}; int m [] [] = new int [n] [n]; int s [] [] = new int [n] [n]; int l = p.length-1; MC.Matrixchain (P, L, M, S); สำหรับ (int i = 1; i <n; i ++) {สำหรับ (int j = 1; j <n; j ++) {system.out.print (m [i] [j]+"/t"); } system.out.println (); } system.out.println (); สำหรับ (int i = 1; i <n; i ++) {สำหรับ (int j = 1; j <n; j ++) {system.out.print (s [i] [j]+""); } system.out.println (); } mc.traceback (1, 6, s); -ผลการทำงาน:
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน