مقدمه :
اين مطلب يك ايده متعار ف براي تعداد متفاوتي از روشهايي است كه جهت تشخيص الگو بكار مي روند و اهميت ندارد كه آن الگوها آماري ، تركيبي يا ساختاري باشند. اين يك مقايسه از الگويي ناشناخته با يك عدد بطور نمونه يا با نمونه الگوي اوليه با استفاده از فاصله يا ( ميزان ) شباهت يا تفاوت است. يعني هر الگوي ناشناخته را بصورت نمونه با يك رشته عددي تقريب زده و آن رشته را با رشته عددي الگوي اوليه مقايسه مي كنيم. ابتدا ارائه يك عدد از نمونه هاي اوليه كه به كلاس مربوط به آن نمونههاي اوليه شناخته شده مرتبط است ، و سپس دسته بندي يك الگوي ناشناخته بوسيله تعيين كردن بيشترين شباهت الگوي تصميم گيري براي آن كلاس است كه دست يافتني است. پس براي هر نمونه اوليه يك عدد در نظر مي گيريم كه آن عدد با كلاسهاي اين نمونه هاي شناخته شده در ارتباط است و دسته بندي الگوهاي ناشناخته بوسيله تعيين كردن بيشترين شباهت الگو و تصميم گيري درباره كلاس آن حاصل مي شود.
در دسته بندي آماري ، نمونه ها به وسيله عامل مشترك از يك تابع تصميم گيري ارزيابي شده اند. پارامترها از يك احتمال توزيع شده نقاط ، در يك فضاي ويژگي تعريف شده ، و مفهوم شباهت نيز بر اساس فاصله تعريف شده است. و توابع تصميم گيري در فضاي n بعدي از اعداد حقيقي كار مي كنند. اگر ساختار الگو لازم باشد ، گرامرهاي رسمي (قراردادي) يك مفهوم مفيد هستند. تابع متداول بصورت دستي يا بصورت اتوماتيك يك گرامر از يك بسته نمونه را نتيجه مي دهد. بنابراين يك الگوي ورودي ناشناخته به يك تجزيه كننده تحويل داده شده و مطابق با اين گرامر تحليل مي شود. در اين روش نه فقط يك دسته بندي ، بلكه همچنين يك شرح ساختاري از الگوي ناشناخته مي توان فراهم كرد. تحليل گر نحوي ميتواند مانند يك تابع ويژه براي تصميم گيري شباهت ساختاري تفسير شود.
مطابق ساختارهاي دادهاي متفاوت كه براي تشخيص الگو مورد استفاده قرار ميگيرند ، فقط رشته گرامرها بررسي نمي شود ، بلكه درخت ، گراف و آرايه گرامرها در يك قاعده مهم تشخيص الگو فعاليت دارند.
اينها مواردي از تعدادي از مثالهاي آماده بسيار كوچك هستند كه كاربردشان براي نتيجه گيري دستوري است ، يا در جايي است كه تمام توان يك پيشروي دستوري نياز نيست. يعني كاربرد اين مثالهاي آماده بسيار كوچك براي استنتاجي بر اساس قواعد ، و يا استنتاجي در مكاني كه نيازي نيست از تمام توان قواعد استنتاجي استفاده كرد مي باشد. اگر ساختار الگو مورد نياز باشد ، با اين حال ، شايد تكنيك تطبيق ساختاري مفيد باشد.
ايده پايه اي تطبيق ساختاري ، به سوي بازنمايي مستقيم نمونه هاي اوليه است ، بخوبي الگوهاي ورودي ناشناخته ، كه بوسيله معاني يك ساختار داده مناسب و بسوي مقايسه اين ساختارها در ترتيبي براي يافتن شباهت نمونه اوليه با يك الگوي ناشناخته ورودي حركت مي كند. اين حركت به جلو نيازمند يك عدد قراردادي از شباهت بين دو ساختار ارائه شده است. تعدادي از برخي اعداد در برخي از نوشته ها پيشنهاد شده است. آنها مي توانند به گروههاي بزرگي طبق ساختارهاي دادهاي تقسيم بشوند كه براي تشخيص الگو استفاده شدهاند. بيشتر ساختارهاي داده اي مهم ، رشته اي ، درختي ، گراف و آرايه اي هستند. وابستگي به دامنه مسائل خاص براي همه اين ساختارهاي دادهاي مي تواند بوسيله ويژگي هايشان افزايش يابد.
با يك محاسبه پيچيده ، رشتهها خيلي كارآمد هستند ، از آنجائيكه بررسي ميزان شباهت بين رشته ها مي تواند كاملا سريع انجام شود ، اگر چه رشتهها به تعداد نمايششان محدود هستند. در موارد خيلي زياد گراف ها بيشترين قدرت رسيدن به بازنمايي الگوي ساختاري را دارند. اگر چه تطبيق گراف بطور مفهومي نسبتا پيچيده است ، و به نسبت قيمت محاسبات ، گران است. بنابراين يك تعادلي بين تعداد نمايه ها و تعداد تكرارهايمان براي تطبيق نياز است. اگر ما براي بازنمايي كلاس الگو از يك گرامر استفاده كنيم ، يك تعادل ساده رعايت مي شود.
در اين بخش ما مهمترين راه رسيدن به تطبيق رشته را بررسي مي كنيم. از نقطه نظر نمايش ، تطبيق ساختاري ، مي تواند به عنوان يك مورد خاص نحوي ( تركيبي ) در حركت بر اساس گرامر مطرح بشود.

