Sub selanjutnya

Sebuah string memiliki urutan, tetapi biasanya tidak semuanya berbeda. Apa kompleksitas menemukan frekuensi maksimum dari setiap urutan? $2^n$

Sebagai contoh, string "urutan" berisi 7 salinan dari urutan "menuntut" dan ini adalah maksimum.

Contoh kode brute-force di http://ideone.com/UIp3t

Apakah ada teorema struktural yang terkait? Keduanya ternyata salah :

urutan frekuensi maksimum terpanjang adalah unik
frekuensi maksimum dari setiap panjang adalah unimodal dalam $k$ $k$

Tautan yang mungkin terkait:

Menghitung # urutan berbeda http://11011110.livejournal.com/254164.html $\in \mathbf{P}$
Masalah kontes terkait untuk berbagai sumber http://www.spoj.pl/problems/CSUBSEQS/
Makalah terkait http://dx.doi.org/10.1016/j.tcs.2008.08.035

Sunting 10 hari kemudian: terima kasih telah melihatnya! Saya bertanya-tanya apakah ini akan membuat masalah kontes pemrograman polinomial waktu yang bagus. Saya kira tidak, tetapi saya berharap untuk memikirkannya lagi nanti.

ds.algorithms string-search daveagp
sumber

Sebuah pertanyaan awal yang mungkin naif: apakah sudah jelas bahwa masalah ini bahkan ada di NP ? Dengan kata lain: untuk masalah menentukan apakah ada urutan dengan paling tidak k kejadian dalam string n -character, seperti apa sebuah sertifikat? Sebagai contoh, mendaftar semua tupel indeks yang mengindikasikan contoh dari contoh yang diberikan akan gagal menjadi ukuran polinomial untuk string aaa ... aa (yang, sementara input yang membosankan, tetap memiliki substring dengan kira-kira kejadian).

n C (n / 2)

$n \mathbf C (n/2)$

Niel de Beaudrap

@Niel de Beaudrap: Saya pikir kita dapat menghitung jumlah kemunculan sebagai hasil dalam waktu polinomial dengan pemrograman dinamis, sehingga memungkinkan untuk menggunakan susunan itu sendiri sebagai sertifikat.

Tsuyoshi Ito

Saya agak bingung: apakah pertanyaan "diberikan string, temukan berikutnya yang terjadi jumlah maksimum kali?"

Suresh Venkat

@ SureshVenkat: Ya, itu pemahaman saya. Misalnya, diberi urutan X sebagai input, jawaban yang benar adalah urutan X.

n

$n$

n / 2

$n/2$

Jeffε

@ marzio-de-biasi: pertanyaan yang Anda tautkan berbeda (dan jauh lebih mudah): di sana Anda diberi urutan berikutnya.

david

Jawaban:

dari pencarian, berikut adalah makalah dengan beberapa penelitian & temuan untuk penelitian tingkat pascasarjana tetapi (peringatan) tidak ada referensi. ia memiliki beberapa heuristik, perkiraan, hasil empiris & komentar tentang masalah dan beberapa ide untuk membuktikan kompleksitasnya (perkiraan) dll.

Identifikasi Penelusuran yang Paling Sering Dilakukan
CSE 549 Laporan Akhir Proyek Biologi Komputasi
Mikhail Bautin 2006

(Walaupun ada beberapa masalah standar urutan yang agak mirip & dipelajari misalnya dalam makalah Elzinga et al, apakah mungkin masalah urutan khusus ini belum terlalu banyak dipelajari?)

ay
sumber

Saya tidak mengerti mengapa ini diturunkan. Ini mungkin bukan makalah yang sangat mendalam tetapi tampaknya langsung pada topik.

David Eppstein

fyi / addendum Bautin juga mengatakan pada akhir makalah ia memiliki 5K baris C ++ & kode Python pada masalah / kertas untuk siapa pun yang tertarik

vzn

@ David, saya tidak berpikir downvote adalah karena kertas yang ditautkan, mungkin lebih berkaitan dengan fakta bahwa jawaban ini terlihat seperti (pada dasarnya) jawaban satu baris tautan (tanpa menjelaskan bagaimana kertas itu terkait dengan pertanyaan dan menjawabnya). Ini mungkin lebih cocok sebagai komentar.

Kaveh

ok kaveh, kemudian, dijabarkan: makalah ini tampaknya mengungkapkan (kecuali ada yang bisa menemukan ref yang lebih baik atau muncul dengan bukti masalah sulit ini sendiri) bahwa kompleksitas masalah yang sebenarnya sejauh ini tidak diketahui / terbuka (selain yang jelas PSpace / ExpTime) dan mungkin berisi analisis / pendekatan yang paling dikenal untuk menyelesaikannya sejauh ini

vzn

Saya memang menemukan makalah ini sebelumnya dan meminta maaf karena tidak menautkannya di atas, yang karena saya pikir itu tidak memberikan banyak informasi konkret. Saya mengirim email kepada penulis beberapa waktu lalu menanyakan apakah ada lagi yang bisa dia katakan tentang apa pun yang terjadi sejak ditulis, tetapi belum mendapat jawaban.

daveagp

Bukan jawaban, hanya lemma.

Jadi pertama-tama orang mungkin bertanya-tanya seperti apa string yang paling umum seperti 12..t12..t12..t .. adalah. Setelah berpikir sedikit orang menyadari bahwa itu juga harus memiliki bentuk 12..t12..t12 .., hanya jelas lebih pendek. Jika string asli memiliki panjang nt, dan selanjutnya dari bentuk khusus ini memiliki panjang k, maka jumlah kemunculannya persis . Ini menyiratkan bahwa urutan paling umum juga berakhir dengan (yaitu harus dapat dibagi dengan ). Tapi di mana ini mengambil maksimum dan berapa ??? Cukup memalukan, tapi saya tidak bisa mengetahuinya ... ${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$ $t$ $k$ $t$

domotorp
sumber