Fungsi potensial pohon hamparan: mengapa menjumlahkan log dari ukuran?

Saya mengajar kursus tentang struktur data dan akan mencakup pohon splay awal minggu depan. Saya telah membaca makalah tentang hamparan pohon berkali-kali dan saya akrab dengan analisis dan intuisi di balik struktur data. Namun, saya tidak bisa menemukan intuisi yang kuat untuk fungsi potensial yang digunakan Sleator dan Tarjan dalam analisis mereka.

Analisis ini bekerja dengan menetapkan setiap elemen dalam pohon bobot yang berubah-ubah dengan , kemudian mengatur ukuran dari sebuah simpul menjadi jumlah bobot dari simpul-simpul dalam subtree yang berakar pada . Mereka kemudian mengambil log dari nilai ini untuk mendapatkan peringkat dari node, jadi . Akhirnya, fungsi potensial dari pohon didefinisikan sebagai jumlah dari peringkat semua node. $w_i$ $s(x)$ $x$ $r(x)$ $r(x) = \log s(x)$

Saya mengerti bahwa fungsi potensial ini bekerja dengan benar dan saya dapat mengikuti analisis, tetapi saya tidak melihat mengapa mereka memilih potensi ini. Gagasan menetapkan ukuran untuk setiap node masuk akal bagi saya, karena jika Anda meringkas ukuran, Anda mendapatkan panjang jalur tertimbang pohon. Namun, saya tidak tahu mengapa mereka memutuskan untuk mengambil log bobot dan kemudian menyimpulkannya - saya tidak melihat properti alami dari pohon yang sesuai dengan ini.

Apakah fungsi potensial dari pohon hamparan sesuai dengan beberapa sifat alami pohon? Adakah alasan tertentu, selain "berhasil", bahwa mereka akan memilih potensi ini? (Saya secara khusus ingin tahu karena rangkaian kursus ini menyebutkan bahwa "analisis adalah ilmu hitam. [N] o ide bagaimana menemukan")

Terima kasih!

ds.data-structures intuition amortized-analysis templatetypedef
sumber

Saya pernah mendengar penjelasan "ini ilmu hitam" sebelumnya. Apakah Anda mencoba mengirim email ke Sleator dan Tarjan?

jbapple

@ jbapple Saya belum mengirim email kepada mereka, karena saya berharap bahwa "komunitas pada umumnya" akan dapat membantu. Saya juga membayangkan bahwa melakukan ping pada seseorang tentang pekerjaan yang mereka lakukan 30 tahun yang lalu mungkin belum tentu mendapat respons. :-)

templatetypedef

Saya tidak sangat akrab dengan hal itu, tapi aku hanya melihat kertas yang sangat kasar, saya pikir satu-satunya alasan adalah bahwa mereka ingin memiliki perubahan kecil dengan fungsi potensial setelah operasi melebarkan, misalnya jika kita mengganti

dengan

atau dengan

sepertinya masih semuanya bekerja dengan baik (saya tidak membuktikannya tetapi tampaknya hanya perlu mathwork sederhana). Tetapi jika kita membiarkannya sebagai

, maka amortisasi itu menganalisis sementara itu benar, tetapi itu bukan upperbound yang baik (sesuatu seperti

). Ini tidak terkait dengan properti pohon sama sekali.

\log

$\log$

\log \log

$\log\log$

l o g^{*}

$log^*$

s

$s$

(m + n)^{2}

$(m+n)^2$

Saeed

Saya selalu mengotakkan pangkat x sebagai "kedalaman pohon pencarian biner ideal yang berisi turunan x", tapi itu lebih merupakan mnemonik daripada intuisi yang berguna.

Jeffε

Jawaban:

Cara membuat potensi jumlah log

Mari kita pertimbangkan algoritma BST yang untuk setiap akses untuk elemen , ia hanya mengatur ulang elemen dalam path pencarian dari disebut before-path, menjadi beberapa pohon yang disebut after-tree. Untuk setiap elemen , biarkan dan menjadi ukuran subtree berakar pada sebelum dan sesudah penataan ulang masing-masing. Jadi dan dapat berbeda jika $A$ $x$ $P$ $x$ $a$ $s(a)$ $s'(a)$ $a$ $s(a)$ $s'(a)$ $a \in P$ .

