پاورپوینت زنجیره مارکف گشت تصادفی

بخشی از پاورپوینت

اسلاید 1 :

زنجیره مارکف
گشت تصادفی

اسلاید 2 :

فهرست مطالب
آشنایی با مسئله گشت تصادفی
صدقپذیری دودویی
زنجیره مارکف
گشت تصادفی روی گراف
مدارهای الکتریکی
زمان پوشش
اتصال گراف

اسلاید 3 :

بخش 1: آشنایی با مسئله
طرح مسئله
راه حل قطعی
راه حل تصادفی
گراف کامل
جمع آوری کوپنها

اسلاید 4 :

طرح مسئله
1. تعداد گام برای رسیدن از یک راس به راس دیگر.
2. تعداد گامهایی که باید طی شود تا با شروع از یک گره تمام گره­ها را ملاقات کنیم.

اسلاید 5 :

راه حل های قطعی
1. تشکیل درخت حالت
2. DFS و BFS

اسلاید 6 :

راه حل تصادفی
شانس انتخاب شدن همسایه­ها با هم برابر است.
انتخاب در هر مرحله مستقل از همه انتخابهای قبلی است.

اسلاید 7 :

گراف کامل
1. تعداد گام برای رسیدن از یک راس به راس دیگر با استفاده از الگوریتم گشت تصادفی برابر است با :
2. تعداد مراحل مورد انتظار برای بازدید تمام رئوس برابر است با
تمرین 6.1

اسلاید 8 :

گراف کامل
یک مرحله:
در حالت کلی:

k-1 بار به هدف نرسیم و k امین بار به هدف برسم
توزیع هندسی:

اسلاید 9 :

گراف کامل
احتمال اینکه بعد از ملاقات i-1 تا از گره ها، iامین گره را ملاقات کنیم.

اسلاید 10 :

جمع آوری کوپنها
الگوریتم گشت تصادفی روی گراف کاملkn دقیقا همان پروسه جمع آوری کوپن
با n – 1 کوپن است.
M = N-1

اسلاید 11 :

بخش 2: صدقپذیری دودویی (2-SAT)
کنترل ناپذیری و صدق پذیری
صدق پذیری دودویی
راه حل تصادفی صدق پذیری دودویی
گشت تصادفی روی خط
تحلیل صدق پذیری دودویی

اسلاید 12 :

کنترل ناپذیری
الگوریتم زمان چند جمله ای پیدا شده است.
کنترل ناپذیری آنها به اثبات رسیده است.
خروجی آنها غیر چندجمله ای است.
غیر قطعی (توقف).
کنترل ناپذیری آنها به اثبات نرسیده اماهرگز الگوریتم زمان چند جمله ای پیدا نشده است.

اسلاید 13 :

تصمیم گیری
خروجی بله یا خیر است
مجموعه :P
تمام مسائل تصمیم گیری که می توان توسط
الگوریتمهای زمان چندجمله ای حل کرد.

اسلاید 14 :

الگوریتم غیرقطعی
Bool verify(weighted G, number d, claimed_tour S)
{ if(S is a tour && the total weight of edges in S is <=d)
return “true”
else
return “false”
}
مراحل حل الگوریتم های
غیر قطعی
مرحله اول حدس (غیرقطعی)
مرحله دوم اثبات (قطعی)

اسلاید 15 :

الگوریتم غیرقطعی
الگوریتم غیرقطعی زمان چندجمله ای
الگوریتمی است که مرحله اثبات آن یک الگوریتم زمان چندجمله ای است.
مجموعه NP:

تمام مسائل تصمیم گیری که می توان توسط الگوریتمهای غیر قطعی زمان چندجمله ای حل کرد.

اسلاید 16 :

-NPکامل
اگر یکی از مسائلNP در P باشد همه مسائل NP در P قرار دارند.
صدقپذیری:
الگوریتم شناختهشدهای وجود ندارد که به صورت کارآمد همهی موارد مسئلهی صدقپذیری را حل کند.

اسلاید 17 :

صدق پذیری دودویی
راه حل قطعی

اسلاید 18 :

راه حل قطعی
y
x
z
جستجوی مسیر در گراف ها

اسلاید 19 :

الگوریتم تصادفی
1. Start with an arbitrary assignment
2. While terminating with all clauses satisfied or repeat M
1. Choose a clause that is currently not satisfied
2. Choose uniformly at random one of the literals
in the clause and switch its value
EndWhile
3. If valid assignment found, return it
4. Else, conclude that F is not satisfiable

اسلاید 20 :

گشت تصادفی روی خط
موقعیت ذره، تعداد متغیرهای دارای ارزش صحیح، در راه حل فعلی را نشان می دهد.
i+1
i-1
0.5
0.5
در هر مرحله با احتمال 0.5 تعداد متغیرهایی که ارزش درست دارند را افزایش می دهیم.
Xi تعداد مراحل برای رسیدن به حالت N با شروع از حالت i می باشد.