Linje mellan motsatta hörn på ytan av en hyperkub?

Jäklar, tänkte fel. De banor jag räknade på är ofta inte de kortaste. I t ex 4D kuber där banan måste gå genom 2D-sidor, räknade jag med banor av typen
(0,0,0,0) --> (x1,0,0,1) --> (x2,0,1,1) --> (1,1,1,1)
och fann genom minimering att minsta s fås för x1=1/3, x2=2/3 med
s = 3•√(1²+(1/3)²) = √10.
(Samma med n=4 och d=2 i formeln jag skrev förut.)

Här kan man även se det jag nämnde om vinklar förut. Koordinatskillnaderna i de tre stegen ges av (1/3,0,0,1), (1/3,0,1,0) och (1/3,1,0,0). Dvs varje kvadrat genomkorsas på samma sätt: 1/3 sida i en riktning och genom hela sidan i en annan.

Men det finns en kortare bana!
(0,0,0,0) --> (0,0,1,1) --> (1,1,1,1)
med längden
s = 2•√(1²+1²) = √8.
Men DETTA bör iaf vara den kortaste banan för n=4 och d=2.

Hur blir detta i det allmänna fallet för andra n och d? Hmm..

Ok det här är över min nivå så en ren gissning här då:
Dela upp i udda och jämna n. För udda så verkar det bra att ta 3 variabler i 2 steg typ (0,0,0,0,0) ->
(1,1/2,0,0,0) ->(1,1,1,0,0) och sista steget som ovan -> (1,1,1,1,1)
För jämna precis som du skrev där ovan då. Och så bara mata på?

Är de linjerna genom ytor på 2D-sidor likadana för insida som utsida av celler i 4D till exempel? Likt √5 kan betraktas som linje på 2D-sidor av en 3D-kubs insida.

Jag har blivit nästan lite för intresserad av det här problemet och kommit fram till en del, men jag ska försöka att hålla mig kort.

Det är najs att försöka tänka intuitivt i 4D eller ännu fler D, men det duger liksom inte för säkra resultat. Man måste formulera det på något sätt där resultaten kan kontrolleras utan någon speciell sorts högre dimensionell intuition.

Det vi har i verktygslådan är
* Euklidiska koordinater x₁, x₂, x₃, ...
* Ett avståndsmått mellan två punkter med koordinatskillnaderna Δx₁, Δx₂, Δx₃, ... som ges av
Δs = √(Δx₁²+Δx₂²+Δx₃²+...)
(vilket stämmer bra i t ex 3D).
* Lätt visualiserbara exempel upp t o m 3D, som vi kan försöka generalisera.

Du frågar: "Är de linjerna genom ytor på 2D-sidor likadana för insida som utsida av celler i 4D till exempel?" Men vad ska detta betyda? Om du tänker på banan längs 2D-sidorna på en 3D-kub, så går denna längs två sidor på t ex följande sätt:
(0,0,0) --> (1/2,1,0) --> (1,1,1).
Koordinatskillnaderna i de båda stegen är
(1/2,1,0) resp (1/2,0,1).
(Den totala sträckan är alltså 2•√((1/2)²+1²)=√5.)
I vilken mening är dessa "likadana"? Den första rör sig i xy-planet och den andra i xz. Skillnaden är att den första y-riktning byts ut mot en z-riktning. Som om man man viker upp planet.

Jag föreslår alltså att "likadana" ska stå för att man byter plats mellan en eller fler koordinater. Så t ex är är även koordinatskillnaderna (1,1/2,0), (0,1/2,1), (1,0,1/2) och (0,1,1/2) "likadana" -- eftersom de bara skiljer sig åt i att vi har vikt upp ett plan så att t ex x-riktningen har blivit en y-riktning osv.

Detta är även lätt att generalisera till hur många dimensioner vi vill.

Så t ex har vi en bana genom 4D-kub, som bara får röra sig längs 2D-sidor (dvs max ändra två koordinater i taget) som ges av
(0,0,0,0) --> (1/3,1,0,0) --> (2/3,1,1,0) --> (1,1,1,1)
med koordinatskillnaderna
(1/3,1,0,0), (1/3,0,1,0) och (1/3,0,0,1)
som är "likadana"!. Den sammanlagda sträckan blir
s = 3•√(1²+1/3²) = √10

