שלום לכולם, אני צריך לפתור את הבעיה הבאה בפייתון, אשמח אם למישהו יש כיוון:

 

נוסע מגיע לעיר מסויימת ל L יחידות זמן, יש לו N אתרים אותם הוא הוא רוצה לבקר. לכל אתר יש מידת אטרקטיביות W בין 1 ל10. בנוסף כל אתר מצריך P יחידות זמן.

שדה התעופה הוא אתר 0 ונמצא ב(0,0) ולכל אתר יש קואורדינטה (x,y). 

הזמן שלוקח לזוז בין מקום למקום נמדד לפי מרחק אווירי (לדוגמא מ 0,0 ל 0,2 לוקח שעתיים)

 

עליי להחזיר את הפתרון האופטימלי למסלול בצורה כזאת 0,1,3,0 (משדה תעופה לאתר 1 ומשם לאתר 3 ומשם חזרה לשדה תעופה)

 

תודה מראש לגאון שיפתור!

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

 

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

הבעיה הזו דווקא לא שקולה ל- SalesMan Problem כי פה יש אילוצים.

 

זו למעשה וריאציה של ה- KnapSack Problem.

 

כלומר יש לבצע מקסימיזציה של ההציון של האתרים אותם רואים תוך אילוץ של כמות הזמן.

 

חיפוש קטן באינטרנט יראה לך את הפתרון (רק זכור לממש בצורה של Dynamic Programming).