» «
בעיית הסוכן הנוסע
מהי בעיית הסוכן הנוסע והאם קיים אלגוריתם לפתרונה?



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

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

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

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


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

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

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

דרכים אחרות? - בטח לא דרך ידנית.

רק שנבין כמה הבעיה מורכבת - פתרון בניסוי וטעייה הוא בלתי אפשרי כאן, כי אם יש לנו 10 נקודות בלבד, יש לה !N אפשרויות, N עצרת!, כלומר נצטרך להשוות
את המרחקים בלא פחות מ-3,628,800 אפשרויות או מסלולים אפשריים.

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


#תולדות הבעיה
במאה ה-19 היו ראשונים שניסחו את בעיית הסוכן הנוסע, שבראשי תיבות מכונה TSP, המתמטיקאים ויליאם המילטון מאירלנד והמתמטיקאי הבריטי תומאס קירקמן (Thomas Kirkman).

ב-1857 המילטון אף פיתח את "משחק איקוסיאן" (Icosian game) שהמטרה בו הייתה למצוא את "המסלול ההמילטוני" שהוא הפתרון הקצר ביותר.

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

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

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


#אז מה עושים?
השיטה הפשוטה היא הגרידית (Greedy). השיטה היא מכל נקודה ללכת אל הכי קרובה אליה.

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


הנה אלגוריתם הסוכן הנוסע (עברית):

https://youtu.be/IUYaqz2hxN8


דוגמה להתמודדות עם חוט:

https://youtu.be/xi5dWND499g


כמה אסטרטגיות למסלול:

https://youtu.be/SC5CX8drAtU


ובתכנות:

https://youtu.be/hvDx7q6vcWM


הסוכן הנוסע ובעיית ייעול המסלול (עברית):

https://youtu.be/MMt3I2P1j3I


עוד הסבר על אלגוריתם קירוב ויעילותו (עברית):

https://youtu.be/9Uwp8NPdti0
יעילות
מה בין יעילות להתייעלות?



יְעִילוּת (Efficiency) פירושה לרוב הוא השגה של התוצאות הטובות ביותר, תוך ניצול מרבי של האמצעים העומדים לרשות המשיג. כשמישהו הוא יָעִיל, הרי שהוא עושה את עבודתו על הצד הטוב ביותר.

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

הִתְיַעְלוּת (re-organization) היא שיפור ביצועי מערכת קיימת. מכאן גם הביטויים בשפות זרות, של אוֹפְּטִימִיזַצְיָה, או בעברית יִעוּל. בתהליכי התייעלות יכולים לפטר עובדים לא נחוצים, לרכוש מכונות טובות ואולי אף להחליף מנהלים בארגון, כדי להחזירו למקום של ביצועים גבוהים במטרותיו.


הנה עובדים יעילים בעבודה על הסרט הנע שהמציא הנרי פורד:

https://youtu.be/qFbsDArAWj8


יעילות מחויכת כשמגיעים לצבא:

https://youtu.be/VDNV_SLsEOQ


דרך להתייעלות היא למשל לעבור לאנרגיות מתחדשות:

https://youtu.be/Ljuyf2EVHyk


הנה יעילות, לפי הסאטירה של צ'ארלי צ'פלין ב"זמנים מודרניים":

https://youtu.be/6n9ESFJTnHs


והתייעלות, מאותו סרט:

https://youtu.be/n_1apYo6-Ow
מכונות במקום אנשים
מי חשב שאוטוטו מכונות יחליפו בני אדם לחלוטין?



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

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

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

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

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


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

http://youtu.be/Vd5R7BHcFfo


ושיחה שמתארת את האבטלה החדשה, שנוצרת כתוצאה מטכנולוגיה שהולכת ומחליפה בני-אדם (עברית):

https://youtu.be/jM00QpOysj8?t=44s
רובוט תעשייתי
מהו הרובוט התעשייתי?



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

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

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


