Menemukan jarak antara dua polinomial (direpresentasikan sebagai pohon)

20

Seorang kolega yang bekerja pada pemrograman genetika menanyakan kepada saya pertanyaan berikut. Saya pertama kali mencoba menyelesaikannya berdasarkan pendekatan serakah, tetapi pada pemikiran kedua, saya menemukan contoh tandingan terhadap algoritma serakah. Jadi, saya pikir layak disebutkan di sini.

Pertimbangkan dua polinomial yang diwakili oleh pohon ekspresi mereka. Misalnya, x3-2x+1 dan x2+4 diilustrasikan di bawah ini:

Aturan:

  1. Setiap node adalah nama variabel ( x,y,z,... ), angka , atau operasi (+, -, ×).
  2. Traversal berurutan pohon harus menghasilkan polinomial yang valid.
  3. Node operasi memiliki derajat 2. Node lain memiliki derajat 0. Semua node memiliki derajat 1 (kecuali root, yang derajatnya 0).

Pada simpul N dari pohon, tentukan operasi dasar sebagai berikut:

  1. Operasi dasar dapat mengubah label node. Misalnya, x dapat diubah menjadi 3, atau + dapat diubah ke × .
  2. Operasi dasar dapat membangun pohon ekspresi di atas N (lihat contoh di bawah).

Biaya operasi dasar tipe 1 adalah 1. Biaya untuk tipe 2 sama dengan jumlah operasi {+, -, ×} di pohon ekspresi yang baru dibangun.

Contoh untuk tipe 2: Biaya operasi dasar berikut adalah 2, karena pohon ekspresi dibangun di atas simpul N menggunakan dua operasi (- dan ×).

Biarkan T1 dan T2 menjadi dua pohon ekspresi yang mewakili polinomial. Tentukan jarak T1 dan T2 sebagai berikut: biaya minimum operasi dasar untuk mengkonversi T1 ke T2. Perhatikan bahwa kami tidak memerlukan pohon yang dikonversi untuk memiliki struktur yang sama dengan T2. Kami hanya ingin menghitung polinomial yang sama dengan T2. (Lihat komentar sebagai contoh.)

Masalahnya: Diberikan T1 dan T2, sajikan algoritma yang menghitung jaraknya.

Contoh 1: Misalkan T1 dan T2 adalah dua pohon yang diilustrasikan di awal posting ini. Untuk mengonversi pohon kanan ke pohon kiri, seseorang dapat membangun pohon biaya 3 di atas ×, dan mengubah 4 ke 1 (total biaya adalah 4).

x4x4+4x3+6x2+4x+1x(x+1)4x4x36x24x

ds.algorithms tree ai.artificial-intel genetic-programming MS Dousti
sumber
2
Jika operasi "hapus" tidak diizinkan, maka jaraknya bukan jarak. Sebagai contoh: pohon T1 = (x * x) +4 tidak dapat ditransformasikan menjadi T2 = x, tetapi T2 dapat ditransformasikan ke T1 menambahkan (* x) dan kemudian (+4) di atas x. Apakah itu oke? Atau Anda harus menentukan jarak sebagai operasi minum yang diperlukan untuk mengubah T1 ke T2 atau T2 ke T1.
Marzio De Biasi
4
Biaya sama dengan 0 jika dan hanya jika dua rumus aritmatika yang diberikan (bebas divisi) mewakili polinomial yang sama. Jika saya mengingatnya dengan benar, ini adalah masalah khas dalam coRP (dengan penugasan acak) yang tidak diketahui berada di P.
Tsuyoshi Ito
4
@ Tsuyoshi: Oh, begitu. Anda menunjuk pada masalah pengujian identitas polinomial . (Referensi yang bagus: [1 ] dan [2 ]). Saya harus memikirkan ini. Sementara itu, semua saran diterima.
MS Dousti
4
Ya itu saja. Tampaknya dalam versi khas masalah pengujian identitas polinomial, dua polinomial input diberikan sebagai sirkuit, bukan rumus. Jadi kata-kata saya bahwa versi formula "khas" mungkin tidak akurat. Pokoknya menempatkan bahkan versi rumus di P tampaknya menjadi masalah terbuka.
Tsuyoshi Ito
2
@Vor: Dalam formulasi saat ini, input T1 benar-benar sebuah pohon dan input T2 adalah polinomial yang kebetulan diberikan sebagai pohon, dalam arti berikut. Mengubah T1 ke pohon berbeda yang mewakili polinomial yang sama dapat mengubah jawabannya secara umum, sedangkan mengubah T2 dengan cara yang sama tidak.
Tsuyoshi Ito

Jawaban:

10

Tree Edit Distance adalah generalisasi jarak edit string. Jarak antara dua pohon adalah jumlah minimum penyisipan simpul \ penghapusan \ dan relabel yang diperlukan untuk mengubah satu pohon menjadi yang lain. (ketika kita menghapus simpul v, anak-anak v menjadi anak-anak dari orang tua (v)). Masalahnya adalah NP-hard ketika pohon tidak teratur, tetapi ketika mereka dipesan (yaitu, ada urutan kiri-ke-kanan di antara saudara kandung) masalahnya diselesaikan dalam waktu O (n ^ 3) waktu (seperti dalam kertas yang Sadeq disebutkan). Sebuah survei bagus yang menggambarkan hal ini: http://portal.acm.org/citation.cfm?id=1085283

Aviv
sumber
1
Terima kasih Aviv. Akan sangat bagus jika Anda menggabungkan respons Anda (saya pikir Anda memiliki masalah dalam menggunakan akun Anda sebelumnya). Anda dapat menggunakan saran dalam posting ini (Khususnya, tautan ini ).
MS Dousti
Bagaimana pendekatan ini mencakup pohon-pohon yang berbeda dengan polinomial ekivalen
narek Bojikian