فهرست مطالب

چكيده ……………………………………………………………………………………………………………… …..1
مقدمه ……………………………………………………………………………………………………………………2

فصل اول : كليات

1-1) هدف ……………………………………………………………………………………………………………….6
1-2) پيشينه تطبيق رشته ……………………………………………………………………………………………6
1-3) روش كار و تحقيق ……………………………………………………………………………………………….7

فصل دوم : فاصله ويرايشي رشته و تطبيق گراف

2-1) تبديل گراف به رشته …………………………………………………………………………………………….10
2-2) تطبيق گراف ………………………………………………………………………………………………………10
2-3) فاصله ويرايشي رشته …………………………………………………………………………………………. 13
2-4) جمع بندي ………………………………………………………………………………………………………..15

فصل سوم : تقريب سريع تطبيق رشته

3-1) تطبيق رشتهاي تقريبي ……………………………………………………………………………………… 18
3-2) اصول كلي كار …………………………………………………………………………………………………. 19
3-2-1) فهرست براي تطابق رشتهاي تقريبي …………………………………………………………………… 20
3-2-2) جستجوي آنلاين ……………………………………………………………………………………………. 22
3-2-3) جستجو در فواصل اندازهاي كلي ………………………………………………………………………… 23
3-3) لغت به عنوان يك فاصله اندازه اي ……………………………………………………….. ………………..26
3-4) جمع بندي ………………………………………………………………………………………………………28

فصل چهارم : تطبيق رشته اي براي تشخيص ساختاري الگو

4-1) الگوريتم ابتدايي ……………………………………………………………………………………………….31
4-2) مفاهيم تشخيص الگو بر اساس فاصلههاي رشته اي …………………………………………………….40

فصل پنجم : الگوريتم بهينه شده براي تطبيق رشته اي

5-1) اصلاحاتي در الگوريتم پايه ………………………………………………………………….. ……………….46
5-1-1) يك روش ساده شده ………………………………………………………………….. …………………..46
5-1-2) شباهت جمله ها در زير دنباله هاي مشترك ……………………………………………………………. 47
5-1-3) مطابقت دهي كشساني و درهم پيچشي ……………………………………….. ……………………48
5-1-4) فاصله رشته بر اساس جايگزيني هاي تعميم يافته ……………………………………………………. 50
5-1-5) هزينه هاي وابسته به متن …………………………………………………………… ………………….54
5-1-6) يك روش سريعتر ……………………………………………………………………… ……………………57
5-2) تطبيق رشته هاي خاص ……………………………………………………………………………………… 58

فصل ششم : نتيجه گيري و پيشنهادات

6-1) نتيجه گيري ……………………………………………………………………………………………………..62
6-2) پيشنهادات ……………………………………………………………………………………………………..62

فصل هفتم : منابع و ماخذ

7-2) آدرس چند سايت و مقاله مرتبط …………………………………………………………… ……………….66
7-2-1) آدرس چند سايت مرتبط …………………………………………………………….. …………………….66
7-2-2) آدرس چند مقاله مرتبط ……………………………………………………………… …………………….66

فهرست شكلها

