קרוסקאַל ס אַלגערידאַם - די קאַנסטראַקשאַן פון אַ אָפּטימאַל ראַם

אין די פרי 19 יאָרהונדערט געאָמעטער Jakob סטיינער פֿון בערלין שטעלן די אַרבעט פון ווי צו פאַרבינדן דרייַ Villages אַזוי אַז זייער לענג איז געווען די שאָרטיסט. שפּעטער, ער סאַמערייזד די פּראָבלעם: עס איז required צו געפֿינען אַ פונט אין אַ פלאַך, די דיסטאַנסע פֿון עס צו n אנדערע פּוינץ זענען די לאָואַסט. אין די 20 יאָרהונדערט, עס האלט צו אַרבעטן אויף דעם טעמע. עס איז באַשלאָסן צו נעמען אַ ביסל ווייזט און פאַרבינדן זיי אין אַזאַ אַ וועג אַז די דיסטאַנסע צווישן זיי איז געווען די שאָרטיסט. דאס אַלע איז אַ ספּעציעל פאַל פון די פּראָבלעם ווייל געלערנט.

"זשעדנע" אַלגערידאַם

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

דערגייונג אַ מינימום קאַרקאַס וואָג

וויעוועד אַלגערידאַם קאַנסטראַקץ אַ אָפּטימאַל ראַם ציילן. די פּראָבלעם פון עס איז ווי גייט. דן ונדירעקטעד גראַפיק אָן פּאַראַלעל עדזשאַז און לופּס, און די שטעלן פון עדזשאַז איז געגעבן די וואָג פֿונקציע ד, וואָס אַסיינז די נומער צו יעדער ברעג E - וואָג ריפּ - וו (E). די וואָג פון יעדער סאַבסעט פון די פּלוראַליטעט פון ריבס איז די סאַכאַקל פון די ווייץ פון זייַן עדזשאַז. רעקווירעד צו געפֿינען די סקעלעט פון אַ קליין וואָג.

באַשרייַבונג

קרוסקאַל ס אַלגערידאַם אַרבעט. ערשטער, אַלע עדזשאַז פון די ערשט גראַפיק זענען עריינדזשד אין אַסענדינג סדר פון די ווייץ. טכילעס, די ראַם טוט ניט אַנטהאַלטן קיין ריבס אָבער כולל אַלע ווערטיסעס. נאָך די ווייַטער שריט פון די אַלגערידאַם צו די שוין קאַנסטראַקטאַד טייל פון די קאַרקאַס, וואָס איז אַ ספּאַנינג וואַלד, איין ברעג איז צוגעגעבן. עס איז ניט אויסדערוויילט אַרביטרעראַלי. אַלע די עדזשאַז פון די גראַפיק, ניט בילאָנגינג צו די ראַם, קענען זיין גערופֿן רויט און גרין. די שפּיץ פון יעדער רויט עדזשאַז זענען אין דער זעלביקער קאָמפּאָנענט אונטער קאַנסטראַקשאַן וואַלד קאַנעקטיוויטי, און די גרין טאַפּס - אַנדערש. דעריבער, אויב איר לייגן צו די רויט ברעג, עס איז אַ ציקל, און אויב די גרין - ווי באקומען נאָך דעם שריט די האָלץ קאָננעקטעד קאַמפּאָונאַנץ וועט זיין ווייניקער ווי איינער. אזוי, דער ריזאַלטינג קאַנסטראַקשאַן קענען ניט לייגן קיין רויט ברעג, אָבער קיין גרין ברעג קענען ווערן צוגעלייגט צו באַקומען די וואַלד. און מוסיף אַ גרין ברעג מיט מינימום וואָג. דער רעזולטאַט איז אַ ראַם פון מינימום וואָג.

ימפּלאַמענטיישאַן

דינאָוט די איצטיקע וואַלד עף עס דיוויידז די שטעלן פון ווערטיסעס אין די פעלד פון קאַנעקטיוויטי (זייער פאַרבאַנד Forms ו, און זיי זענען דיסדזשאָינט). ביי ביידע עדזשאַז פון די רויט ווערטיסעס זיי ליגן אין איין שטיק. טייל (רענטגענ) - די פֿונקציע אַז פֿאַר יעדער ווערטעקס רענטגענ קערט אַ חלק פון די נאָמען, עס געהערט רענטגענ. פאַרייניקן (X, י) - אַ פּראָצעדור אַז טוט בויען אַ נייַ צעטיילונג, קאַנסיסטינג פון קאַמביינינג פּאַרץ פון רענטגענ און י און אַלע די אנדערע טיילן. זאל ען - נומער פון עדזשאַז. אַלע די קאַנסעפּס זענען ינקלודעד אין קרוסקאַל ס אַלגערידאַם. ימפּלעמענטאַטיאָן:

1. צולייגן אַלע די עדזשאַז פון די גראַפיק פון די 1 צו ען-טה אַסענדינג ווייץ. (אַי, ביי - איך מיט אַפּעקס ברעג נומער).

2. פֿאַר איך = 1 צו ען טאָן.

3. רענטגענ: = טייל (אַי).

4. י: = טייל (צוויי).

5. אויב רענטגענ טוט ניט גלייַך י דעמאָלט וניטע (X, י), צו אַרייַננעמען מיט דעם ברעג ו איך נומער.

