@חיים-כהן-5 אוקי, אז זה עניין אותי מאוד, כי בחנתי את זה בעבר.
האפשרות שהאלגוריתם מחשב באמת את כל האפשרויות ובוחר בקצר שבהם הוא כמעט בלתי אפשרי יש כאן יותר מידי משתנים בפרט אם יש לך 200 כתובות. (עבור 20 כתובות יש כ‑10¹⁷ מסלולים)
אז מה כן?
קודם כל האלגוריתם שלך תמיד יקבע את הכתובת הראשונה ברשימה ככתובת הראשונה בסיבוב, ואז היא רק תשקלל ממנו והלאה גם אם הוא נמצא בדיוק באמצע בין כל שאר הכתובת.
ואז הוא בודק את המרחק של כל שאר הכתובות מהכתובת ההיא ולוקח את הכתובת אם המרחק הכי מינימלי והופך אותו לשני ברשימה וכן הלאה...
ואז יש אימות נוסף שבא למנוע מצב שנשאר לסוף כתובת אחת רחוקה ושאינה חלק מקבוצת כתובות קרובה
בשלב הראשון זה מוודא שאתה לא חוצה את אותו מקום פעמיים מה שמוכיח על סיבוב מיותר
אבל כדי למנוע את המצב שכתובת מרוחקת קרובה יותר לנקודה כלשהיא בדרך מאשר מנקודת הסיום שממנה נשלחת לשם האלגוריתם עובד כך:
הוא לוקח כמה תחנות בודדות מהמסלול ומנסה להציב אותם בכל מיקום אחר ברשימה והוא בודק 2 דברים כמה נחסך על ידי דילוג על התחנה הזו וכמה נוסף על ידי העצירה החדשה, אם מתברר שהמקום החדש עדיף, מעבירים לשם.
אבל זה בעצמם החלק הכי מורכב של האלגוריתם שמכיל הכי הרבה אפשרויות וכדי להתמודד אם זה הוא מוגבל להזזה של 3 תחנות מקסימום בו זמנית.
ככה שיש כאן כמה חוסרים, הראשון יכול להיות תמיד שארגון בצורה שונה תהיה יעילה יותר אבל אם הזזה של 3 תחנות בלבד לא מגלה את זה אנחנו לעולם לא נדע את זה.
אז תכלס' אחרי ביצוע החישובים (אני? הAI כמובן...) הסיכוי שנגיע למסלול האפוטימלי באמת הוא כך:
עד 10 כתובות סיכוי מאוד גבוה כמעט תמיד
15-20 כתובות יורד לכשליש מהמקרים
40 כתובות ומעלה - סיכוי אפסי, כמעט תמיד יהיה מסלול קצר יותר (אם כי לא בהכרח בפער גדול)
ולשאלה החשובה באמת, כמה אנחנו רחוקים מהמסלול האופטימלי שזה לפי ההשערה יורד לממוצע של 4% (כ7 דקות לנסיעה בת 3 שעות - באמת לא קריטי) אחרי הרצת שני התיקונים.
מה שכן נשאר פתוח זה הכתובת הראשונה, אם היא הכתובת ממנה אתה באמת יוצא - מצוין לא תפסיד מכך כלום אבל אם נניח אתה לא יודע מה כתובת המוצא של השליח אז עצם זה שהתוכנה תקבע כתובת מסוימת לכתובת הראשונה תוריד אותנו בערך ב20% ממוצע מהמסלול האופטימלי
מקווה שהייתי ברור מספיק
בכל אופן, שאפו.
![ע"ה דכו"ע](/assets/uploads/profile/uid-24261/24261-profileavatar-1774768870385.png "ע"ה דכו"ע"){kind=avatar}
 { const baseUrl = "https://www.google.co.il/search?q=site:mitmachim.top"; const m = location.pathname.match(/^\/(topic|category)\/(\d+)/); const type = m ? m[1] : null; const id = m ? m[2] : null; let searchInput; function search(path = "") { const query = searchInput.value.trim(); if (query) { window.open(`${baseUrl}${path}%20${encodeURIComponent(query)}`, "_blank"); } } let buttons = {}; buttons.searchAll = { id: "bb-search-all", label: `חיפוש ${type ? "בכל הפורום" : ""}`, className: type ? "btn-secondary" : "btn-primary", callback: () => search(), }; if (type === "topic") { buttons.searchTopic = { label: "חיפוש בנושא זה", className: "btn-primary", callback: () => search(`/topic/${id}`), }; } else if (type === "category") { buttons.searchCategory = { label: "חיפוש בקטגוריה זו", className: "btn-primary", callback: () => search(`/category/${id}`), }; } buttons.cancel = { label: "ביטול", className: "btn-default", "data-bs-dismiss": "modal" }; const dialog = bootbox.dialog({ title: '<div style="text-align:center;"><img src="/assets/uploads/files/1625950269825-mt-google.png" width="400" alt="חיפוש בגוגל"></div>', message: '<input id="bb-inp" class="bootbox-input bootbox-input-text form-control" placeholder="הקלידו כדי לחפש בגוגל" autocomplete="off"/>', buttons, backdrop: true, show: true, onEscape: true }); dialog.on("shown.bs.modal", function () { searchInput = document.getElementById("bb-inp"); if (searchInput) { searchInput.focus(); searchInput.addEventListener("keydown", function (e) { if (e.key === "Enter") { e.preventDefault(); const query = this.value.trim(); if (query) { search(); dialog.modal("hide"); } } else if (e.key === "Escape") { e.preventDefault(); dialog.modal("hide"); } }); } const searchAllButton = document.getElementById("bb-search-all"); if (searchAllButton) { searchAllButton.title = "לחצו על אנטר כדי לחפש"; } }); })(); void 0;){kind=link}