לעולם לא נמאס להם.. הנה "זמנים מודרניים" של הרובוטים בפס הייצור:

https://youtu.be/d7hwDw7rCuo


וכאן הרובוטים התעשייתיים עובדים בהילוך מהיר, בתעשיית הרכב במפעל מכוניות "קיה":

https://youtu.be/sjAZGUcjrP8


הנה רמת הדיוק שהם מגיעים אליה:

https://youtu.be/SOESSCXGhFo


רובוט תעשייה קטן:

https://youtu.be/e2u2rEY7btU


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

https://youtu.be/XjlAYgxBhao


ומה קורה כשהרובוטים הקודמים יוצאים לפנסיה ומגיעים עובדים רובוטיים מוחדשים (שעבדו קודם במפעל אחר):

https://youtu.be/nkLd45Ftfhc

ייעול

הנרי פורד
מה בנה הנרי פורד ומה היה החידוש הגדול שלו?



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

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

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


הנה המצאתו הגדולה 100 שנה אחרי:

https://youtu.be/qFbsDArAWj8


סיפורו של פורד ושל מודל T שלו:

http://youtu.be/wA2P76gQUCo


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

http://youtu.be/HaR3M70DYBw?t=2s


עוד על תולדות חייו של יצרן הרכב הנרי פורד:

http://youtu.be/AT4gdODtEzk?t=6s



ותכנית חינוכית על הנרי פורד - האיש והסרט הנע (עברית):

https://youtu.be/h-fCeR5pihQ?long=yes
שיטת הסרט הנע
מהי שיטת הסרט הנע ומהו פס הייצור?



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

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

אז הרעיון היה שכל עובד במפעל יתמחה בפעולה שאותה הוא יבצע וכך יגיע המפעל ליעילות המרבית. בפורד קראו לזה "פס ייצור" (Assembly line).

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

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

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


הנה סיפורו של פס הייצור עם הסרט הנע:



מודל ה-T של פורד שהיה הראשון שבו יישם פורד את השיטה היעילה כל כך:

http://youtu.be/S4KrIMZpwCY?t=12s


כך הציג צ'ארלי צ'אפלין בסרט "זמנים מודרניים" את העבודה על הסרט הנע:

http://youtu.be/DfGs2Y5WJ14?t=7s


ולצערנו גם בעלי חיים מטופלים בסרט נע:

http://youtu.be/S6DyLd82AHg
עקרון פארטו
מהו חוק פארטו ואיך הוא מאפשר התנהלות נכונה?



חוק פארטו או עיקרון פארטו (Pareto principle), הוא חוק שנקרא גם "חוק 80/20" ולפיו 20% מהפעולות שעושה אדם אחראיים ל-80% מהערך שהוא יוצר, בעוד שעבור 20% הנותרים של הערך הוא נאלץ להשקיע המון - 80% מהאנרגיה שלו. הרבה צעדי ייעול ותכנון עיסקי נגזרים מהחוק הזה, פרי הגותו של הכלכלן והסוציולוג וילפרדו פארטו.

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

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

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

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

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


הנה הסבר של חוק פארטו (עברית):

http://youtu.be/wadm8AWIv5M


הסבר מצוין של המשמעות של חוק פארטו לחיים:

https://youtu.be/PaUWhO-B7Ts


ולעסקים:

https://youtu.be/zPoA6dzKmtg


דוגמאות לריכוז מאמץ ב-20% שמייצרים את 80% מההצלחה:

http://youtu.be/V28B_xOJzK4


וכך חוק 80/20 יכול לסייע לך לשנות:

http://youtu.be/bBQtel7tYNg


אֵאוּרִיקַה - האנציקלופדיה של הסקרנות!

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

אלפי נושאים, תמונות וסרטונים, מפתיעים, מסקרנים וממוקדים.

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

בואו לגלות, לחקור, ולקבל השראה!

אֵאוּרִיקַה - האנציקלופדיה של הסקרנות!

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