3-1) تقريب جستجو در يك ايندكس معكوس …………………………………………………….. ……………21
3-2) ساختار دادهاي پيشنهادي …………………………………………………………………………… ……27
4-1) الگوريتم براي محاسبه d(x,y) …….ا……………………………………………………………………….. 34
4-2) تصوير گرافيكي الگوريتم شكل 4-1 ………………………………………………………….. ……………35
4-3) يك مثال از محاسبه فاصله رشته ……………………………………………………………….. …………36
4-4a) سه مسير متفاوت ، مطابق با حداقل هزينه عملياتهاي ويرايشي ………………….. ……………….37
4-4b) سه مسير متفاوت ، مطابق با حداقل هزينه عملياتهاي ويرايشي ……………………………………. 37
4-4c) سه مسير متفاوت ، مطابق با حداقل هزينه عملياتهاي ويرايشي …………………… ……………….38
4-5) مثال ديگري از محاسبه فاصله رشته ……………………………………………………………………….. 38
4-6) دو مسير متفاوت مطابق با حداقل هزينه عملياتهاي ويرايش در شكل 4-5 ……………………………. 39
5-1) اصلاحاتي در الگوريتم شكل 4-1 براي مطابقت دهي كشساني …………………….. …………………48
5-2) يك مثال از مطابقت دهي كشساني ……………………………………………………………. ………….49
5-3) توضيح گرافيكي محاسبه فاصله رشته بر پايه جايگزينيهاي تعميم يافته ……………………………….. 52
5-4) يك مثال از فاصله رشته وابسته به متن ………………………………………………………. ……………57

فصل اول

