מנסה למצוא אלגוריתם יעיל לבעיה הבאה

[yossi_s1]

השאלה היא חלק משיעורי בית שלי, אני צריך לפתור את השאלה בדרך הכי יעילה שבטוח טובה יותר מ O(n^2)

המשימה היא כזו:

יש מערך דו מימדי שמכיל אפסים ואחדים וצריך למצוא משהוא שנקרא בור.בור הוא מצב בו בשורה K יש רק אפסים ובעמודה K יש רק אחדים, בנק' המפגש יש 0, הנה דוגמא:

0 1 1 1 1 0

0 0 1 1 0 0

0 0 1 1 0 1

0 0 0 0 0 0

0 0 1 1 0 1

1 1 1 0 1 0

במערך הזה יש בור ב K=3

כתבתי קוד שפותר את השאלה, אבל הוא לא הכי אלגנטי כנראה וגם, למרות שהיעילות טיפה טובה יותר מN^2 במקרה הגרוע ביותר היא לא רחוקה מזה.

אני לא מצליח לישר את הקוד לשמאל אז זה יוצא מבולגן אז הנה קישור:

https://www.dropbox.com/s/tzdd6ua9czs3h0q/code.txt

הצעות?

[בור ועם הספר]

רעיון ראשון שחשבתי הוא עבור כל K לסכום שורה ועמודה - אם סכום שורה הוא 0 וסכום עמודה הוא n-1 אז זה בור.

אפשר לייעל ע"י זכירה של מה שכבר עברנו עליו.

בכל מקרה במטריצה NxN זה חייב להיות בסיבוכיות של N^2 כי אתה חייב לעבור על כל איברי המטריצה. ברגע שמצאת בור, אפשר להפסיק כי לא ייתכנו שני בורות (וודא שאתה מבין למה)

[Zelig]

רמזים:

א) אפשר לפתור את זה בסיבוכיות לינארית O(N) - לא צריך לעבור על כל אברי המטריצה.

ב) באילו מקומות יכול להיות בור?

ג) תחשוב על זה: כמה בורות יתכנו במערך לכל היותר, ולמה דווקא המספר הזה?

[Gil28]

רמז ג' קצת מתוחכם. תחשוב כשאתה בודק על K מסויים אם הוא בור, מה הבדיקה שאתה עושה ומה זה מעיד על ה-K הבא.

[ErezBH]

המרתי את הבעיה לגרף (ייצוג בעזרת "מטריצת שכנים") ורשמתי לך פסאודו קוד, מקווה שיעזור:

בור הוא צומת בגרף מכוון G(V,E) דרגת כניסה n-1 ודרגת יציאה 0.

I. נבנה רשימה באורך n של כל קודקודי הגרף, ונקרא לה "רשימת מועמדים (להיות בור)".

II. נריץ את הלולאה הבאה:

- כל עוד יש יותר מאיבר אחד ברשימה, הוצא את האיבר הראשון ברשימה V ואת האיבר השני ברשימה U.

- בדוק האם במטריצה יש קשת מ-U ל-V

אם כן – מחק את U והחזר את V לתור

אם לא- מחק את V והחזר את U לתור

III. אם ברשימה נשאר איבר אחד W בדוק האם יש קשת מכל האיברים האחרים אליו. אם כן – החזר את W, אחרת החזר שאין בור.

סיבוכיות: בניית רשימת מועמדים O(n), אח"כ n בדיקות שכל אחת היא O(1) סה"כ O(n). בסוף עוד n בדיקות סה"כ O(n)

[Ligi]

רמז ג הוא רמז גדול, תחשוב כמה בורות יש, תנסה ליצור 2 בורות ולכן תראה שזה לא הגיוני כי יהיה התנגשות בין 2 הבורות.

מכאן שאם יש בור יש רק אחד.

אתה יכול לקחת את האכסון ולראות איפה יש לך מועמד לבור (לעבור על האלכסון זה O(n) )

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

בכל מקרה זה רעיון שעלה לי לראש ללא מחשבה עמוקה, בהצלחה עם זה.

נ.ב. תערוך את הדוגמא שלך היא לא טובה, שורה 4 ועמודה 3 הם אם הנתונים הנכונים אצלך.

[Ligi]

טוב נראה לי שפתרתי...

כמו שהסברתי קודם יכול להיות מצב שיש רק בור אחד או שאין בור בכלל...

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

נניח שהראשון הוא ב1 והשני ב3 לכן התא במקום X =3 Y=1 יקבע מי בניהם יכול להיות הבור והשני בטוח לא.

אם יש שם 1 אז 3 עם פוטנציאל ו1 בטוח לא ואם יש 0 אז ההפך.

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

עלות הרשימה O של (N) כמות השוואת במקרה הרע N-1 ועלות של בדיקה של בור 2N העלות היוצאת O של N

[yossi_s1]

קודם כל סורי שנטשתי קצת את הדיון, לינארית ובדידה העסיקו אותי.

בקשר לפתרון, רוב התגובות לא ממש עזרו, או אפשר להגיד הרמזים לא ממש עזרו.

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

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

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

011

001

000

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

לגבי השאלה באילו מקומות יכול להיות בור. בכל מקום? לא בטוח שאני מבין את הכוונה.

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

הפתרון האחרון של LIGI הוא באמת הפתרון הקטע שלא חושב שהייתי מצליח לעלות על זה בעצמי אי פעם.

זה באמת הפתרון היחיד? למישו יש רעיון?

בכל מקרה תודה LIGI וכל הכבוד... עכשיו אני אלך כמה דקות לכתוב את זה.

[Gil28]

עכשיו נגיד אתה בודק לכל K האם זה בור, לא משנה איך בודקים.

מעבר על כל K משמע לעבור על N איברים של האלכסון - עד כאן סיבוכיות טובה. עכשיו בדיקה של האם בור כביכול הוא החלק המסובך (זמן ריצה).

אבל אם מצאת שהוא לא בור, זה אומר שיש תא כלשהו ראשון שלא מקיים את התנאי של בור. נניח שעבור המועמד הראשון (0,0) מצאת כי התא (0,4)

הוא 1 ולכן עבור K=0 הוא לא בור. אבל מה זה מעיד על K=1 ועד K=3? למה הם לא יכולים להיות בור ולכן ה-K הבא שתבדוק הוא K=4?

[yossi_s1]

אני מבין מה אתה אומר, אבל מה הסיבוכיות של המקרה הגרוע?

נגיד אני מתחיל לבדוק מ i=0 ויורד למטה.

המקרה הגרוע אמור להיות מסוג המטריצה שתיארתי בתגובה האחרונה שלי.

במקרה הזה אני לא יכול לפסול בכלל.

שוב, נניח המטריצה הבאה:

0111

0011

0001

0000

אני מתחיל משורה 0. מצאתי 1 ב(0,1), זה לא אומר לי כלום על שורה 1 והלאה.

טוב עובר לשורה 1, מוצא 1 ב (1,2), שוב לא אומר לי כלום על שורה 2 והלאה.

וככה עד הסוף.

יוצא שאני צריך לבדוק n^2 / 2 (חצי של הריבוע) שהוא כמובן O(N^2).

או שאני לא מבין פה משו.

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

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

הנה הקוד:

https://www.dropbox.com/s/3y36oysovasof6k/isSink.java

רק מקווה שלא יהיו לי דברים כאלו במבחן, כי לבד לא הייתי מצליח לפתור.

[Gil28]

באותה מידה יכולת לחשב את זה כשתיים בחזקת N חלקי 2 אבל זה לא המקרה. זה יוצא משהו כמו N*2 כלומר (O(N

על על איבר באלכסון אתה אתה בודק אותו ועוד תא או שניים (בשורה ו\או בטור). אם אתה בודק יותר זה על חשבון איבר אחר באלכסון

ולכן זה מתקזז.

תנסה לחשב את זה מספרית על המקרה הטוב ביותר (לא כש-K=0) והמקרה הגרוע על מטריצה גדולה (נניח 10X10).

שים לב שהסיבוכיות היא בנוטציה אסימפטוטית כך שבודקים מה קורה כש-N גדול מאוד. אם המטריצה הייתה 1X1 היית יכול לחשוב על זה כ-N^100

[yossi_s1]

וואלה, עכשיו הבנתי.

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

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

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

הנה הקוד:

https://www.dropbox.com/s/1seqhwz6ehfi75n/isSink2.java

שורות 25 עד 70.

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

דבר שני, מדובר בקורס מבוא לJAVA של הפתוחה, ככה שאני בשלב מוקדם יחסית, לא עשיתי עדיין את הקורס סיבוכיות והקוד הזה די מסובך כדי שאני יוכל לנמק מהי הסיבוכיות שלי, למרות שברור לי שהיא N

[Gil28]

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

בכל מקרה בשביל קורס מבוא אף אחד לא מצפה ממך להוכיח את הסיבוכיות, מספיק שתתאר למה היא לינארית.