Question

spring16_a
dynamic_programming

יהא G=(V,E)G=(V,E) גרף מכוון וחסר מעגלים ויהא v0Vv_0\in V. אליס ובוב משחקים משחק בו לכל אחד תור לסירוגין, כאשר בוב מתחיל. בכל תור ii, השחקן שתורו כעת בוחר קשת e=(vi,x)e=(v_i,x) היוצאת מ-viv_i. אחר כך, נקבע כי vi+1=xv_{i+1}=x, והתור עובר לשחקן השני. מפסיד השחקן שאין לו קשת לבחור (דהיינו הצומת viv_i הוא בור). הציעו אלגוריתם המכריע האם בוב יכול להבטיח ניצחון.

2

Answers

No answers yet ¯\_(ツ)_/¯
Feedback