פתרון סודוקו ע"י זרימה?

פתרון סודוקו ע"י זרימה?

מישהו אולי מכיר איזושהי סכמה שמסבירה טוב זרימה, איך היא יכולה לעזור לפתור תשבצים כגון סודוקו או ריבוע קסם, או טבלה ריבועית שרשום בה סכום כל שורה וכל עמודה וצריך להציב מספרים על מנת שזה יסתדר בדיוק. אשמח לעזרה בענין הזה.
 

johnny d

New member
זרימה היא בעיה NP קשה

אני לא בטוח למה אתה מתכוון אבל אני בטוח שהיא אינה יכולה לעזור לך לפתור שום דבר.
 

johnny d

New member
sorry, u probably mean Maximum Flow

אחת האמנויות במדעי המחשב היא הצגת רדוקציות במיוחד אם הן יעילות חישובית ופשוטות לטיפול. נראה שאתה מחפש רדוקציות שפותרות בעיה NP-קשה בזמן פולינומיאלי, וכאן אולי הטעות שלך . . .
 
כן

בסוף הסתדרתי. צריך לבנות רשת זרימה ולתת ערכים של אינסוף לקשתות באמצע. פתרון זרימת המקסימום ברשת שבונים הוא נותן את פתרון כל הטבלה.
 
למעלה