فرض کنید میخواهیم یک متن را از فارسی به انگلیسی ترجمه کنیم. یک راه برای این کار این است که داده‌ساختاری داشته باشیم تا معنی کلمات را در آن جستجو کنیم. برای این کار می‌توانیم از یک درخت سیاه و سفید استفاده کنیم که ارتفاع دورترین راس آن به ریشه از
$O(\lg n)$
باشد. اما امکان دارد که کلمات پراستفاده مانند «برای» در راس‌های پایین‌تر بیایند و در مقابل کلماتی مانند «قسطنطنیه» در راس‌های بالاتر بیایند و این روش بهینه نیست و کار جستجو را کند می‌کند. حتی برای اینکه درخت ما بهینه باشد، دلیلی ندارد که ارتفاع درخت ما کمینه باشد.
به درختی که بهترین زمان جستجو را بدهد، درخت جستجوی بهینه می‌گویند. به زبان ریاضی، فرض کنید یک دنباله‌‌ی مرتب‌شده (از کوچک به بزرگ)
$ K = \langle k_1, k_2, \dots, k_n \rangle $
با
$n$
کلمه برای جستجو را در نظر بگیرید. ما میخواهیم درخت جستجویی با این کلمات بسازیم و می‌دانیم که احتمال اینکه در این درخت، جستجویی به دنبال کلمه‌ی
$k_i$
انجام شود برابر
$p_i$
است.
همچنین امکان دارد بعضی از جستجوها نتیجه‌ای نداشته باشند. پس باید
$n+1$
«رأس مصنوعی» نیز داشته باشیم که آن‌ها را با
$d_0, d_1, \dots, d_n$
نشان می‌دهیم.
$d_0$
یعنی تمام مقادیر کوچکتر از
$k_1$
و
$d_n$
یعنی تمام مقادیر بزرگ‌تر از
$k_n$
و باقی مقادیر
$d_i$
نشان‌دهنده‌ی کلمات بین
$k_i$
و
$k_{i+1}$
است.
برای هر رأس مصنوعی، احتمال اینکه جستجویی برای آن انجام گیرد نیز برابر
$q_i$
است. پس می‌دانیم:
$$ \sum_{i=1}^{n} p_i + \sum_{i=0}^{n} q_i = 1 $$
در نتیجه امیدریاضی (به زبان ساده، همان مقدار متوسط) هر جستجو در یک درخت، به شکل زیر محاسبه می‌شود و درخت جستجوی بهینه درختی است که این مقدار در آن کمینه باشد. (
$\text{depth}(k_i)$
را فاصله‌ی رأس حاوی
$k_i$
از ریشه بگیرید.):
$$ E[\text{search cost}] = \sum_{i=1}^{n}{\big(\text{depth}(k_i)+1) . p_i} + \sum_{i=0}^{n} {\big(\text{depth}(d_i)+1) . q_i} $$
$$ = 1 + \sum_{i=1}^{n}{\text{depth}(k_i) . p_i} + \sum_{i=0}^{n} {\text{depth}(d_i) . q_i} $$
دو نکته که خوب است درباره‌ی رأس‌های مصنوعی به آن دقت کنیم، این است که اولا رأس‌های مصنوعی باید برگ‌های درخت باشند. چون تا وقتی که هنوز رأس دیگری مانده، نمی‌توان مطمئن شد که جستجو نتیجه‌ای نداشته. همچنین، در اولین لحظه‌ای که دیگر رأس عادی‌ای در زیر وجود نداشت، معلوم می‌شود که جستجو نتیجه‌ای نداشته و باید به یک رأس مصنوعی رسیده باشیم. همچنین، اگر مثلا در یک زیردرخت، رأس‌های $k_i, k_{i+1}, \dots, k_j$ قرار داشته باشند، باید رأس‌های مصنوعی $d_{i-1}, d_i, \dots, d_j$ نیز در همان زیر درخت باشند.
فرض کنید میخواهیم سوال را به صورت بازگشتی حل کنیم. اگر رأس‌های $k_i, k_{i+1}, \dots, k_j$ با شروط $1 \leq i, i-1 \leq j, j \leq n$ در یک زیردرخت باشند (حالت $i-1 = j$ یعنی رأس اصلی نداریم، بلکه فقط رأس مصنوعی $d_j$ را داریم). پس یکی از رئوس اصلی باید ریشه‌ی این زیر درخت باشد و این ریشه هر کدام از این رئوس اصلی می‌تواند باشد. آن را $k_r$ بنامیم. پس زیردرخت سمت راست، رأس‌های $k_i, \dots, k_r-1$ و زیردرخت سمت چپ، رأس‌های $k_{r+1}, \dots, k_j$ را دارند. اگر مقدار کمکی زیر را تعریف کنیم $$ w(i, j) = \sum_{l=i}^{j} p_l + \sum_{l=i-1}^{n} q_l $$ هزینه‌ی زیردرختی که در آن هستیم یا همان $c[i, j]$ برابر می‌شود با: $$ c[i, j] = p_r + \big(c[i, r-1] + w(i, r-1)) + \big(c[r+1, j] + w(r+1, j)) $$ و اگر دقت کنید $$ p_r + w(i, r-1) + w(r+1, j) = w(i, j) $$ پس می‌توان فرمول بالا را به صورت زیر نوشت: $$ c[i, j] = c[i, r-1] + c[r+1, j] + w(i, j) $$
بعد از حساب کردن مقدار بالا، به سادگی می‌توان تشخیص داد که می‌توان از روش برنامه‌ریزی پویا برای محاسبه‌ی تابع $c$ استفاده کرد و جواب مسئله، مقدار تابع برای ورودی‌های $i=1, j=n$ یعنی $c[1, n]$ است.
برای مقداردهی اولیه مقادیر
$c[i, i-1]$
برای
$1 \leq i \leq n+1 $
را برابر
$q_{i-1}$
قرار می‌دهیم. چون فقط رأس مصنوعی $i-1$ ام را دارند.
برای به روز رسانی هم از فرمولی که در بخش قبلی داده شده استفاده می‌کنیم. برای محاسبه‌ی
$w(i, j)$
هم می‌توانیم از مقادیر کوچکتر خودش استفاده کنیم. فقط در هنگام محاسبه‌ی باید حواس‌مان باشد که ابتدا مقدار $c$ را برای بازه‌های به طول ۱، سپس برای بازه‌های به طول ۲ و … حساب کنیم.
شبه کد:
for i from 1 to n+1 c[i][i-1] = q[i-1] w[i][i-1] = q[i-1] for len from 1 to n for i from 1 to n-len+1 j = i + len -1 c[i][j] = inf w[i][j] = w[i][j-1] + p[j] + q[j] for r from i to j val = c[i][r-1] + c[r+1][j] + w[i][j] c[i][j] = min(c[i][j] , val)
مقدار حافظه مورد نیاز از $O(n^2)$ است. هر به روز رسانی نیز از $O(n)$ است. پس پیچیدگی زمانی الگوریتم از $O(n^3)$ است.