کوتاهترین ابر رشته (فصل 2)

مجموعه متناهی از الفبا و n رشته s_i از این الفبا داده شده، کوتاهترین رشته s را بیابید که همه ی رشته های s_i زیر رشته آن باشند. بدون از دست رفتن عمومیت مساله فرض کنید هیچ رشته ای زیر رشته ی دیگری نباشد.

راه حل حریصانه: دو رشته با بیشترین اشتراک را اول قرار بدهیم، بقیه رشته ها را چک کنیم و رشته ای که پیشوند آن با پسوند رشته ی فعلی اشتراک بیشتری دارد انتخاب کنیم و همین کار را ادامه بدهیم.

تحلیل: رشته ها را از نقاط اشتراک آنها با رشته ی بعدی بازه بندی می کنیم. در این صورت هر رشته به حداکثر سه زیر رشته تقسیم می شود: قسمتی که با رشته ی قبل از خود اشتراک دارد، قسمتی که با کسی اشتراک ندارد و قسمت بعد که با رشته ی بعدی خود اشتراک دارد. جوابی که برای هر رشته به دست می آید حداکثر دو برابر جواب بهینه ی این دو رشته است. (مثال حالت بد: سه رشته ی cb...b و b...ba و b...b را که طول مساوی دارند در نظر بگیرید، اگر دو رشته اول را به هم بچسبانیم و بعد رشته ی فقط b را بگذاریم جواب cb..bab...b است که دو برابر حالتی است که اول فقط b را به یکی از رشته های دیگر بچسبانیم یعنی cb..ba.)

از اینجا نتیجه می شود الگوریتم حریصانه ی قبلی ضریب 2 دارد و خوب نیست. حالا سعی می کنیم آن را بهبود بدهیم.

راه حل حریصانه 2: با حذف ترتیب انتخاب مجموعه ها می توانیم انتخاب حریصانه ی بهتری انجام بدهیم. همه ی ابررشته های ممکن را برای هر دو رشته ورودی حساب می کنیم (نه فقط دو تا ابر رشته ی بهینه ی آنها را، نمی دانم چرا؟؟).

طبق تعریف ابر رشته ی بهینه، همه ی رشته های دیگر زیر رشته ی آن هستند و این ابررشته کمترین طول را دارد. پس ما می توانیم هزینه ی هر ابررشته ی زوج رشته {همان اجزای مساله که می گفتم} را تعداد زیرمجموعه های آن بگیریم. با این کار هنگام ادغام دو جواب مرحله ی قبل، با اجتماع گرفتن مجموعه ها به مجموعه ای می رسیم که زیر رشته های رشته های سازنده ی چند ابررشته است.

پس به حالتی از مساله ی پوشش مجموعه ای رسیده ایم که تعدادی مجموعه داریم (ابر رشته ی زوج رشته ها) که شامل زیر رشته های این ابررشته ها هستند و می خواهیم مجموعه ی مرجع همه ی زیرمجموعه های همه ی رشته ها را بپوشانیم. هزینه ی هر مجموعه هم تعداد زیر رشته های درون آن است.

مساله ی پوشش مجموعه ای تعدادی از ابررشته ی زوج رشته ها را به ما بر می گرداند که کل مجموعه را پوشش می دهند. این ابررشته ها را به هم می چسبانیم.

(توی کتاب نگفته که چرا ابر رشته ها رشته مشترک ندارند یا اگر دارند چطور رشته های مشترک را حذف می کند و کاری می کند که یک رشته بیش از دو بار نیامده باشد.)

جواب نهایی شده ضرب ضریب تقریب این دو مساله: 2 * H(n)