Rihma tasakaalustaja probleem (Factorio)

Belt Balancer Problem



Lahendus:

UTU = universaalne läbilaskevõime piiramatu

UTU tasakaalustajad on olemas 3, 4 ja 5 vöö jaoks ja tõenäoliselt mis tahes arvu vööde jaoks . Näiteid on toodud selles Jupyteri märkmikus koos Pythoni rakendusega iteratiivne algoritm voolu arvutamiseks mis tahes rihmade ja jaoturite komplekti jaoks .



Tsiteerin siin mõnda märkmikku neile, kes ei soovi linki järgida. Ma nimetan jagajaid ristmikeks, sest nii need tegelikult toimivad.



Iga vöö koosneb ühiku pikkustest segmentidest, mida mängus nimetatakse plaatideks. Mudelis kujutame ette, et iga rihm voolab vasakult paremale koordinaatide suunas$ x $ja iga ristmik, mis ühendab kahte vööd antud plaadi vasakus servas. Pange tähele, et mõned praktikas kasutatavad tasakaalustajad sisaldavad silmuseid ja neid ei saaks meie mudel kujutada ilma lõpmatu pikkusega vööta.



Vööplaatide olekut tähistab tihedus$ 0 le rho le 1 $ja kiirus$ 0 le v le 1 $. Väärtus$ v = 1 $on normaalne vöö kiirus ja$ rho = 1 $on rihma maksimaalne kandevõime. On selge, et saame ainult$ v<1$kui$ rho = 1 $; see on seisund, kus rihm on täielikult koormatud ja allavoolu ei ole piisavalt väljavoolu.

Sissevoolu ülesvoolu määrab tihedus$ rho_ {üles} $domeeni vasakus servas ($ x = 0 $) ja väljavoolu allavoolu täpsustab$ v_ {alla} $domeeni paremas servas. UTU testimise huvides oleme huvitatud ainult nende väärtuste seadmisest nullile või ühele, kuid üldisemad väärtused töötavad alloleva algoritmiga.

Peamine täidetav tingimus on konserveerimine igal ristmikul. Esemete voo piki vööd annab toode$ rho v $ja me nõuame, et ristmikku minev voog oleks võrdne väljuva vooga. See osutub palju keerulisemaks, kui ma eeldasin, et täidan selle tingimuse igal ristmikul viisil, mis on kooskõlas jagajate tööga, ja see kajastub allolevas koodis. Kui aega saan, lisan loodetavasti täpsema matemaatilise kirjelduse tingimustest, mida algoritmis kaitsmise saavutamiseks rakendatakse.



Lühidalt: algselt panime paika$ rho = 0 $ja$ v = 1 $kõikjal, välja arvatud piiridel. Iga korduse korral me ainult suurendame$ rho $ja vähenema$ v $; iteratiivsed väärtused on õigete väärtuste puhul alati madalamad (vastavalt ülemised). Igal kordamisel kontrollime ristmikke, kus sissevool on suurem kui väljavool (eelmise lause tingimuste tõttu ei saa vastupidist olukorda juhtuda), ja kohandame neid, et saavutada kaitse ja võrdne väljavool. Võimaluse korral suurendatakse selle saavutamiseks väljavoolu tihedust. Kui see pole võimalik (kuna üks väljavoolu tihedustest ulatub 1 -ni), määratakse kogu liigne väljavool teisele rihmale. Kui see pole võimalik (kuna mõlemad väljavoolutihedused ulatuvad 1 -ni), täitub üks või mõlemad sissevooluvööd ja aeglustuvad.

Siin on lihtsustatud vaade ühest voolust läbi UTU 3-vöö tasakaalustaja: 3-vööga UTU mängusArvud on tihedused ja värvid kiirused. Jällegi on vool vasakult paremale ja iga must joon tähistab ristmikku ('splitter'). See näeb mängus välja selline:

4-vööline UTU

See tundub üsna lihtne ja ilmne; Ma olen üllatunud, et seda pole juba Factorio foorumitesse postitatud.

Siin on neljavööline UTU tasakaalustaja:

sisestage pildi kirjeldus siia

ja üks viis selle koostamiseks mängus:

sisestage pildi kirjeldus siia

Ma arvan, et see on juba välja mõeldud ja postitatud Factorio foorumitesse, kuigi jõudsin selleni iseseisvalt.

Sülearvutil on ka 5 vööga tasakaalustaja, kuid ma ei ole võtnud aega selle ehitamiseks mängus.

Sülearvuti sisaldab koodi, millega luua ja testida kõiki UTU atribuudi nõutavaid sisendite ja väljundite komplekte.

