daftar kata terpanjang dengan huruf awal dan akhir yang cocok

Teman saya memberi saya masalah yang menurutnya mudah, tetapi saya tidak dapat menemukan algoritma yang baik untuk melakukannya.

Anda diberi input 100 kata bahasa Inggris acak. Anda harus menemukan string kata terpanjang di mana huruf terakhir dalam satu kata cocok dengan huruf pertama di kata berikutnya. Anda hanya dapat menggunakan setiap kata satu kali.

Misalnya, jika Anda diberi kata "cat", "dog", "that", string terpanjang yang bisa Anda buat adalah "cat -> that". Jika Anda diberi kata "mouse", "moose", "unicorn", string terpanjang yang dapat Anda buat hanyalah satu kata (karena tidak satu pun dari kata-kata itu terhubung). Jika Anda diberi kata "burung", "hidangan", "harb", string terpanjang yang bisa Anda buat adalah "harb -> bird -> dish" (atau "dish -> harb -> bird" atau "bird - > hidangan -> harb ").

Saya datang dengan ide pemodelan ini sebagai grafik siklik diarahkan. Setiap simpul hanya akan menjadi kata, dengan simpul menuju setiap kata / simpul yang dimulai dengan huruf yang diakhiri dengan kata ini.

+-------+         \ +------+
|  cat  |-----------| that |
+-------+         / +------+
    |                  |
   \|/                 |
+-------+ /            |
|  the  |--------------+
+-------+ \

Masalah ini tampaknya merupakan pencarian jalur terpanjang , yaitu NP-Hard.

Apakah ada cara yang lebih baik untuk melakukannya? Atau bahkan semacam algoritma perkiraan yang bisa digunakan? Atau beberapa cara untuk mengeksploitasi kualitas bahasa Inggris untuk mengurangi ruang pencarian?

Saya pikir ini terkait dengan masalah jalur terpanjang (LP) yang Anda sebutkan, tapi ini sedikit berbeda. Perbedaan utama adalah bahwa masalah LP memiliki tingkat konektivitas yang lebih tinggi daripada apa yang masalah Anda sarankan. Dengan membatasi koneksi Anda ke huruf terakhir dan pertama, Anda menghapus banyak kombinasi potensial.

Inilah cara saya akan merekomendasikan menangani yang ini:

1. Untuk setiap kata dalam daftar, hitung kemungkinan koneksi masuk dan keluar.
2. Buang kata-kata yang mengandung 0 in dan 0 out.
3. Identifikasi set awal "kata-kata pembuka" dengan jumlah seluk beluk terendah, dan seluk harus lebih besar dari 0.
4. Setiap kata pembuka menerima copy pekerjaan penghitungan koneksi seluk-beluknya sendiri. Ini membentuk kepala rantai.
5. Untuk setiap rantai, identifikasi daftar "kata-kata berikutnya" berdasarkan:
   
   • huruf terakhir starter atau kata sebelumnya
   • jumlah koneksi seluk beluk terendah (sekali lagi, beluk harus lebih besar dari 0)
6. Untuk masing-masing next word, ulangi langkah 5 hingga rantai berakhir.

Ingatlah bahwa:

• Anda harus melacak panjang rantai dan memiliki beberapa mekanisme global untuk mengidentifikasi rantai terpanjang.

• Anda juga harus menghapus setiap kata dari copy pekerjaan penghitungan koneksi untuk menghindari loop rekursif.

• Pada titik tertentu, rantai Anda akan berakhir dan Anda harus memilih kata dengan jumlah koneksi keluar 0.

• Anda mungkin harus menghitung ulang seluk beluk karena kata-kata dihapus dari daftar kerja. Pada pandangan pertama, saya tidak berpikir ini akan diperlukan karena set keseluruhan akan relatif kecil. Jika Anda menskala hingga 1000 kata, maka penghitungan statis dapat memperlambat algoritme dari konvergensi.

Saya melihat ini sebagai masalah pengepakan. Bagi saya, koneksi masuk dan keluar mengidentifikasi bentuk yang akan dikemas. Semakin rendah koneksinya, semakin aneh bentuknya. Semakin aneh bentuknya, semakin cepat saya ingin mengemasnya karena saya merasa semakin kecil kemungkinannya untuk mengemas bentuk aneh, kemudian saya masuk ke rantai.

Sebagai contoh:

{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this

Jika Anda membuat 26X26 matriks untuk mewakili grafik vertex yang diarahkan karena setiap alfabet dan kata-kata sebagai tepi. Misalnya kata - APPLE menghubungkan simpul A dan E dengan tepi diarahkan dari A ke E. Sekarang masalahnya berkurang untuk menemukan jejak Euler terbesar (jalur yang mencakup jumlah tepi maksimum, mengunjungi setiap tepi sekali dengan kemungkinan pengulangan simpul) dalam grafik. Salah satu algoritma O (E) akan memulai secara acak dari sepasang simpul. Temukan jalan di antara mereka. Daripada tetap santai jalan sampai mungkin.

update @ GlenH7 Saya memecahkan pertanyaan serupa di www.hackerearth / jda baru-baru ini, ada nilai relatif sehubungan dengan solusi terbaik dan saya mencetak nilai tertinggi dengan pendekatan berikut-

Diberikan daftar kata. Temukan rantai terpanjang yang bisa dibentuk oleh mereka. Rantai valid jika setiap kata dimulai dengan huruf * berakhir pada akhir kata terakhir.

Approch =

1) menjadikan grafik huruf sebagai simpul dan kata sebagai ujung. Di tempat menggunakan beberapa tepi gunakan satu dengan berat sama dengan jumlah tepi.

2) menemukan komponen grafik yang sangat terhubung dengan tepi maksimum. Buang sementara tepi yang lain untuk sementara.

3) Untuk setiap titik membuat indegree-nya sama dengan outdegree-nya.

4) Sekarang ada sirkuit eulerian mereka dalam grafik. Temukan.

5) Sekarang dalam grafik yang tersisa (grafik orignal wrt menemukan jejak terpanjang dengan simpul pertama dalam komponen yang terhubung sangat kuat. Saya pikir ini sulit NP.

6) Sertakan jejak di atas dalam sirkuit Elerian yang mengubah sirkuit euler menjadi jejak.

Mengapa - Saya menerima bahwa pertanyaan ini kemungkinan besar adalah NP sulit (tebak, tidak berbicara secara matematis). Tetapi pendekatan di atas bekerja paling baik ketika ada daftar panjang (1000+) dari kata-kata yang terdistribusi secara seragam (yaitu tidak dimaksudkan sebagai wc untuk pendekatan di atas). Mari kita asumsikan bahwa setelah mengonversi daftar yang diberikan ke grafik yang disebutkan di atas, untungnya ternyata itu adalah grafik euler (lihat http://en.wikipedia.org/wiki/Eulerian_path untuk kondisi), maka tanpa ragu kita dapat mengatakan jawaban itu pertanyaan di atas adalah P dan sebenarnya adalah jalur euler dalam grafik (lihat http://www.graph-magics.com/articles/euler.php untuk pendekatan yang sangat sederhana untuk melakukannya dan lihat ini untuk memverifikasi bahwa grafik Anda memiliki single http://www.geeksforgeeks.org/strongly-connected-components/dan jika tidak sementara membersihkan scc kecil lainnya karena jalur euler ada untuk scc tunggal). Jadi untuk kasus yang tidak beruntung (yang hampir semua kasus) saya mencoba mengubahnya menjadi kasus yang beruntung (yaitu kondisi jejak Euler terpenuhi). Bagaimana cara melakukannya? Saya mencoba melakukan peningkatan pencarian kedalaman untuk tepi yang tidak relevan (himpunan tepi dalam jalur yang memandang dari vertex dengan outdegree lebih besar dari indegree dan berakhir di vertex dengan indegree lebih besar dari outdegree). Meningkatkan pencarian kedalaman berarti bahwa pertama saya mencari semua set satu sisi di jalur daripada dua tepi di jalur dan sebagainya. Mungkin tampak pada pandangan pertama bahwa pencarian kedalaman akan mengambil O (node ​​^ i) sehingga total kompleksitas waktu dari O (node ​​+ node ^ 2 + node ^ 3 + ....) sampai itu adalah kasus yang beruntung. Tetapi analisis diamortisasi akan bersenang-senang itu adalah O (tepi). Setelah itu dikurangi kasus beruntung menemukan sirkuit euler.

Sampai di sini, itu semua waktu polinomial. Ini akan memberikan hampir solusi terbaik. Tetapi untuk lebih meningkatkan solusi Anda (solusi sempurna adalah NP sulit) coba beberapa pendekatan serakah dalam grafik yang tersisa untuk menemukan jejak panjang menatap dengan salah satu simpul dalam scc yang dipilih. Sekarang tambahkan ini ke jejak eulerian yang ditemukan di atas untuk lebih meningkatkannya.

Ide:

Pertama, buat dua peta (hash), katakanlah, S, dan E, dari huruf alfabet ke kata; yang pertama, S, memetakan huruf mulai kata-kata, yang kedua, E, melakukan hal yang sama dengan huruf berakhir.

Misalnya, jika kamus dibuat dari:

burung, hidangan, anjing, harb

kita punya:

S:

a -> [ ]
b -> [ bird ]
c -> [ ]
d -> [ dish, dog ]
...
h -> [ harb ]
...

dan,

E:

a -> [ ]
b -> [ harb ]
c -> [ ]
d -> [ bird ]
...
g -> [ dog ]
h -> [ dish ]
...

Selanjutnya, menggunakan S dan E untuk pencarian cepat, buat hutan (kumpulan pohon), dengan ukuran yang sama dengan kamus, dengan akar di setiap kata, dan tidak memungkinkan kata muncul lebih dari satu kali di pohon - cache kedalaman pohon saat Anda membangunnya:

bird (depth: 2)
   dish
      harb
   dog

dish (depth: 3)
   harb
      bird
         dog

dog (depth: 0)

harb (depth: 2)
   bird
      dish
      dog

Akhirnya, beralihlah ke hutan dan temukan pohon yang paling dalam.

Solusinya adalah pada sumbu keturunan pohon-pohon itu.

Misalnya,

dish / harb / bird / dog

atas.