Կրուսկալի ալգորիթմի լաբիրինթոս գեներատոր
Հրապարակվել է՝ 16 փետրվարի, 2025 թ., 18:05:48 UTC
Լաբիրինթոս գեներատոր՝ օգտագործելով Kruskal-ի ալգորիթմը՝ կատարյալ լաբիրինթոս ստեղծելու համար: Այս ալգորիթմը ձգտում է ստեղծել լաբիրինթոսներ միջին երկարության միջանցքներով և բազմաթիվ փակուղիներով, ինչպես նաև բավականին ուղիղ լուծումներով:Kruskal's Algorithm Maze Generator
Kruskal-ի ալգորիթմը նվազագույն տարածվող ծառի ալգորիթմ է, որը կարող է հարմարեցվել լաբիրինթոսային սերնդի համար: Այն հատկապես արդյունավետ է կատարյալ լաբիրինթոսներ ստեղծելու համար։ Կրուսկալի ալգորիթմի այլընտրանքը Պրիմի ալգորիթմն է, որը նույնպես մինիմալ տարածվող ծառի ալգորիթմ է, բայց քանի որ դրանք գեներացնում են նույնական լաբիրինթոսներ եւ Kruskal-ի վազքն ավելի արագ է, ես չեմ անհանգստացրել Պրիմի ալգորիթմի իրականացումը։
Կատարյալ լաբիրինթոսն այն լաբիրինթոսն է, որտեղ լաբիրինթոսի ցանկացած կետից դեպի ցանկացած այլ կետ կա ուղիղ մեկ ճանապարհ: Դա նշանակում է, որ դուք չեք կարող ի վերջո շրջել շրջանակներով, բայց հաճախ կհանդիպեք փակուղիների՝ ստիպելով ձեզ շրջվել և հետ գնալ:
Այստեղ ստեղծված լաբիրինթոսային քարտեզները ներառում են լռելյայն տարբերակ՝ առանց որևէ մեկնարկի և ավարտի դիրքերի, այնպես որ դուք կարող եք որոշել դրանք ինքներդ. լուծում կլինի լաբիրինթոսի ցանկացած կետից մինչև ցանկացած այլ կետ: Եթե ցանկանում եք ոգեշնչել, կարող եք միացնել առաջարկվող սկզբի և ավարտի դիրքը և նույնիսկ տեսնել լուծումը երկուսի միջև:
Կրուսկալ ալգորիթմի մասին
Կրուսկալի ալգորիթմը ստեղծել է ամերիկացի մաթեմատիկոս, վիճակագիր եւ համակարգչային գիտությունների դոկտոր Ջոզեֆ Բերնարդ Կրուսկալ կրտսերը։ Նա առաջին անգամ ալգորիթմը նկարագրել է 1956 թվականին իր «Գրաֆի ամենակարճ spanning Subtree-ի եւ ճանապարհորդող վաճառողի խնդրի մասին» թղթում:
Ալգորիթմը նախատեսված է գրաֆի նվազագույն տարածվող ծառը (MST) գտնելու համար, ապահովելով, որ բոլոր վերնիսայները միացված լինեն նվազագույն հնարավոր ընդհանուր եզրային քաշի հետ, միաժամանակ խուսափելով ցիկլերից:
Ինչպես է աշխատում Kruskal-ի ալգորիթմը Maze սերնդի համար
Քայլ 1: Սկզբնայնացնել
- Լաբիրինթոսում գտնվող յուրաքանչյուր բջիջին վերաբերվեք որպես առանձին կոմպլեկտ (եզակի բաղադրիչ):
- Թվարկեք բոլոր պատերը հարեւան բջիջների միջեւ որպես պոտենցիալ եզրեր:
Քայլ 2: Դասավորեք պատերը
- Շեֆ կամ պատահական պատվիրեք պատերը: Եթե այն իրական Kruskal-ի ալգորիթմ է, ապա պատահական կարգով դասավորեք պատերը (քանի որ լաբիրինթոսային սերունդը չի պահանջում կշռաքարեր)։
Քայլ 3: Պրոցեսորային պատեր
- Շիկացած պատերի միջով իտերատ...
- Եթե պատով բաժանված երկու բջիջները պատկանում են տարբեր կոմպլեկների (այսինքն՝ դեռեւս լաբիրինթոսում չեն միացված), հեռացրեք պատը եւ միացրեք կոմպլեկտները:
- Եթե դրանք արդեն նույն շարքում են, բաց թողեք պատը (ցիկլերից խուսափելու համար):
Քայլ 4. Շարունակել մինչեւ ավարտը
- Կրկնեք այս պրոցեսը, մինչեւ բոլոր բջիջները միացված են, ձեւավորելով մեկ երկարություն ունեցող ծառ:
- Ի վերջո, յուրաքանչյուր բջիջ միացված է մյուսներին առանց պտույտների կամ մեկուսի հատվածների։
Քանի որ Kruskal-ի ալգորիթմը հենվում է միաձուլման կոմպլեկտների վրա, այն կարելի է օպտիմալացնել՝ օգտագործելով Union-Find ալգորիթմը, որն ապահովում է լաբիրինթոսային սերնդի ընթացքում կապակցված բջիջներին հետեւելու արդյունավետ եղանակ: Յունիոն-Find ալգորիթմի իմ PHP իրականացումը կարող եք տեսնել այստեղ. Disjoint Set (Union-Find Algorithm) PHP-ում