Java Dynamic Programming Edit Problem Problem Problem Code

عملية التخطيط الديناميكي هي: يعتمد كل قرار على الحالة الحالية ، ثم يتم نقل الدولة. يتم إنشاء تسلسل القرار في حالة تغيير ، لذلك تسمى عملية صنع القرار تحسين المراحل المتعددة هذه البرمجة الديناميكية.

البرمجة الديناميكية هي في الواقع مصطلح عام لنوع الموضوع ، وليس خوارزمية ثابتة. يتمثل معنى البرمجة الديناميكية في حل النهج العام من خلال تبني استراتيجيات العودية (أو الانقسام والقهر) وحل المشكلات الفرعية للمشاكل الكبيرة. تتمثل الفكرة الأساسية للبرمجة الديناميكية في تقسيم المشكلة بذكاء إلى مشكلات فرعية متعددة ، والحصول على الحل العام للمشكلة من خلال حساب المشكلات الفرعية. يمكن تقسيم المشاكل الفرعية إلى المزيد من المشاكل الفرعية ، وبالتالي حل المشكلات المطلوبة باستخدام طرق مماثلة للتكرار المتكرر. وصف السؤال:

بالنسبة للتسلسلات S و T ، يتم تعريف المسافة بينهما على أنها: إجراء العمليات التالية عدة مرات على أحدهما: 1 ، حذف حرف ؛ 2 ، أدخل شخصية ؛ 3 ، تغيير شخصية. في كل مرة يتم فيها إجراء العملية ، يتم زيادة العدد بمقدار 1. إن الحد الأدنى لعدد التحول S و T إلى تسلسل متساوٍ هو مسافة التحرير (EditDistance) أو التشابه بين الاثنين. يرجى إعطاء الخوارزمية المقابلة وتنفيذها.

تحليل:

افترض أن أطوال التسلسلات S و T هي M و N على التوالي ، ويتم التعبير عن مسافة التحرير بينهما كتحرير [M] [n]. ثم هناك المواقف التالية عند تشغيل التسلسل:

أ. عندما تكون الأحرف النهائية لـ S و T متساوية ، لا يوجد أحد من عمليات التعريف أعلاه (أي "التحرير") مطلوبًا للأحرف النهائية ، أي أنه لا يوجد عدد مطلوب. يتم استيفاء الشرط: تحرير [M] [n] = تحرير [M-1] [N-1].

ب. عندما لا تكون الأحرف النهائية لـ S و T متساوية ، يجب تحرير نهاية أي منهما ، وسيتم زيادة العدد المقابل بمقدار 1.

B1 ، قم بتعديل نهاية S أو T لجعلها مساوية لـ T أو S ، ثم تحرير [M] [n] = edit [m-1] [n-1] +1 ؛

B2 ، قم بحذف العنصر في نهاية S لجعل S و T متساويين ، ثم تحرير [M] [n] = edit [m-1] [n] +1 ؛

B3 ، قم بحذف العنصر في نهاية T لجعل T و S متساويين ، ثم تحرير [M] [n] = edit [m] [n-1] +1 ؛

B4 ، أضف عنصر الذيل لـ T في نهاية S لجعل S و T متساويين ، ثم يصبح طول S M+1 ، ولكن في هذا الوقت ، تكون العناصر النهائية لـ S و T متساوية بالفعل. تحتاج فقط إلى مقارنة عناصر M الأولى من S مع عناصر N-1 الأولى من T ، لذلك تحرير [M] [n] = edit [m] [n-1] +1 ؛

B5 ، أضف عنصر الذيل من S في نهاية T لجعل T و S متساويين. الموقف في هذا الوقت هو نفس B4 ، مما يرضي التحرير [M] [n] = edit [m-1] [n] +1 ؛

ج. الحالة الخاصة هي أنه عندما يكون S فارغًا ، تحرير [0] [n] = n ؛ وعندما يكون t فارغًا ، قم بتحرير [M] [0] = M ؛ هذا سهل الفهم. على سبيل المثال ، بالنسبة للتسلسلات "" و "ABC" ، فإن الحد الأدنى للتشغيل كلاهما هو 3 ، أي ، تسلسل "" يؤدي 3 عمليات إدخال ، أو تسلسل "ABC" يؤدي 3 عمليات حذف.

