متغیر نهان

همان‌طور که در بخش قبل توضیح داده‌شد، تعداد حالت‌های ممکن برای متغیرهای پنهان یا معادلاً تعداد مسیرها نسبت به طول توالی از اندازهٔ نمایی است. شکل زیر، حالت‌های متغیرهای نهان یک مدل پنهان مارکف را به‌صورت یک شبکه نشان داده‌است که در آن، حالت‌های مختلف برای هر متغیر نهان با رنگ‌های متفاوت مشخص شده‌اند و متغیرهای نهان به‌صورت افقی از چپ به راست نمایش داده شده‌اند. با استفاده از الگوریتم ویتربی، می‌خواهیم محتمل‌ترین مسیر را در این شبکه بیابیم به‌طوری که هزینهٔ محاسباتی به‌صورت خطی با طول توالی افزایش یابد.

اگر گره‌های گراف روبرو را با استفاده از دوتایی‌هایی که به‌ترتیب از شمارهٔ متغیر نهان و شمارهٔ حالت‌های ممکن برای آن‌ها تشکیل‌شده باشند، نمایش دهیم، می‌توان وزن بین دو گرهٔ