Detta är dock inte den kortaste sträckan runt 4D-kuben genom 2D-sidor. En kortare ges som sagt av
(0,0,0,0) --> (1,1,0,0) --> (1,1,1,1)
med de "likadana" koordinatskillnaderna
(1,1,0,0) och (0,0,1,1)
och sammanlagd sträcka
s = 2•√(1²+1²) = √8

Tyvärr verkar dock inte alltid den kortaste sträckan av ett visst slag alltid bestå av "likadana" koordinatskillnader. Jag trodde att det var så, men det är nog fel. Mer om det i ett annat inlägg. Måste ju ju svara Igni-ferroque också. Nån gång.

Tack för input!

Du har nog iaf rätt om [n,2] = banor genom 2D-sidor runt en n-dimensionell kub. Notera dock att dessa banor INTE uppfyller TS krav på att ha "likadana" steg. Gissar att det bara är i vissa specialfall som den kortaste [n,d]-banan uppfyller det villkoret, t ex när n=kd för något heltal k.

Den kortaste banan i [5,3] verkar vara med de två "likadana" stegen i
(0,0,0,0,0) --> (1/2,1,1,0,0) --> (1,1,1,1,1)
med längden 2•√((1/2)²+2•1²)=3.

Notera dock att den kortaste banan i [10,3] INTE bara är att upprepa [5,3] två gånger (först för de första fem koordinaterna, och sen för de sista fem). En kortare bana ges av två st 3-diagonaler, och så de sista 4 koordinaterna med med de två stegen i
(0,0,0,0) --> (1/2,1/2,1,0) --> (1,1,1,1).
Längden blir då 2•√(3•1²)+2•√(2•(1/2)²+1²)=2•√3+√6≈5.91.

Gissar (men vet inte) att alla [n,d] med n>2d, och där n inte är en multipel av d, är av detta slag. Dvs börja med d-diagonaler tills man har kvar mindre än 2d dimensioner.

Notation: låt t ex cₐ stå för c,c,...,c där c upprepas a gånger.

Om d≤n<2d TROR jag att den kortaste [n,d]-lösningen ges av
(0ₐ,0ₑ,0ₑ) --> ((1/2)ₐ,1ₑ,0ₑ) --> (1ₐ,1ₑ,1ₑ)
där a+e=d och a+2e=n, dvs a=2d-n och e=n-d.

En kandidat till kortaste väg i [10, 3]:
Längd ~ 5,83.

Grymt!

Snälla, berätta hur du hittade denna?

Här är differenserna:

Tack. Jag minns inte den exakt tankegången, men jag slumpade i alla fall lite olika vägar, bland annat på formen

som gav bäst resultat. I går kväll gjorde jag även en steepest descent med ansatsen

och fick samma resultat. Om det är ett globalt minimum vet jag inte, men skulle tro det. Intressant att notera från de beräkningarna är att det inte tycks vara optimalt att gå mer än två steg längs någon dimension, åtminstone inte med denna ansats. Exempelvis är c = 1, e = d = 0,75 och f = 0.

Fallet [n, d] = [5, 2] som nämndes några inlägg tillbaka:
Längd ~ 3,61.

Monte Carlo alltså. Najs, måste jag också testa! Antar att du fick decimaltal som resultat egentligen (eller slumpade du bråktal?), och att du gissade de exakta kvoterna (t ex 1/3) sen från det.

Ok, även om det iaf inte är omedelbart uppenbart hur det kan bli samma lösning med olika antal rader i ansatsen.

Noterar också att differenserna är symmetriska. Din lösning har "likadana" koordinatskillnader både bakåt och framåt, som synes i t ex mitt förra inlägg. De längsta stegen är det första och det sista, och de kortaste det näst första och det näst sista.

Går det här att generalisera till andra [n,d]? Finns det någon allmän formel?

Riktigt najs det med. Också med en symmetri i koordinatskillnaderna framåt och bakåt.

Exakt, jag slumpade flyttal mellan 0 och 1 och gissade. Men steepest descent är snabbare och ger bättre precision.

För [n = 2*k+1, 2] verkar diagonalen i matrisen bestå av

0,
1 - 1/(k+1),
1/k,
1 - 2/(k+1),
2/k,
1 - 3/(k+1),
3/k,
1 - 4/(k+1),
4/k,
..., och så vidare tills man når 1 i motsatta hörnet.

För exempelvis [9, 2] (k = 4) blir det då

Varför det här är optimalt (om det är det) har jag ingen aning om.