1- 1) هدف :
هدف از اين سمينار ارائه يك الگوريتم با كمترين پيچيدگي زماني ، جهت بدست آوردن فاصله بين يك رشته به عنوان الگوي ناشناخته با يك مجموعه رشته به عنوان كلاس هاي الگوست. حال اين فاصله ممكن است فاصله ويرايشي شباهتي يا فاصله ويرايشي تفاوتي باشد. يعني در بررسي تطبيق رشته ها تا به اينجا ميرسيم كه اين دو رشته (يعني الگوي ناشناخته با هر يك از الگوهاي مجموعه كلاس الگو) به ميزان α% شباهت و يا β% تفاوت دارند. كه اين درصد بر اساس تعداد كاراكتر مشابه ، تقسيم بر طول رشته ضرب در 100 براي حالت شباهت ، و بر اساس تعداد كاراكتر متفاوت ، تقسيم بر طول رشته ضرب در 100 براي حالت تفاوت محاسبه مي گردد.
1- 2) پيشينه تطبيق رشته :
فاصله ويرايشي بين دو رشته كاراكتري را مي توان به صورت حداقل هزينه دنباله اي از عمليات ويرايشي تعريف كرد ، كه يك رشته را به رشته ديگري تبديل مي كند. عملياتي كه ما مي پذيريم عبارت است از حذف كردن ، درج كردن و جايگزيني يك نماد در يك زمان و احتمالا براي هر كدام از اين عمليات ها هزينه هاي متفاوتي وجود دارد. مسئله پيدا كردن بلندترين زير دنباله مشترك دو رشته حالت خاصي از مسئله محاسبه فاصلههاي ويرايشي ميباشد. براي محاسبه فاصلههاي ويرايشي هزينه هاي عمليات ويرايشي بايد مضرب صحيحي از يك عدد حقيقي مثبت مثل r باشد ، و به الفباي مورد استفاده در رشته ها محدود باشند. اين شرايط براي اينكه الگوريتم محدوديت زماني داشته باشد لازم هستند.
Wagner و Fischer الگوريتمي براي تعيين يك دنباله از تبديلات ويرايشي كه يك رشته را به رشته ديگر تبديل ميكند ارائه كردند. زمان اجراي الگوريتم آنها متناسب با حاصلضرب طولهاي دو رشته ورودي است. همان سه نوع عمليات گفته شده اينجا هم مد نظر هستند. يعني: 1- درج يك كاراكتر در رشته ، 2- حذف يك كاراكتر از رشته و 3- جايگزيني يك كاراكتر از رشته با كاراكتري ديگر. اين الگوريتم دنباله ويرايشي بهينه اي را براي جفت رشته محاسبه ميكند ، و به عنوان حالت خاص مي تواند بلندترين زير دنباله مشترك آنها را بدست بياورد.
براي حالت الفباي محدود Wong و Chandra حدهاي بالايي و پاييني متناسب با ٢n را با استفاده از يك مدل با محدوديت جزئي بدست آوردند. همچنين Aho نتايج مشابهي را براي مسئله بلندترين زير دنباله مشترك بدست آورد. Lawrance و Wagner نتايج Wagner و Fischer را تعميم دادند تا شامل عمل جابجايي كاراكترهاي مجاور باشد. آنها با حل كردن مسئله تعميم يافتهشان الگوريتمي از درجه (2O(n را ايجاد كردند.

1- 3) روش كار و تحقيق :
با استفاده از ماتريس نزديكي يك گراف گره هاي آن را به رشته تبديل مي كنيم. آنگاه اگر اين ترتيب از گرهها با يك پيمايش تصادفي از گراف يكسان بود ، آن عمليات ويرايشي را پيدا ميكنيم كه بتواند رشته حاصل از ماتريس نزديكي را با كمترين فاصله ويرايشي به رشته حاصل از پيمايش تصادفي گراف تبديل كند. براي يافتن اين فاصله ويرايشي ميتوان از روش Wagner پيروي كرده و از برنامه نويسي ديناميكي براي ارزيابي فاصله ويرايشي بين رشتـهها استفـاده كـرد. پـس بـا سـه عمليـات درج (مانند : ε→a اضافه كردن a) ، حذف (مانند : b→ε حذف b) و جايگزيني (مانند : a→b جايگزين كردن a به جاي b) و تخصيص هزينه اي براي هر كدام و جمع هزينه ها ، تلاش مي كنيم تا رشته اول را به رشته دوم تبديل كنيم و ميزان تطابق را بدست آوريم.
براي تقريب سريع تطبيق رشته ، ابتدا بايد فاصله ويرايشي يا ed() بين دو رشته مورد نظر را كه همان k است بدست آورد. فاصله ويرايشي در واقع كمترين فاصله درج ، حذف و يا جابجايي كاراكتر جهت همسان سازي رشتههاست. برنامه نويسي پويا كه بهترين نتايج را توليد مي كند در بدترين حالت داراي O(mn) مي باشد. ايده جستجوي تقريبي براي پايگاه داده تصاوير ، اثر انگشت ، فايلهاي صوتي و بانكهاي اطلاعاتي بزرگ كاربرد دارد كه هدف اصلي مطابقت رشتهاي تقريبي در آن ، ناشي از كيفيت پايين متن ، ناهماهنگي پايگاه داده ، غلط املايي در الگو يا در متن ، جستجوي اسامي خارجي و جستجوي نامطمئن است.
براي اينكه بتوان ميزان شباهت يا تفاوت رشته مورد نظر با الگو را بصورت ساختاري با استفاده از تطبيق رشتهاي تشخيص داد ، به كمك سه عمليات ويرايشي كه گفته شد يك ماتريس تشكيل داده و در آن تعريف مي كنيم كه حركت عمودي به سمت پايين در ماتريس به معناي حذف يك كاراكتر ، حركت افقي به سمت راست در ماتريس به معناي اضافه كردن يك كاراكتر و حركت اريب به سمت انتهاي ماتريس به معناي جايگزيني يك كاراكتر است. و با يك كد برنامه نويسي سلولهاي اين ماتريس را پر ميكنيم و در نهايت عنصر موجود در خانه (n,m) كمترين هزينه عمليات ويرايشي براي تبديل رشته اول به رشته دوم را در خود نگهداري خواهد كرد.

فصل دوم

فاصله ويرايشي رشته و تطبيق گراف

2-1) تبديل گراف به رشته :
اين فصل نشان مي دهد كه چگونه ساختار ويژه ماتريس نزديكي ، مي تواند به منظور يك تطبيق دهي كارآمد گراف مورد استفاده قرار گيرد. اگر بردار ويژه هادي يك ماتريس احتمال انتقال ، همان حالت يكنواخت زنجيره وابسته به ماركوف باشد ، آنگاه هنگاميكه ماتريس انتقال نرمال شده نزديكي يك گراف ، موجود باشد ، بردار ويژه هادي ، يك دنباله از گرههاي پيمايش تصادفي بر روي گراف در حالت يكنواخت را به ما نتيجه مي دهد. ما از اين ويژگي براي تبديل گرههاي گراف به رشته استفاده مي كنيم. به اين شكل ، كه اگر ترتيب گرهها با يك دنباله از گرههاي ديده شده در پيمايش تصادفي گراف داده شده يكسان باشد ، گرافهايي را كه به اين صورت نشان داده مي شوند بوسيله پيدا كردن دنبالهاي از عمليات ويرايشي رشته كه فاصله ويرايش را به كمترين مقدار ميرسانند تطبيق مي دهيم.
2-2) تطبي ق گراف :
تطبيق گراف در سطح بالايي از نگرش كاري است كه از اهميت محوري برخوردار است به اين دليل كه ابزاري فراهم ميآورد كه بوسيله آن ميتوان توصيفات تصويري يگانه را با يكديگر تطبيق داد.
متاسفانه از آنجا كه پروسه فراخواني و بدست آوري ساختارهاي گراف از داده هاي خام تصويري به دليل وجود نويز و كارآيي محدود الگوريتمهاي موجود قطعه بندي كاري ظريف و دشوار ميباشد ، تطبيق گراف همواره با روشهاي غير دقيق حاصل مي شود. جستجو براي يافتن روشهايي كه در برخورد با خطاهاي تطبيقدهي گراف ، قويتر عمل كنند ، در طول دهه هاي اخير مورد توجه و كوشش مداوم متخصصين بوده است. همه روشها از ايدههاي تشخيص الگوي ساختاري بيرون كشيده شده و در حول موضوع گسترش و تعميم دادن مفهوم فاصله ويرايش رشته به گراف ها عمل مي كنند. پيشرفتهاي اخيربر روي استفاده از روشهاي بهينهسازي و احتمالاتي متمركز شده اند ، با اين هدف كه پروسه تطبيقگراف را در برابر خطاهاي ساختاري مقاوم كنند.
با وجود اثبات كارآيي ، اين روشها فاقد ظرافت و زيبايي نمايش ماتريسي هستند كه براي نخستين بار توسط Ullman در تحقيقش بر روي همريختي زير گرافها بكار برده شد. ثابت شده است ، كه عمل قرار دادن روش غير دقيق تطبيق گراف در قالب روش ماتريسي ، گمراه كننده و بي فايده است.
اين از زماني مايوس كننده بود كه مجموعهاي غني از ابزارهاي قوي در حوزه رياضيات با نام تئوري طيفي گراف در دسترس بود. اين اصطلاح به مجموعهاي از تكنيكها داده شد ، كه هدفشان مشخص كردن و نماياندن خصوصيتهاي جامع و سراسري ساختاري يك گراف با استفاده از مقادير ويژه و بردارهاي ويژه ماتريس نزديكي مي باشد. در متنهايي از علوم كامپيوتر ، كوششهايي براي استفاده از تئوري طيفي در تطبيق گراف ، تشخيص اشياء و قطعه بندي تصوير وجود دارد. Umeyama روش تجزيه اي دارد كه گرافهايي با اندازه يكسان را مطابقت دهي مي كند. Scott و Longuet-Higgins جزو اولين كساني بود كه با قرض گرفتن ايده هايي از شيمي ساختاري ، روشهاي طيفي را براي آناليز مطابقت بكار بردند. آنها نشان دادند كه چگونه مطابقتها از تجزيه تك مقداري بر روي ماتريس پيوستگي نقطه ، بين تصويرهاي مختلف بدست مي آيند. Shapiro و Brady از تئوري طيفي گراف كه Scott و Longuet-Higgins ارائه داده بودند فراتر رفتند ، كه در آن مجموعه نقاط ، با بردارهاي ويژه ماتريس مجاورت نقاط ، مطابقتدهي مي شوند. در اينجا ماتريس مجاورت با محاسبه فاصله بين نقاط با وزن دهي گوسي ، ساخته مي شود. بردارهاي ويژه ماتريس مجاورت ، ميتوانند به صورت بردارهاي پايه يك تبديل متعامد ، بر روي مختصات نقطه اوليه در نظر گرفته شوند. به عبارت ديگر مولفه هاي بردارهاي ويژه ، نشان دهنده آم يختهاي از زاويه ها ، براي نقطه هاي تبديل يافته هستند. بررسي مطابقت دهي ، در واقع بين مجموعه نقاط مختلف تاثير گرفته از مقايسه الگوي بردارهاي ويژه در تصاوير مختلف مي باشند. روش Shapiro وBrady مي تواند به عنوان متدي كه به جاي فضاي ساختار در فضاي مقادير ويژهكار مي كند ، در نظر آيد. Horaud و Sossa روشي كاملا ساختاري را براي تشخيص ترسيمهاي خطيبكار بردند. روش ارائه شده آنها بر اساس چند جمله اي هاي اصلي ماتريس لاپلاسي در گراف اتصال خطي است. با مقايسه ضرايب چند جمله اي ها ، آنها قادر خواهند بود كه پايگاه اطلاعاتي بزرگي از
ترسيمات خطي را طبقهبندي و انديسدهي كنند. Dickinson ، Shokoufandeh و Siddiqi نشان دادند كه به منظور تشخيص شكل از يك پايگاه اطلاعاتي بزرگ ، چگونه مي توان گرافها را بوسيله طيف توپولوژيكي محلي شان كد گذاري كرد.
در يك مقاله جديد Luo و Hancock به روش Umeyama برگشتند و نشان دادند كه چگونه مي توان اين روش را در برابر تغييرات و اندازه گراف و خطاهاي ساختاري مقاوم ساخت. آنها از يك توزيع برنولي براي خطاهاي مطابقت شروع كردند و الگوريتمي را بوجود آوردند كه مقدار اميد رياضي براي مطابقتدهي گراف را ماكزيمم ميكند. مطابقتها در مرحله M يا مرحله بيشينهسازي الگوريتم با اجراي تجزيه تك مقداري بر روي حاصل وزني ماتريسهاي مجاورت براي گرافهاي در حال تطبيق ، بدست مي آيند. در مرحله E يا مرحله مقدار منتظره ماتريس وزني ، تطابق وزني ماتريس به روز مي شود. به هر حال از آنجا كه اين روش داراي تكرار است روشي نسبتا كند و حساس به مقداردهي اوليه مي باشد.
هدف در اين بخش اين است كه از ساختار ويژه ماتريس مجاورت براي تطبيق گرافها با استفاده از يك متد جستجو بجاي روش تكرار استفاده شود. براي انجام اين كار ما به سراغ تئوري زنجيره هاي ماركوف مي رويم. يك زنجيره ماركوف را در نظر ميگيريم كه ماتريس احتمال انتقال آن ، ماتريس نرمال شده و كناره وزين گراف ميباشد. پيمايش تصادفي پيوسته براي زنجيره ماركوف روي گراف ، بوسيله بردارهاي ويژه هادي انتقال ماتريس كناره وزين انجام ميشود. به اين ترتيب با در نظر گرفتن ترتيب گرههاي تعريف شده بوسيله بردارهاي ويژه ما مي توانيم گراف را به رشته تبديل كنيم. اين امكان مطابقت دهي گراف را با به انجام رساندن تطبيق رشته بوسيله كمينه كردن فاصله لونشتين يا فاصلهويرايش انجام مي دهيم. ما مي توانيم از Wagner پيروي كنيم و از برنامه نويسي ديناميكي برايارزيابي فاصله ويرايش بين رشتهها استفاده كنيم و به اين ترتيب ميزان مطابقت را بدست آوريم. بايد به اين نكته تاكيد كنيم كه اگر چه تلاشهايي براي تعميم ايده ويرايش رشته به درختها و گرافها صورت گرفته است ، اما هنوز كار و زحمت قابل توجهي در جريان است با اين هدف كه متدولوژي لحاظ شده بر روي شالودهاي دقيق و استوار گذاشته شود. بعنوان مثال Bunke و همكارانش ارتباط بين فاصله ويرايش گراف با اندازه بزرگترين زير گراف مشترك را نشان دادند.
2-3) فاصله ويرايشي رشته :
با بدست آوردن بردارهاي ويژه ماتريسهاي مجاورت در گراف داده و گراف مدل ، ما دو گراف را به دو رشته تبديل كردهايم. قصد ما در اين بخش آن است كه كشف كنيم كه آيا مي توانيم وقتي گرافها به اين شكل نمايش داده شوند از فاصله ويرايش رشته ، براي تطبيق دهي مقاوم در برابر خطاي گرافها استفاده كنيم؟ فرض اينكه X و Y دو رشته با نمادهايي از الفباي ∑ باشند. ما مي خواهيم طي يك دنباله مرتب از عمليات X را به Y تبديل كنيم. به شكلي كه هزينه مربوط به دنباله حداقل شود.

قیمت 25 هزار تومان

خرید فایل pdf به همراه فایلword

قیمت:35هزار تومان