נושא: עזרה דחופה בקוד :(

נשלח בתאריך: 26 March 2009 בשעה 19:11 | IP רשוּם

האם למישהו יש במקרה את הקוד לשיטת hill climbing בשפת c,c++ או java???

אשמח לעזרה אם כן...

נשלח בתאריך: 30 March 2009 בשעה 18:57 | IP רשוּם

אני מניח שזה יעזור:

http://www.java2s.com/Code/Java/Collections-Data-Structure/Findconnectionsusinghillclimbing.htm

נשלח בתאריך: 30 March 2009 בשעה 22:35 | IP רשוּם

שלום לך,

שיטת hillclimbing היא דרך למציאת פתרון אומפטימלי ע"י קירוב איטרטיבי / רקורסיבי.

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

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

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

נשלח בתאריך: 31 March 2009 בשעה 16:36 | IP רשוּם

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

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

תודה....

נשלח בתאריך: 04 April 2009 בשעה 03:33 | IP רשוּם

שבת שלום,

כל פונקצית שיפור תחזיר מצב חדש טוב יותר מהפתרון הנוכחי, בתנאי שהמצב הנוכחי אינו נק' מקסימום (או מינימום תלוי לאן מנסים לקרב) כלשהיא. כיוון עליית הפונקציה נקבע לפי מהות הבעיה וראות המתכנן לנכון. לדוגמא בבעיית שמונה המלכות בוחרים מאוסף אפשרויות השיפור אחד (לרוב הראשון) וממשיכים משם (גישה הנקראת stochastic hill climbing). לעומת זאת בבעיית הסוכן הנוסע מנסים לשפר את המסלול הנתון ע"י בחירת השיפור ההטוב ביותר מבין מסלולי השיפור האפשריים (best first).

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

(Xn = Xn-1 + f'(Xn-1

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

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

  (Xn = Xn-1 + Cn * f'(Xn-1

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