The number of moves of the largest disc in shortest paths on Hanoi graphs

Aumann, Simon; Götz, Katharina; Hinz, Andreas; Petr, Ciril

| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Prva stran > Izpis gradiva

Izpis gradiva

Naslov:	The number of moves of the largest disc in shortest paths on Hanoi graphs
Avtorji:	ID Aumann, Simon (Avtor) ID Götz, Katharina (Avtor) ID Hinz, Andreas (Avtor) ID Petr, Ciril (Avtor)
Datoteke:	Electronic_Journal_of_Combinatorics_2014_Aumann_et_al._The_number_of_moves_of_the_largest_disc_in_shortest_paths_on_Hanoi_graphs.pdf (376,70 KB) MD5: 54B714EE86235B1DDA9E49C4E1B94267 PID: 20.500.12556/dkum/18893bd4-6b0b-478d-a2db-1bf89baee89d http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i4p38
Jezik:	Angleški jezik
Vrsta gradiva:	Znanstveno delo
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	FNM - Fakulteta za naravoslovje in matematiko
Opis:	In contrast to the widespread interest in the Frame-Stewart conjecture (FSC) about the optimal number of moves in the classical Tower of Hanoi task with more than three pegs, this is the first study of the question of investigating shortest paths in Hanoi graphs $H_p^n$ in a more general setting. Here $p$ stands for the number of pegs and $n$ for the number of discs in the Tower of Hanoi interpretation of these graphs. The analysis depends crucially on the number of largest disc moves (LDMs). The patterns of these LDMs will be coded as binary strings of length $p-1$ assigned to each pair of starting and goal states individually. This will be approached both analytically and numerically. The main theoretical achievement is the existence, at least for all $n \geqslant p(p-2)$ , of optimal paths where $p-1$ LDMs are necessary. Numerical results, obtained by an algorithm based on a modified breadth-first search making use of symmetries of the graphs, lead to a couple of conjectures about some cases not covered by our ascertained results. These, in turn, may shed some light on the notoriously open FSC.
Ključne besede:	graph theory, Tower of Hanoi, Hanoi graphs, shortest paths, symmetries, breadth-first search
Status publikacije:	Objavljeno
Verzija publikacije:	Objavljena publikacija
Leto izida:	2014
Št. strani:	str. 1-22
Številčenje:	Letn. 21, št. 4
PID:	20.500.12556/DKUM-67353
ISSN:	1077-8926
UDK:	519.17
COBISS.SI-ID:	17173081
ISSN pri članku:	1077-8926
NUK URN:	URN:SI:UM:DK:CUEEYWTE
Datum objave v DKUM:	14.08.2017
Število ogledov:	1714
Število prenosov:	248
Metapodatki:
Področja:	Ostalo
:	AUMANN, Simon, GÖTZ, Katharina, HINZ, Andreas in PETR, Ciril, 2014, The number of moves of the largest disc in shortest paths on Hanoi graphs. The Electronic journal of combinatorics [na spletu]. 2014. Vol. 21, no. 4, p. 1–22. [Dostopano 15 marec 2025]. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=67353 Kopiraj citat

Skupna ocena:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 glasov)
Vaša ocena:	Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:

Podobna dela iz repozitorija:

Podobna dela iz ostalih repozitorijev:

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:	The Electronic journal of combinatorics
Skrajšan naslov:	Electron. j. comb.
Založnik:	N.J. Calkin and H.S. Wilf
ISSN:	1077-8926
COBISS.SI-ID:	6973785

Sekundarni jezik

Jezik:	Slovenski jezik
Naslov:	Število premikov največje ploščice na najkrajših poteh v hanojskih grafih
Opis:	Kljub širšemu zanimanju za Frame-Stewartovo domnevo o optimalnem številu potez v klasičnem problemu hanojskega stolpa z več kot tremi položaji, je to prva študija o najkrajših poteh v hanojskih grafih $H_p^n$ , kjer $p$ predstavlja število položajev in $n$ število ploščic, če graf interpretiramo kot graf stanj hanojskega stolpa. Študija se še posebej loti analize premikov največje ploščice. Vzorec teh premikov je zakodiran kot binarni niz dolžine $p-1$ in prirejen vsakemu paru začetnega in končnega stanja posebej. K analizi problema se pristopa tako analitično kot tudi numerično. Glavni teoretični dosežek je obstoj optimalnih poti za vse $n \geqslant p(p-2)$ , na katerih so nujni $p-1$ premiki največje ploščice. Numerični rezultati so pridobljeni z modificiranim algoritmom, zasnovanim na algoritmu iskanja v širino. V namene optimizacije iskanja se uporabijo simetrije grafov. Numerična evidenca vodi k nekaj domnevam o (ne)obstoju, ki jih teoretični rezultati ne pokrivajo in mogoče nam pomaga razkriti tudi kakšno skrivnost še nerazrešene Frame-Stewartove domneve.
Ključne besede:	teorija grafov, hanojski stolp, hanojski graf, najkrajša pot, simetričnosti, iskanje v širino

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)

0 - 0 / 0

Ni komentarjev!

Nazaj