Apalagi, $A$ hanya mengatur ulang banyak elemen secara konstan di jalur pencarian kapan saja. Sebut saja jenis algoritme "lokal" ini. Misalnya, pohon splay adalah lokal. Ini mengatur ulang hanya paling banyak 3 elemen sekaligus dengan zig, zigzig dan zigzag.

Sekarang, setiap algoritma lokal yang membuat "banyak" daun di after-tree, seperti splay tree, memiliki properti bagus berikut.

Kita bisa membuat pemetaan sedemikian rupa $f: P \rightarrow P$

Ada linear banyak , di mana . $a \in P$ $s'(f(a)) \le s(a)/2$

Ada terus banyak , di mana bisa besar tapi sepele paling $a \in P$ $s'(f(a))$ $n$ .

Elemen-elemen lain , . $a \in P$ $s'(f(a)) \le s(a)$

Kita bisa melihat ini dengan membuka perubahan jalur pencarian. Pemetaan ini sebenarnya cukup alami. Makalah ini, A Global Geometric View of Splaying , tepatnya menunjukkan detail cara melihat pengamatan di atas.

Setelah mengetahui fakta ini, sangat wajar untuk memilih potensi jumlah log. Karena kita dapat menggunakan potensi perubahan elemen tipe-1 untuk membayar seluruh penataan ulang. Selain itu, untuk elemen tipe lain, kita harus membayar perubahan potensial paling banyak dengan logaritmik. Oleh karena itu, kita dapat memperoleh logaritma biaya diamortisasi.

Saya pikir alasan mengapa orang berpikir ini adalah "ilmu hitam" adalah bahwa analisis sebelumnya tidak "membuka" perubahan keseluruhan jalur pencarian, dan melihat apa yang sebenarnya terjadi dalam satu langkah. Sebaliknya, mereka menunjukkan perubahan potensi untuk setiap "transformasi lokal", dan kemudian menunjukkan bahwa perubahan potensial ini dapat secara teleskopik ajaib.

PS Makalah ini bahkan menunjukkan beberapa batasan jumlah potensial log. Artinya, seseorang dapat membuktikan kepuasan akses lemma melalui jumlah log-potensial hanya untuk algoritma lokal.

Interpretasi jumlah total log

Ada cara lain untuk menentukan potensi BST dalam makalah Georgakopoulos dan McClurkin yang pada dasarnya sama dengan jumlah total log dalam kertas Sleator Tarjan. Tetapi ini memberikan intuisi yang baik untuk saya.

$w(u)$ $u$ $W(u)$ $u$ $u$ subtree ketika berat setiap node adalah satu.)

Sekarang, alih-alih mendefinisikan peringkat pada node, kami menentukan peringkat ke tepi, yang mereka sebut faktor kemajuan .

hal f (e) = catatan (W (kamu) / W (v)) .

$pf(e)=\log(W(u)/W(v)).$

Dan potensi pohon $S$ adalah

Φ (S) = \sum_{e \in S} hal f (e) .

$\Phi(S) = \sum_{e\in S} pf(e).$

Potensi ini memiliki interpretasi alami: jika selama pencarian kita melewati batas $(u,v)$ kami mengurangi ruang pencarian dari keturunan $u$ untuk keturunan $v$ , pengurangan sedikit dari $W(u)/W(v)$ . Faktor kemajuan kita adalah ukuran logaritmik dari 'kemajuan' ini, karena itu namanya. [Dari Bagian 2.4]

Perhatikan bahwa ini hampir sama dengan potensi Sleator Tarjan, dan merupakan tambahan pada jalur.

sunting: Ternyata definisi alternatif ini dan intuisi di baliknya telah dijelaskan sejak lama oleh Kurt Mehlhorn. Lihat bukunya "Struktur Data dan Algoritma" Volume I, Bagian III. 6.1.2 Splay Trees, halaman 263 - 274.

Thatchaphol
sumber