נושאים פעיליםנושאים פעילים  הצגת רשימה של חברי הפורוםרשימת משתמשים  חיפוש בפורוםחיפוש  עזרהעזרה
  הרשמההרשמה  התחברותהתחברות RSS עדכונים
מדעי המחשב
RSS UnderWarrior Forums : RSS מדעי המחשב
נושא

נושא: שאלה למי שלמד חישוביות ויודע מה זה סודוקו

 שליחת תגובהשליחת נושא חדש
כותב
הודעה << נושא קודם | נושא הבא >>
מאיר
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 01 August 2005 בשעה 11:13 | IP רשוּם
ציטוט מאיר

שלום לכולם

השאלה היא לאיזה מחלקה משתייכת הבעיה האלגוריתמית שבמשחק סודוקו.

P NP  NP-complete  וכו'  האם ניתן לשייך בעיה זו למחלקה מבחינת סיבוכיות מקום?

 
חזרה לתחילת העמוד הצג את כרטיס החבר של מאיר חפש הודעות אחרות של מאיר בקר בדף הבית של מאיר
 
ניר
מנהל האתר
מנהל האתר
סמל אישי

הצטרף / הצטרפה: 12 January 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 3296
נשלח בתאריך: 02 August 2005 בשעה 01:09 | IP רשוּם
ציטוט ניר
ברור שהיא שייכת ל-NP - אני יכול לבנות מכונת טיורינג אי דטרמיניסטי שבפאזה האי דטרמיניסטית שלה תנחש צירוף ואז תעבור בצעד דטרמיניסטי ותבדוק האם זוהי השמה חוקית.

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


__________________
מספר האייסיקיו שלי ו/או כתובת ה-MSN שלי אינם מהווים מוקד תמיכה
חזרה לתחילת העמוד הצג את כרטיס החבר של ניר חפש הודעות אחרות של ניר בקר בדף הבית של ניר
 
מאיר
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 12 September 2005 בשעה 18:26 | IP רשוּם
ציטוט מאיר
הבעיה ב NP COMPLETE :

ניתן להסתכל על בעיית הסודוקו כבעיית 9 צביעה של גרף (בעיית 9 צביעה - בהנתן גרף האם ניתן לצבוע את קודקודיו בעזרת 9 צבעים כך שכל שני קודקודים המקושרים על ידי צלע צבועים בצבע שונה)
נסתכל על כל תא בסודוקו כעל קודקוד בגרף בעל 81 קודקודים.
כאשר יש צלע בין כל שני קודקודים הנמצאים באותה שורה או באותו הטור או באותו ריבוע קטן - כלומר כל קודקוד מקושר לכל הקודקודים שבריבוע הקטן שלו ולכל הקודקודים שבטור שלו וכן לכל הקודקודים שבשורה שלו.
כעת ניתן לכל ספרה בין אחד ל9 צבע שונה וננסה לצבוע את הגרף.
אם ניתן לצבוע את הגרף אזי בכל שורה|טור|ריבוע קטן  יש תשעה צבעים שונים - כלומר תשעה מספרים שונים - הצבה טובה לסודוקו.

ידוע שבעיית התשע צביעה היא NP-C  ולכן הסודוקו הוא NP-C
חזרה לתחילת העמוד הצג את כרטיס החבר של מאיר חפש הודעות אחרות של מאיר בקר בדף הבית של מאיר
 
רועי
אורח
אורח


הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
נשלח בתאריך: 12 February 2006 בשעה 10:42 | IP רשוּם
ציטוט רועי

חבר'ה, אני מבקש לדייק.

כפי שהצגתם את הבעיה היא פתירה בזמן קבוע (1)O, מכיוון שלסודוקו כפי שהוא מוכר לנו יש 81 משבצות.

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

רועי 
חזרה לתחילת העמוד הצג את כרטיס החבר של רועי חפש הודעות אחרות של רועי בקר בדף הבית של רועי
 

אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם

  שליחת תגובהשליחת נושא חדש
גרסת הדפסה גרסת הדפסה

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