פתרון מבוך (Maze)

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

יש להגיע מההתחלה (החץ האדום) עד לסוף (החץ הירוק).

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

אבל כאמור - ניתן את הכבוד ל-ChatgPT:

זה הפתרון שהוא "מצא": גאוני, לא? שוברים את הקירות והחוקים, ואולי מגיעים ואולי לא.

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

את בעיית המבוך ניתן להציג כבעייה מתורת הגראפים בה יש קודקודים (nodes) וקשתות (arcs) שמחברות בין צמדי קודקודים.

קודקוד אחד יהיה כמובן בנקודת ההתחלה (החץ האדום) ואחד בנקודת הסיום (החץ הירוק), ואת שאר הקודקודים נמקם בנקודות המחלוקת, במקומות שבהם יש לפחות שתי אפשרויות לאן להמשיך, או כשאין לאן להמשיך:

מיקמתי את 30 הקודקודים השונים במבוך, שוב - כשיש יותר מאפשרות אחת לאן להמשיך, או כשאין לאן. למשל - מ-N1 עד ל-N2 אין מה להתלבט ולהתבלבל, ורק ב-N2 צריך להחליט אם לרדת למטה (ולהגיע ל-N3 דרך ללא מוצא) או להמשיך למעלה.

מכיוון שהמבוך פשוט מדי ויש לו פתרון אחד שניתן למצוא בקלות, ואין אפשרות להסתבך בלולאות אין סופיות, עשיתי תיקון קטן והוספתי את קודקוד N30 במקום שקודם היה חסום, וכעת יש סכנה להיכנס ללופ: N30,N22,N20,N18,N17,N15,N13,N30.

ניצור טבלת קודקודים ונאכלס אותה ב-30 קודקודים:

Create Table T_Nodes

              (Node Char(3) Constraint PK_T_Nodes Primary Key);

Insert

Into   T_Nodes(Node)

Values ('N1'),('N2'),('N3'),('N4'),('N5'),('N6'),('N7'),('N8'),('N9'),('N10'),('N11'),('N12'),('N13'),('N14'),('N15'),('N16'),('N17'),('N18'),('N19'),('N20'),('N21'),('N22'),('N23'),('N24'),('N25'),('N26'),('N27'),('N28'),('N29'),('N30');

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

Create Table T_Arcs

              (Node1 Char(3) Constraint FK_T_Arcs_Node1 Foreign Key References T_Nodes(Node),

              Node2 Char(3) Constraint FK_T_Arcs_Node2 Foreign Key References T_Nodes(Node),

              Constraint PK_T_Arcs Primary Key(Node1,Node2));

Insert

Into   T_Arcs(Node1,Node2)

Values ('N1','N2'),

              ('N2','N3'),

              ('N2','N4'),

              ('N4','N29'),

              ('N4','N5'),

              ('N5','N6'),

              ('N5','N7'),

              ('N7','N8'),

              ('N7','N9'),

              ('N9','N10'),

              ('N9','N11'),

              ('N11','N12'),

              ('N11','N30'),

              ('N22','N30'),

              ('N24','N30'),

              ('N13','N30'),

              ('N13','N15'),

              ('N15','N16'),

              ('N15','N17'),

              ('N22','N23'),

              ('N20','N22'),

              ('N20','N21'),

              ('N18','N20'),

              ('N18','N19'),

              ('N17','N18'),

              ('N17','N25'),

              ('N25','N26'),

              ('N25','N27'),

              ('N27','N28');

ולפתרון: נשלוף את N1, נקשר אותו בעזרת CTE רקורסיבי למי שיש לו קשת איתו, את השני למי שלו יש קשר, וכו'. נקפיד בהתחלה להכפיל את מספר הקשתות כך שיכילו גם את N1-N2 וגם את N2-N1 על ידי Union All, ובחלק הרקורסיבי - נשרשר את הקודקודים אליהם הגענו, גם כדי שנדע מהי הדרך מ-N1 ל-N27, וגם כדי שלא נעבור באותו קודקוד פעמיים וחלילה נסתבך בלולאה אינסופית:

With AllArcs As

(Select       Node1,

              Node2

From   T_Arcs

Union All

Select Node2,

              Node1

From   T_Arcs),

T As

(Select       Cast('N1' As Char(3)) Node,

              Cast(',N1,' As Varchar(Max)) Path

Union All

Select A.Node2 Node,

              Concat(T.Path,A.Node2,',') Path

From   T

Inner Join AllArcs A

              On T.Node=A.Node1

Where  T.Path Not Like Concat('%,',A.Node2,',%')

              And A.Node1<>'N27')

Select *

From   T

Where  Path Like '%N27,';

הסט AllArcs הוא Union All של טבלה T_Arcs עם עצמה בסדר הפוך של הצמתים. עמודה Path משרשרת רקורסיבית את הצמתים עם פסיקים מפרידים, והיא משמשת בפסוקית ה-Where למנוע פנייה לקודקודים בהם היינו כבר. התנאי 'A.Node1<>'N27 נועד למנוע את המשך החיפוש לאחר שנגיע ליעד N27. התנאי ',Path Like '%N27 נועד להחזיר מסלולים שנגמרו ב-N27.

אלו הם שני המסלולים מ-N1 ל-N27.

ניתן לוותר על ה-Union All וכך לחסוך Scan כפול של הטבלה ולהסתפק באחד, במחיר של סיבוך הקוד של ה-CTE הרקורסיבי ובדיקה בכל איטרציה של שני צידי הקשת - קצת פחות אינטואיטיבי, אבל זול יותר במשאבים, ואת הקודקוד שנוסף נחשב בפסוקית ה-Cross Apply:

With T As

(Select       Cast('N1' As Char(3)) Node,

              Cast(',N1,' As Varchar(Max)) Path

Union All

Select CA.Node,

              Concat(T.Path,CA.Node,',') Path

From   T

Inner Join T_Arcs A

              On (T.Node=A.Node1

                     And T.Path Not Like Concat('%,',A.Node2,',%')

                     And A.Node1<>'N27')

              Or (T.Node=A.Node2

                     And T.Path Not Like Concat('%,',A.Node1,',%')

                     And A.Node2<>'N27')

Cross Apply (Select IsNull(NullIf(A.Node2,T.Node),A.Node1) Node) CA)

Select *

From   T

Where  Path Like '%N27,';