Diberikan beberapa fragmen string, saya ingin mencari string tunggal yang sesingkat mungkin ("string keluaran") yang berisi semua fragmen. Fragmen dapat saling tumpang tindih dalam string output.
Contoh:
Untuk fragmen string:
BCDA
AGF
ABC
String output berikut berisi semua fragmen, dan dibuat oleh penambahan naif:
BCDAAGFABC
Namun string output ini lebih baik (lebih pendek), karena mempekerjakan tumpang tindih:
ABCDAGF
^
ABC
^
BCDA
^
AGF
Saya mencari algoritme untuk masalah ini. Tidak sepenuhnya penting untuk menemukan string keluaran yang paling pendek, tetapi semakin pendek semakin baik. Saya mencari algoritma yang lebih baik daripada yang naif yang akan mencoba menambahkan semua permutasi dari fragmen input dan menghapus tumpang tindih (yang tampaknya NP-Lengkap).
Saya sudah mulai mengerjakan solusi dan terbukti cukup menarik; Saya ingin melihat apa yang mungkin muncul dari orang lain. Saya akan menambahkan pekerjaan saya dalam proses untuk pertanyaan ini sebentar lagi.
sumber
Jawaban:
Apa yang Anda tanyakan adalah masalah Shortest Common Superstring, yang tidak ada algoritma yang berfungsi untuk semua kasus. Tetapi ini adalah masalah umum (dalam kompresi dan sekuensing DNA) dan beberapa algoritma aproksimasi sudah terkenal.
Algoritma "serakah" umumnya diterima sebagai yang paling efektif (seperti, mereka memiliki kasus terburuk paling buruk).
Bacalah makalah Algoritma Aproksimasi untuk Masalah Superstring Terpendek oleh Jonathan Turner untuk informasi lebih lanjut.
sumber