روش تجزیه دوگان برای حل مسیله شبکه های مارکوفی

شبکه های مارکوفی، کلاس مهمی از مدل های گرافی می باشند که کاربرد وسیعی در بینایی کامپیوتر، آنالیز تصاویر پزشکی، بخش بندی تصویر، نظریه اطلاعات و فیزیک آماری دارند. شبکه های مارکوفی شامل یک گراف غیرجهت دار و یک مجموعه گسسته از برچسب ها هستند. مسیله استنباط MAP برای یک شبکه مارکوفی به صورت پیدا کردن تخصیص بهینه برچسب ها به ریوس گراف تعریف می شود، که هزینه تخصیص برچسب ها مینیمم شود. این مسیله استنباطی که یک مسیله عدد صحیح است، NP -سخت می باشد. ما به مطالعه روش تجزیه دوگان برای حل این مسیله می پردازیم. به وسیله روش تجزیه دوگان ابتدا مسیله را به زیرمسیله های قابل حل و آسان تر تجزیه کرده و سپس به کمک روش زیرگرادیان تصویر شده، تلاش می شود تا یک جواب برای مسیله اولیه بیابد. این روش، در صورت تعیین طول گام مناسب همواره به یک جواب همگراست که به خوبی جواب حاصل از آزادسازی خطی این مسیله است