Märkate, et need tasakaalustajad on ehitatud naiivselt nii palju ristmikke sisse pannes ja neid vapustades. Ma oletan, et kui te seda piisavalt teete, saate alati UTU tasakaalustaja, kuid mul pole aimugi, kuidas tasakaalustaja pikkus rihmade arvuga kasvab. Huvitaval kombel on minu 4-vöö tasakaalustaja lühem (mudeli esitusel, kus vööd saab tahtmatult kombineerida tegeliku geomeetria pärast muretsemata) kui 3-rihma tasakaalustaja. Kuid 5-vöö tasakaalustaja on palju pikem.

Sülearvuti algoritmi saab kasutada ka muude stsenaariumide, näiteks$ m $-kuni$ n $tasakaalustajad koos$ m $pole võrdne$ n $, või katsetada teistes vastustes esitatud ideed, et a$ 2n $UTU tasakaalustaja saab üles ehitada$ n $TÜ tasakaalustaja. Oleks lihtne lisada see mõnele toorele jõule või intelligentsemale otsingule, mis püüab leida teatud omadustega võimalikult lühikese tasakaalustaja.

Pean ütlema, et olen üllatunud selle probleemi keerukusest, mida ma esialgu arvasin, et seda on palju lihtsam lahendada. Eelkõige ei ole ma veel suutnud lahendusele selget lähenemist välja pakkuda, ainult märkmiku korduv algoritm. Tänan teid väga huvitava probleemi eest.

Värskenda : Kommentaarides väidetakse, et 3-vöö tasakaalustaja ebaõnnestub, kui ülemine ja alumine väljund on keelatud. Siin on selle olukorra pilt, mis näitab täielikku läbilaskevõimet:

Pange tähele, et jagajad teevad täpselt seda, mida @Rhamphoryncus väidab, et nad peaksid tegema. Näiteks tõmbur, mis ühendab kahte alumist vööd plaadil 2 (kolmas plaat), tõmbab mõlemast kahest ülesvoolu rihmast täpselt 1/2 täisvööd. Sama juhtub jaoturiga, mis ühendab need kaks vööd plaadil 4.


See pole päris matemaatiline vastus, kuid tundub, et leiutate uuesti mitteblokeeruva minimaalse ulatusega lüliti ja võrkude sulgemise. Sel juhul on jaotur sisuliselt 2x2 ristlüliti ja te kasutate neid suuremate lülitite ehitamiseks.

Kui teil on NxN -lüliti (antud juhul 2x2 -jaotur), saate lihtsa näitena kasutada 3N -i neist (3*2 = 6), et luua lüliti, mis on N2xN2(ja seega populaarne 4x4 tasakaalustaja, mis kasutab 6 jaoturit).

Kui soovite 16x16, siis võite võtta 12 neist 4x4 tasakaalustajatest, 4 sisendpoolt, 4 väljundpoolt ja 4 keskelt, kusjuures iga lüliti on ühendatud järgmise astme iga lülitiga ühe rihmaga. Seejärel saate seda protsessi korrata, et saada 256x256 jne.

Pärast seda pole ma matemaatikas päris kindel, aga mina mõtle saate näiteks disaini pooleks lõigata, et saada pool läbilaskevõimest (nt 6x 4x4 tasakaalustajad, et saada 8x8). Seejärel saate asju, mis ei ole 2 volitused, lihtsalt ühendamata mõned sisendid/väljundid.


See pole täielik vastus, kuid

Eeldus 1: piiramatu 4: 4 tasakaalustaja on võimalik. Ma usun, et see on piiramatu läbilaskevõime.

Võtke 4: 4 tasakaalustaja, asendage iga 2: 2 tasakaalustaja 4: 4 tasakaalustajaga ja teil peaks olema tasakaalustaja 8: 8, mis on minu arvates piiramatu

Veidi üldisemalt: kui meil on n: n tasakaalustaja, kus n on võimsus 2, saame 2n: 2n, võttes 4: 4 tasakaalustaja disaini ja asendades iga 2: 2 tasakaalustaja an: n tasakaalustajaga .

See eeldab, et see on alati geomeetriliselt võimalik.

Induktsiooni abil peaks kõigil 2 võimsusel olema piiramatu läbilaskevõimega tasakaalustaja.

Lisa 1: Eeldades, et ülaltoodu kehtib siis, kui 2 võimsuse korral on piiramatu läbilaskevõimega võimalik piiramatut tasakaalustajat väiksema arvu puhul saavutada täiendavate sisendite/väljundite blokeerimisega.

Lisa 2: (See on puhas spekulatsioon) Kui meil on rihmade komplekt kindlas järjekorras ja kõik liiguvad samas suunas, peaksime saama vahetada mis tahes kahe rihma asukohta järjekorras, lubades kõigil teistel vöödel kasutada maa -aluseid rihmasid. paar ruutu. Seega saame rihmasid suvaliselt permeerida, kuna 2 rihma permutatsioon on võimalik. See peaks tähendama, et saame alati ehitada 2: 2n tasakaalustajaid n: n üksustest.