בעיה שנתקלתי בה:

[סילווריו]

בעיה שנתקלתי בה:

יש לי מערך גדול מאד : NxM אני צריך "לטייל" על המערך מנק Si לנק´ Di, ולשמור את הדרך במינימום מקום, כך שכאשר יתבצע הטיול Sj עד ל Dj, אוכל לבדוק האם כבר עברתי במקום. כמובן שפרט לאחסון מינימאלי, אני צריך יעילות בשליפת המידע בקשר למעבר בנק´ מסויימת (אם היה). שימוש במערך בקרה דו מימדי הוא לא יעיל כי מדובר בN ו M בסדר גודל של יותר מ 1000 (שזה יותר מדי מקום לתפוס בשביל הבקרה בלבד). סיל.

 

[באפט]

תגובה

הכנס לרשימה את כל הכיוונים השונים שנעת בהם החל מנקודה מסויימת. זה יהיה משהו כמו "ימינה, ישר, ישר, ישר, ימינה, שמאלה, ישר, ישר, ..." אחר כך כווץ את הרשימה, כל שכל רצף של כיוון יהפוך להיות ציון הכיוון ומספר החזרות שלו. כך, הדוגמה שלמעלה תהייה: "ימינה, ישר 3, ימינה, שמאלה, ישר 2, ...." עכשיו נשאלת השאלה כיצד למצוא אם מסלול כזה, בהינתן נקודת המוצא, עובר דרך נקודה כלשהי. אפשר לבצע מעין backtracking על המסלול הזה ולבדוק. אם אתה יודע שגודל המסלול קטן מאוד יחסית למטריצה (העולם) עצמה, אולי כדאי לחשב תוך כדי תנועה את האזור הכללי שבו עבר המסלול. האזור הזה יהיה המרובע (כלומר ישמר ע"י שתי נקודות) הקטן ביותר שמכיל את כל המסלול. קל לחשב אותו. נקודה אחת שלו היו נקודת המוצא, ונקודה שניה שלו מחושבת כך: X הנקודה - סכום ההליכות לצד ימין פחות סכום ההליכות לצד שמאל. Y הנקודה - סכום ההליכות למטה פחות סכום ההליכות למעלה. עכשיו, בהינתן נקודה כלשהי, אם היא נמצאת מחוץ למרובע, אין טעם לחפש האם היא נמצאת במסלול. אפשר להמשיך ולפרק את המסלול ליותר ממרובע אחד (למשל למספר לוגריתמי של מרובעים בגודל המסלול), כדי להגביר את יעילות הזמן. לפי דעתי, הפתרון ההיוריסטי האחרון דומה לדרך שבא בני אדם היו פותרים את הבעייה.

 

[סילווריו]

בעניין החלק הראשון

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

 

[voguemaster]

איבדתי אותך...

תראה, לא בדיוק הבנתי האם אתה רק רוצה לדעת אם מישהו עבר בנקודה מסוימת, או שאתה רוצה משהו מורכב יותר כמו לדוגמא למצוא את הנתיב הכי יעיל מנקודה לנקודה בהנחה שכבר קיימים נתיבים מסוימים.. במקרה הראשון, אפשר לשמור עבור כל תא במטריצה מערך או יותר טוב רשימה מקושרת של הנתיבים שעברו דרכה, פלוס COUNTER למספר הנתיבים שעוברים בנקודה (מה שמכריח לעבוד עם מטריצה של מבנים אבל לא נורא). אם תרצה לדעת אם עברו בנקודה, תוכל לבדוק את הנקודה ספציפית ולראות האם ה-COUNTER הוא 0. כדי לבדוק אם כבר יש נתיב, תוכל לבדוק את שתי נקודות הקצה ולבדוק האם יש נתיב משותף לשתיהם. לדוגמא נקודה מספר 1 מכילה שני נתיבים, מספרים סידוריים 10000 ו-10001 נקודה מספר 2 מכילה נתיב אחד חזרה לנקודה מספר 1, עם מספר סידורי 10000 נקודה מספר 3 מכילה נתיב אחד חברה לנקודה מספר 1, עם מספר סידורי 10001 אם אתה רוצה לדעת האם יש נתיב מ-1 ל-2, תוכל לבדוק איזה מספרים סידוריים של נתיבים יש בנקודות, וכך לפחות לדעת אם יש נתיב מ-1 ל-2. כמובן שעל כל נקודה בנתיב מ-1 ל-2 יש אחסון של המספר הסידורי 10000. אני מקווה שהבנתי מה אמרת, ואם לא אז אני אשמח לדסקס איתך את העניין.. יש לך איסיקיו ?

אלי

 

[סילווריו]

לא עד הסוף

ההנחה היא שאני מוצא את הנתיב האידאלי לפי סריקת האיזור הקרוב. השימוש ברשימה גם לא נותן פיתרון טוב מספיק מהסיבה שהחיפוש של כל איבר יארך יותר מדי זמן. אין ICQ, אם יש מי שמאמין עדיין ב Email אז בשמחה : [email protected]

 

[voguemaster]

כן אבל...

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

 

[באפט]

בעייה מעט שונה

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

 

[סילווריו]

החידוד:

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

 

[באפט]

בעייה מסובכת

צריך ליצור מודל של דרך שלוקח בחשבון טופולוגיה ותנאי טבע. אני לא מבין כלום בזה, אבל נראה לי מסובך לייצג מקורות מים, הרים, צמחייה, גדרות, שטחים מוצלים, יישובים וכולי, והכל בשטח אחסון מינימלי. נניח ויש לך מודל כזה, אני מציע שתי שיטות: 1. להשתמש באלגוריתם היוריסטי. אפשר לנסח מספר חוקים כגון: "חיה לא עוברת בגדר", "חיה מתרחקת מיישוב" וכולי. לפי אלו האלגוריתם ימשקל את כל האפשרויות ויחזיר את המקסימום האפשרי. 2. אתה צריך לדגום חלק מהדרכים ולהסתמך על המידע הזה כ-"מידע אמת". מידע זה יהיה "קבוצת אימון" של אלגוריתם הניבוי. על סמך מידע זה ועל סמך שיטות של למידה מכונה (machine learning), אפשר לנבא באופן יותר טוב מאקראי את המסלולים. בקשר למבנה נתונים של מסלול עם הפעולה "האם נקודה במסלול", אני עדיין חושב שמה שהצעתי בהודעה הראשונה עם המרובעים פועל היטב. המסלול יהיה מורכב ממספר סביר של מרובעים, והם יקרבו בגדול את הצורה שלו. "בתוך" כל מרובע, אפשר לשמור מסלול מכווץ - כלומר אך ורק את רשימת הפניות שעשו בו (לך ישר 16 פעמים, ימינה, ישר 14 פעמים וכולי). הפעולה "האם נקודה במסלול" תחושב כך: 1. עבור כל מרובע (יש מספר סביר, לא ענק, בכל מקרה אתה יכול לשלוט בו) בצע: 1.1. אם הנקודה נכללת בשטח המרובע (חישוב מיידי) בצע: 1.1.1.בדוק אם הנקודה נמצאת במסלול המכווץ המשוייך למרובע הנוכחי. הפעולה "בדוק אם נקודה P נמצאת במסלול מכווץ": 2. לך על המסלול המכווץ - כלומר בצע את ההוראות "ימינה, ישר 17 פעמים" ותוך כדי כך שחזר את הנקודה האמיתית (למעשה טווח של נקודות) שאתה נמצא בה. אם זאת שווה לנקודה P אז החזר אמת" סעיף 2 לוקח זמן כאורך המסלול המכווץ שבתוך מרובע...וזה אמור להיות משהו די קטן. כמו כן אני חושד שצעד 1.1.1 בכלל לא יתבצע במרבית הפעמים.

 

[ekampf]

תשתמש במערך של ביטים

1000 ביטים זה לא משהו נורא... 32 משתנים מסוג int אמורים להספיק...

 

[באפט]

1000X1000 לא 1000

 

[סילווריו]

ובהנחה שצריך יותר מסיבית אחת ...

 

[ekampf]

עדיין לא נורא, צריך סיבית לכל תא...