لذلك ، ليس من الصعب علينا استنتاج معادلة البرمجة الديناميكية لمسافة التحرير أعلاه:

لذلك ، يمكن التعبير عن التنفيذ المتكرر لخوارزمية البرمجة الديناميكية لمسافة تحرير السلسلة في رمز Java التالي:

 public static int editdistance (سلسلة A ، سلسلة B) {if (a == null || b == null) {return -1 ؛ } return editDistance (a ، A.Length () - 1 ، B ، B.Length () - 1) ؛ } static int editdistance (string a ، int m ، string b ، int n) {if (m <0 || n <0) {return 1 ؛ } آخر if (A. charat (m) == B.Charat (n)) {return editDistance (a ، m - 1 ، b ، n - 1) ؛ } آخر {return math.min (math.min (editdistance (a ، m - 1 ، b ، n) + 1 ، editdistance (a ، m ، b ، n - 1) + 1) ، editdistance (a ، m - 1 ، b ، n - 1) + 1) ؛ }}

تحديث:

في الوقت نفسه ، من معادلة البرمجة الديناميكية لمسافة التحرير ، يمكننا أن نرى أن التحرير [m] [n] يمكن اشتقاقه من تحرير [m - 1] [n - 1] ، تحرير [m - 1] [n] ، تحرير [m] [m] [n - 1] ، وإذا كان التحرير عبارة عن صفيف ثنائي الأبعاد ، التحرير [m] وهذا هو ، يمكننا اجتياز الصفيف ثنائي الأبعاد ثم حساب القيمة الحالية من خلال التراجع.

على سبيل المثال ، بالنسبة للسلاسل s = "sailn" و t = "الفشل" ، تتم تهيئة الصفيف ثنائي الأبعاد على النحو التالي:

لأن s [0] = s ، t [0] = f ، ثم s [0]! = t [0] ، ثم يتوافق مع المصفوفة ثنائية الأبعاد أعلاه ، تحرير [1] [1] = min (edit [0] [0] ، edit [0] [1] ، edit [1] [0] 1 = 1.

لـ S [1] = A ، T [1] = A ، S [1] = T [1] ، فهو يتوافق مع مصفوفة ثنائية الأبعاد ، تحرير [2] [2] = تحرير [1] [1] ، لذلك تحرير [2] [2]

لذلك ، يتم تحرير مسافة التحرير بين الاثنين [M] [n] = تحرير [5] [7] = 3.

لذلك ، وفقًا للفكرة أعلاه ، يمكن تنفيذ إصدار Java من حل التراجع للبرمجة الديناميكية على النحو التالي:

 public static int editdistance (سلسلة A ، سلسلة B) {if (a == null || b == null) {return -1 ؛ } int [] [] matrix = new int [A.Length () + 1] [B.Length () + 1] ؛ لـ (int i = 0 ؛ i <a.length ()+1 ؛ i ++) {for (int j = 0 ؛ j <b.length ()+1 ؛ j ++) {if (i == 0) {matrix [i] [j] = j ؛ } آخر إذا (j == 0) {matrix [i] [j] = i ؛ } آخر {if (a.charat (i - 1) == B.Charat (j - 1)) {matrix [i] [j] = matrix [i - 1] [j - 1] ؛ } آخر {matrix [i] [j] = 1 + math.min (math.min (matrix [i - 1] [j] ، matrix [i] [j - 1]) ، matrix [i - 1]) ؛ }}} مصفوفة الإرجاع [A.Length ()] [B.Length ()] ؛ }

لخص

ما سبق هو المحتوى الكامل لهذه المقالة حول رمز عينة مشكلة تحرير المسافة للبرمجة الديناميكية Java. آمل أن يكون ذلك مفيدًا للجميع. يمكن للأصدقاء المهتمين الاستمرار في الرجوع إلى الموضوعات الأخرى ذات الصلة على هذا الموقع. إذا كانت هناك أي أوجه قصور ، فيرجى ترك رسالة لإشارةها.