الگوریتم هیرشبرگ: تفاوت میان نسخه‌ها

در [[علوم رایانه]], الگوریتم هیرشبرگ (به انگلیسی [[:en:Hirschberg's_algorithm|Hirschberg's Algorithm]]) [[الگوریتم|الگوریتمی]] [[برنامه‌ریزی پویا|پویا]] برای [[هم‌ترازسازی چند توالی|هم‌ترازسازی]] بهینه‌ی دو [[توالی]] است که دان هیرشبرگ (Dan Hirschberg) در سال‌ ۱۹۷۵ آن را ارائه کرد. <ref name=":0">{{یادکرد وب|نویسنده=|کد زبان=|تاریخ=|وب‌گاه=|نشانی=https://en.wikipedia.org/wiki/Hirschberg's_algorithm|عنوان=Hirschberg's Algorithm - Wikipedia}}</ref>

هوشمندی الگوریتم هیرشبرگ در استفاده از مشاهده‌های زیر است<ref>{{یادکرد کتاب|عنوان="A linear space algorithm for computing maximal common subsequences"|نام خانوادگی=Hirschberg|نام=.Dan S|ناشر=Communications of the ACM|سال=1975|شابک=|مکان=|صفحات=http://dl.acm.org/citation.cfm?doid=360825.360861}}</ref>:

# اگر <math>(align1Z, align2W) = OptAlign(Str1X, Str2Y)</math>هم‌ترازی سراسری بهینه‌ی [[رشته (علوم رایانه)|رشته‌]]<nowiki/>های Str1X و Str2Y باشد و <math>Str1X = Str1X^{leftl} + Str1X^{rightr}</math>تقسیم‌بندی دلخواهی از Str1X باشد, تقسیم بندی <math>Str2Y = Str2Y^{leftl} + Str2Y^{rightr}</math>از Str2Y وجود دارد که <math>(align1Z, align2W) = OptAlign(Str1X^{leftl}, Str2Y^{leftl}) + OptAlign(Str1X^{rightr}, Str2Y^{rightr})</math>.

[[شبه‌کد]]<ref name=":0" />:<syntaxhighlight>

[[شبه‌کد]]<ref name=":0" />:<syntaxhighlight>

این الگوریتم تنها <math>O(min\{m, n\})</math>حافظه نیاز دارد که بهینه‌تر از الگوریتم نیدلمن-وانچ (با حافظه <math>O(mn)</math>) است. <ref>{{یادکرد وب|نویسنده=|کد زبان=|تاریخ=|وب‌گاه=|نشانی=http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec02/node10.html|عنوان=http://www.cs.tau.ac.il/~rshamir/algmb/98/scribe/html/lec02/node10.html}}</ref>

== مثال <ref name=":0" /> ==