שאלה באלגוריתם למציאת רצף

[שרוני251]

שאלה באלגוריתם למציאת רצף

היי.. אני צריכה למצוא אלגוריתם שמוצא לי רצף של n כוכביות בתוך מטריצה בגודל M*M (כמובן ש M>n) הכוכביות יכולות להופיע רצוף באלכסון , בשורה או בתור... לשורה ולתור מצאתי אלגוריתם שמוצא רצף אבל הוא לא יעיל (אם אעבור על כל המטריצה זה סדר של M^2...) אשמח לקבל רעיון שיהיה יותר יעיל.. ואם אין לכם יותר יעיל אבל יש לכם אלגו למציאת רצף אלכסון גם אשמח לקבל תודה!

 

[גיל14]

בכל מקרה תצטרכי לעבור על כל המטריצה.

 

[שרוני251]

איך מוצאים רצף מוכל בתוך אלכסונים?

 

[1ca1]

עוברים על האלכסונים

זה בגדול M אלכסונים, כל אחד חסום בO(M) (כי האלכסון הראשי, אורכו sqrt(2)*M) ואז תקבלי M^2 אני לא רואה דרך לשפר את הM^2 עבור הדבר הזה (כי ריצה על match של "שורה" (יכול להיות גם טור או אלכסון) חייב להיות O(M)), ואין דרך "לחסוף שורות" לפי מה שאני רואה (פרט למיקבול פשוט של האלגוריתם, חתיכה לשניים של המטריצה ושליחה ל2 מעבדים, אבל זה כבר צריך מחשב PRAM, אבל כמובן צריך יותר מחשבים לעיבוד בכל צעד). לכן חיפוש בשורות זה O(M^2), וכך גם אלכסונים וטורים, סה"כ 3 פעמים O(M^2) שזה O(M^2). אם מדובר במשימה יותר מתוחכמת (pattern matching, בין אם זה חד או דו מימדי וכו') אז אולי כבר שווה להכניס תותחים כבדים (לpattern matching אפשר להשתמש בKMP (או גירסא דו-מימדית שלו), אפשר גם (תלוי בדיוק במה שאת רוצה ובאלף-בית שמחפשים בו) לעשות משהו עם טרנספורם פורייה).

 

[גיל14]

אורכו של האלכנוס הראשי כמה? ../images/Emo3.gif

 

[1ca1]

ארג.... צודק

sqrt(M)*M, פשוט היה לי בראש אחד על אחד... בכל אופן, עלה לי רעיון של ביצוע בM^2*O(N) (ובהנחה כי N קבוע בתחילת ריצת התוכנית, זה בעצם O(1)*M^2). בעצם עוברים על כל התאים במטריצה, לכל תא, בודקים את הn-1 מימינו, משמאלו, באלכסון לו ומעליו ומתחתיו, סה"כ יש כאן 8*O(N), שזה מצטמצם לO(1) במקרה הקבוע..., זה גם פשוט מאוד תכנותית (עוברים על המטריצה, עוברים לפוקנציה check cell, ואז היא קוראת לפונקציה שבודקת ימין ושמאל, למעלה למטה ובאלכסון).

 

[שרוני251]

אמממ תודה לך... מה זה KMP?

 

[1ca1]

אלגוריתם לPattern Matching

פחות רלוונטי אצלך (כי את יכולה פשוט לעבור ולספור רצף לצורך העניין), אבל אם את רוצה לחפש צורה ספציפית בתוך הטקסט, ולא מעוניינת לעשות בשיטה "הנאיבית" (נניח את המילה shalom אז לבדוק את s, אם יש s לבדוק שהאות הבאה היא h, וכך לבדוק את האותיות הבאות עד לm...), אז אפשר להשתמש בה. http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm