วันนี้จะขอเปิดหัวข้อใหม่ ซึ่งเป็นหัวข้อที่ผมกำลังศึกษาอยู่ เลยอยากมาเขียนไว้ให้ดูกันและเพื่อความเข้าใจของตัวผมเองด้วย เป็นเรื่องเกี่ยวกับ SSP: Shortest Superstring Problem.

Problem: String ในที่นี้จะหมายถึงสายอักขระ หรือก็คือลำดับของอักขระ (Character) สำหรับตัวปัญหาก็คือ หากเรามีเซตของ string หลายๆตัว เราต้องการจะหา string หนึ่งตัวที่ครอบคลุม string ทุกตัวในเซตนั้น โดยมีความยาวสั้นที่สุดที่เป็นไปได้ จะทำอย่างไร?

ปัญหานี้รู้กันอยู่ว่าเป็นปัญหาประเภท NP-hard การค้นคว้าวิจัยจึงมุ่งไปที่การแก้ปัญหาแบบ Approximationซึ่งเราจะค่อยๆติดตามไป

Preliminaries: ให้ $S={s_(1),...,s_(m)}$ เป็นเซตของ string โดยเราสมมติให้ $S$ เป็น substring-free คือไม่มี $s_(i)inS$ เป็น substring ของ string $s_(j)inS$ เมื่อ $i!=j$
เราจะเรียก string $s$ ว่าเป็นcommon superstring ของ $S$ ถ้าสำหรับแต่ละ $s_(i)inS$, $s$ สามารถเขียนเป็น $u_(i)s_(i)v_(i)$ สำหรับบาง $u_(i)$,$s_(i)$ เราจะให้ $n=OPT(S)$ เป็นความยาวของ common superstring ที่สั้นที่สุดของ $S$ จุดมุ่งหมายของเราคือจะหา common superstring ของ $S$ ที่มีความยาวใกล้ $n$ ให้มากที่สุดเท่าที่ทำได้

เอาไว้แค่นี้ก่อนดีกว่า ใครคิดวิธีดีๆออก ผมก็น้อมรับข้อเสนอครับ