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

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

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

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

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

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

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

Ինչպես է աշխատում Kruskal-ի ալգորիթմը Maze սերնդի համար

Քայլ 1: Սկզբնայնացնել

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

Քայլ 2: Դասավորեք պատերը

• Շեֆ կամ պատահական պատվիրեք պատերը: Եթե այն իրական Kruskal-ի ալգորիթմ է, ապա պատահական կարգով դասավորեք պատերը (քանի որ լաբիրինթոսային սերունդը չի պահանջում կշռաքարեր)։

Քայլ 3: Պրոցեսորային պատեր

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

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

• Կրկնեք այս պրոցեսը, մինչեւ բոլոր բջիջները միացված են, ձեւավորելով մեկ երկարություն ունեցող ծառ:
• Ի վերջո, յուրաքանչյուր բջիջ միացված է մյուսներին առանց պտույտների կամ մեկուսի հատվածների։

Քանի որ Kruskal-ի ալգորիթմը հենվում է միաձուլման կոմպլեկտների վրա, այն կարելի է օպտիմալացնել՝ օգտագործելով Union-Find ալգորիթմը, որն ապահովում է լաբիրինթոսային սերնդի ընթացքում կապակցված բջիջներին հետեւելու արդյունավետ եղանակ: Յունիոն-Find ալգորիթմի իմ PHP իրականացումը կարող եք տեսնել այստեղ. Disjoint Set (Union-Find Algorithm) PHP-ում