קערעקטנאַס

זאל ג - ראַם פון דער אָריגינעל גראַפיק קאַנסטראַקטאַד ניצן די קרוסקאַל אַלגערידאַם און ד - זייַן אַרבאַטרערי ראַם. מיר האָבן צו באַווייַזן אַז וו (ה) איז נישט גרעסער ווי וו (ד).

לאָזן ב - פּלוראַליטעט פון Fins ד, פּ - אַ פּלוראַליטעט פון Fins טי אויב ד איז נישט זיין גלייך ווי ה, דעמאָלט עס איז אַ ראַם ריפּ און ה, ניט בילאָנגינג צו ש ש עט אַדזשוין די ציקל, עס איז גערופֿן סי C באַזייַטיקן פֿון קיין ברעג עס, בילאָנגינג ש מיר קריגן אַ נייַ ראַם, ווייַל די עדזשאַז און ווערטיסעס איז די זעלבע. זייַן וואָג איז נישט גרעסער ווי וו (ד), זינט וו (און) ניט מער וו (עס) אין אַ מאַכט קרוסקאַל אַלגערידאַם. דעם אָפּעראַציע (פאַרטרעטער ה ף ד ד ריבס אויף ריבס) וועט זיין ריפּיטיד ווי לאַנג ווי באַקומען טי די וואָג פון יעדער סאַבסאַקוואַנט באקומען ראַם איז נישט גרעסער ווי די פֿריִערדיקע וואָג, וואָס ימפּלייז אַז וו (ה) איז נישט גרעסער ווי וו (ד).

די ראָובאַסטנאַס פון קרוסקאַל ס אַלגערידאַם גייט פֿון די טעאָרעם פון ראַדאָ-עדמאָנדס אויף מאַטראָידס.

אַפּפּליקאַטיאָן עקסאַמפּלעס קרוסקאַל אַלגערידאַם

דן גראַפיק מיט נאָודז אַ, ב, C, ד, E און ריבס (א, ב), (א, E), (ב, C), (ב, E), (C, ד), (C, E) , (ד, E). די ווייץ פון עדזשאַז זענען געוויזן אין די טיש און אין די פיגור. טכילעס, קאַנסטראַקשאַן וואַלד ו כּולל אַלע די ווערטיסעס פון די גראַפיק און טוט ניט אַנטהאַלטן קיין ריבס. אַלגאָריטהם קרוסקאַל ערשטער לייגן ריפּ (א, E), זינט די וואָג האט די לאָואַסט, און די ווערטיסעס א און E זענען אין פאַרשידענע קאַמפּאָונאַנץ געהילץ קאַנעקטיוויטי פֿ '(ריפּ (א, E) איז גרין), דעמאָלט דער ריפּ (C, ד), ווייַל אַז לפּחות דעם ברעג וואָג פון גראַפיק עדזשאַז, ניט בילאָנגינג צו ו, און עס איז גרין, דעמאָלט פֿאַר די זעלבע סיבות צווואַקסן ברעג (א, ב). אבער די ברעג (ב, E) איז דורכגעגאנגען, אַפֿילו כאָטש ער און דער מינימום וואָג פון די רוען עדזשאַז, ווייַל עס איז רויט: די ווערטיסעס ב און E- געהערן צו דער זעלביקער קאָמפּאָנענט פון וואַלד קאַנעקטיוויטי ו, וואָס איז, אויב מיר לייגן צו ו דעם ברעג (ב, E), איז געגרינדעט ציקל. דעמאָלט צוגעגעבן גרין ברעג (ב, C), איז דורכגעגאנגען רויט ברעג (C, E), און דעמאָלט ד, E. אזוי, עדזשאַז זענען צוגעגעבן סאַקווענטשאַלי (א, E), (C, ד), (א, ב), (ב, C). פֿון ניהעראַ אָפּטימאַל ראַם און באשטייט פון דער אָריגינעל גראַפיק. אַזוי אין דעם פאַל עס אַפּערייץ אַ אַלגערידאַם קרוסקאַל. אַ משל איז געוויזן.

די פיגור ווייזט אַ גראַפיק, וואָס באשטייט פון צוויי קאָננעקטעד קאַמפּאָונאַנץ. די דרייסט שורות אָנווייַזן די אָפּטימאַל ראַם ריבס (גרין) קאַנסטראַקטאַד ניצן די קרוסקאַל אַלגערידאַם.

די שפּיץ בילד ווייזט דער אָריגינעל גראַפיק, און די דנאָ - אַ סקעלעט פון מינימאַל וואָג, געבויט פֿאַר אים דורך ניצן די אַלגערידאַם.

די סיקוואַנס פון די צוגעלייגט ריבס (1.6); (0,3), (2,6) אָדער (2,6), (0,3) - איז ניט וויכטיק; (3,4); (0,1), (1,6) אָדער (1,6), (0,1), אויך זאָרגן (5,6).

קרוסקאַל ס אַלגערידאַם פינדס פּראַקטיש אַפּלאַקיישאַן, למשל, צו אַפּטאַמייז די גאַסקאַט קאָמוניקאַציע, ראָודז אין נייַ האָוסינג יסטייץ לאָוקאַליטיז אין יעדער מדינה, ווי ווויל ווי אין אנדערע קאַסעס.