אני צריך פיתרון

[ogispan]

אני צריך פיתרון

שלום לכם! הנה חידה שאני מקווה לקבל פיתרון עליה (אני לא יודע את התשובה) אתם נימצאים מול גדר אינסופית ואתם צריכים להגיע לצד השני של הגדר. אתם יודעים שיש פירצה אחת בגדר אבל אתם לא יודעים אם הפירצה לשמאלכם או לימינכם ואתם לא יודעים גם באיזה מרחק אתם נימצאים מהפירצה. מה האלגוריתם היעיל ביותר למצא את הפירצה? (כמובן אלגוריתם שיגרום לכם ללכת את מספר המטרים הקטן ביותר כדי למצא את הפירצה בביטחון) יש כמה הנחות: המרחקים נאמדים במטרים שלמים (כלומר הפירצה לא נימצאת במרחק X מטרים וחצי). אם החלטתם ללכת 10 מטר לצד ימין והפירצה נימצאת 5 מטר לצד ימין, אז אתם לא עוברים על פני הפירצה וממשיכים, אלא ניתן לקבוע שמצאתם את הפירצה והאלגוריתם מסתיים אודה לכם אם תוכלו לעזור לי לפתור את זה

 

[Evil Guy]

אמ...

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

 

[ogispan]

לא נישמע הגיוני

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

 

[Evil Guy]

אז אין לך שום אפשרות אחרת>

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

 

[Tesseract]

לדעתי..

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

 

[ogispan]

זה ברור

אני מחפש את הפיתרון הטוב ביותר. לא את הגרוע ביותר אם אני אלך צעד שמאלה, 2 ימינה, 3 שמאלה, 4 ימינה........ אני אמצא את הפירצה תוך X^2 צעדים.... וזה לא הפיתרון הטוב (X מציין את המרחק מהפירצה שבו אני נמצא בהתחלה)

 

[LeCagot]

אולי

1 ימינה, 2 שמאלה, 4 ימינה, 8 שמאלה וכן הלאה. נדמה לי שזה יוצא פחות, ואין לי כוח לחשב.

 

[sindip]

לא נראה לי...

בדרך הזו אתה מתקדם רק לכיוון אחד...

 

[Tesseract]

*הפירצה בגדר

טוב שנזכרתי

 

[אורצוש]

רגע אחד! משהו לא מסתדר.

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

 

[slallum]

בדיוק מה שאני חושב../images/Emo45.gif

 

[עריסטו]

לא נכון

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

 

[slallum]

הממ אז רגע

אם אני אלך 3 מטרים ימינה, אח"כ 6 מטרים שמאלה, אח"כ 12 ימינה וכך הלאה, אז הסיכויים פה הם אותו דבר כמו השיטה הקודמת, לא?

 

[עריסטו]

לא

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

 

[Tesseract]

../images/Emo45.gif

מה שאני חשבתי, רק שאתה ניסחת את זה יותר טוב

 

[dark dumb]

לא נכון,

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

 

[mili999]

מזמן לא הייתי כאן

שלום לותיקים. אי אפשר ללכת רק לצד אחד כי אז לא בטוח שהפרצה תמצא. אם בחרצ ימינה והפרצה משמאלך, לעולם לא תוכל להגיע אליה. חיבים לזגזג כדי להגיע לפירצה. אפשר לזגזג 1,2,3,4... אבל נשים לב שזגזוג של 2,4,6,8 יהיה יותר יעיל. וכו' ולכן זה לא אופטימלי. ואכן הוא סדר גודל של X^2 (למעשה אם הפרצה היא במרחק N אז זה סכום הסדרה החשבונית שיצרת עד N) במקרה הפשוט זה N^2-N)/2) בפתרון של הריבועים ( 1 2 4 8 ...) אם הלכנו K צעדים ימינה אז סה"כ הצעדים שלנו זה 2K-1. ולכן במקרה הרע נצעד כ-6N צעדים. (אם עצרנו בדיוק ליד הפרצה שבמרחק N, הלכנו 2N לצד השני ושוב 2N+1 עד לפרצה).