Կրուսկալի ալգորիթմի լաբիրինթոս գեներատոր

Կրուսկալի ալգորիթմը նվազագույն ընդգրկող ծառի ալգորիթմ է, որը կարող է հարմարեցվել լաբիրինթոս ստեղծելու համար: Այն հատկապես արդյունավետ է կատարյալ լաբիրինթոսներ ստեղծելու համար: Կրուսկալի ալգորիթմի այլընտրանքը Պրիմի ալգորիթմն է, որը նույնպես նվազագույն ընդգրկող ծառի ալգորիթմ է, բայց քանի որ դրանք ստեղծում են նույնական լաբիրինթոսներ, և Կրուսկալի գործողությունները ավելի արագ են, ես չեմ անհանգստացել Պրիմի ալգորիթմը իրականացնելու համար:

Կատարյալ լաբիրինթոսն այն լաբիրինթոսն է, որտեղ լաբիրինթոսի ցանկացած կետից դեպի ցանկացած այլ կետ կա ուղիղ մեկ ճանապարհ: Դա նշանակում է, որ դուք չեք կարող ի վերջո շրջել շրջանակներով, բայց հաճախ կհանդիպեք փակուղիների՝ ստիպելով ձեզ շրջվել և հետ գնալ:

Այստեղ ստեղծված լաբիրինթոսային քարտեզները ներառում են լռելյայն տարբերակ՝ առանց որևէ մեկնարկի և ավարտի դիրքերի, այնպես որ դուք կարող եք որոշել դրանք ինքներդ. լուծում կլինի լաբիրինթոսի ցանկացած կետից մինչև ցանկացած այլ կետ: Եթե ​​ցանկանում եք ոգեշնչել, կարող եք միացնել առաջարկվող սկզբի և ավարտի դիրքը և նույնիսկ տեսնել լուծումը երկուսի միջև:

Կրուսկալի ալգորիթմի մասին

Կրուսկալի ալգորիթմը ստեղծվել է ամերիկացի մաթեմատիկոս, վիճակագիր և համակարգչային գիտնական Ջոզեֆ Բեռնարդ Կրուսկալ կրտսերի կողմից։ Նա առաջին անգամ նկարագրել է ալգորիթմը 1956 թվականին իր «Գրաֆի ամենակարճ ընդգրկող ենթածառի և շրջիկ վաճառողի խնդրի մասին» հոդվածում։

Ալգորիթմը նախագծված է գրաֆի նվազագույն ճյուղավորված ծառը (MST) գտնելու համար՝ ապահովելով, որ բոլոր գագաթները կապված լինեն հնարավոր նվազագույն ընդհանուր եզրի կշիռով՝ միաժամանակ խուսափելով ցիկլերից։

Ինչպես է Կրուսկալի ալգորիթմը աշխատում լաբիրինթոսի ստեղծման համար

Քայլ 1. Նախաձեռնել

• Լաբիրինթոսի յուրաքանչյուր բջիջը դիտարկեք որպես առանձին հավաքածու (միակ բաղադրիչ):
• Հարակից բջիջների միջև գտնվող բոլոր պատերը թվարկեք որպես պոտենցիալ եզրեր։

Քայլ 2. Պատերի տեսակավորում

• Պատերը խառնեք կամ պատահականորեն դասավորեք։ Եթե այն իրականացնում եք որպես իրական Կրուսկալի ալգորիթմ, պատերը դասավորեք պատահական կարգով (քանի որ լաբիրինթոսի ստեղծումը կշիռներ չի պահանջում)։

Քայլ 3. Գործընթացային պատեր

• Անցեք խառնված պատերի միջով։
• Եթե պատով բաժանված երկու բջիջները պատկանում են տարբեր բազմությունների (այսինքն՝ դրանք դեռևս միացված չեն լաբիրինթոսում), հեռացրեք պատը և միացրեք բազմությունները։
• Եթե դրանք արդեն նույն հավաքածուի մեջ են, բաց թողեք պատը (ցիկլերից խուսափելու համար):

Քայլ 4. Շարունակեք մինչև ավարտը

• Կրկնեք այս գործընթացը մինչև բոլոր բջիջները միանան՝ կազմելով մեկ տարածվող ծառ։
• Վերջում յուրաքանչյուր բջիջ միացված է մյուսներին առանց օղակների կամ մեկուսացված հատվածների։

Քանի որ Կրուսկալի ալգորիթմը հիմնված է միաձուլվող բազմությունների վրա, այն կարող է օպտիմալացվել՝ օգտագործելով Union-Find ալգորիթմը, որը ապահովում է լաբիրինթոսի ստեղծման ընթացքում միացված բջիջները հետևելու արդյունավետ միջոց: Դուք կարող եք տեսնել Union-Find ալգորիթմի իմ PHP իրականացումը այստեղ՝ Հղում

Լրացուցիչ ընթերցանություն

Եթե ​​ձեզ դուր եկավ այս գրառումը, ձեզ կարող են նաև դուր գալ այս առաջարկները.

• Լաբիրինթոսի Գեներատոր Հորդարձ և Մահ
• Recursive Backtracker Maze գեներատոր
• Էլլերի ալգորիթմ Maze գեներատոր