Miklix

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

Հրապարակվել է՝ 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-ում

Կիսվեք Bluesky-ումԿիսվել Facebook-ումԿիսվեք LinkedIn-ումԿիսվեք Tumblr-ումԿիսվեք X-ումԿիսվեք LinkedIn-ումԿպցնել Պինթրեսթում

Միկել Բանգ Քրիստենսեն

Հեղինակի մասին

Միկել Բանգ Քրիստենսեն
Mikkel-ը miklix.com-ի ստեղծողն ու սեփականատերն է: Նա ունի ավելի քան 20 տարվա աշխատանքային փորձ՝ որպես պրոֆեսիոնալ համակարգչային ծրագրավորող/ծրագրային ապահովման մշակող և ներկայումս լրիվ դրույքով աշխատում է եվրոպական խոշոր ՏՏ կորպորացիայի մեջ: Երբ նա բլոգ չի գրում, նա իր ազատ ժամանակն անցկացնում է հետաքրքրությունների, հոբբիների և գործունեության լայն շրջանակի վրա, որոնք որոշ չափով կարող են արտացոլվել այս կայքում ընդգրկված թեմաների բազմազանության մեջ: