جواب تمرین های الگوریتم تصادفی

سوال 4 این سوال 1 تمرینه: (موش و گربه)

http://www.eecs.berkeley.edu/~vkanade/cs174/HW/HW9_sol.pdf

من از استادمون پرسیدم که این راهی که من رفتم راه اصلیه گفت آره اما خب این راه دیگه ای رفته.

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

من گفتم که این معادل یک random walk روی یک گراف دیگه است که هر راسش جای موش و گربه است.

ظاهر این دو تا حل مثل همه (یعنی این قسمتی که من گفتم) ولی بقیه اش خیلی فرق داره.