מחפש אלגוריתם

[kobi2579]

מחפש אלגוריתם

למציאה: האם האלגוריתם מכיל מעגל מאורך זוגי או לא... בתודה מראש!

 

[אמיתי ר]

לא הבנתי מה זה

אלגוריתם שמכיל מעגל מאורך זוגי...

 

[kobi2579]

מעגל מאורך זוגי

מספר קשתות זוגי במעגל

 

[אמיתי ר]

אתה אולי מתכוון למעגל בגרף?

אם כן, אז האם הגרף מכוון או לא?

 

[kobi2579]

האם למעגל בגרף יש מס' קשתות זוגי

 

[gil levi]

מכוון או לא?

יעזור גם אם תכתוב את הבעיה בצורה של "קלט: ......, שאלה:......".

 

[yonyl]

פיתרון לשתי האפשרויות

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

 

[אמיתי ר]

יש דרכים יעילות הרבה יותר

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

 

[yonyl]

אתה טועה

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

 

[johnny d]

הגדרות זה עניין חשוב.

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