روش تجزيه دوگان براي حل مسئله شبكه‌هاي ماركوفي

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