| 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 |
|---|
| Poslano v recenzijo: | 04.04.2014 |
|---|
| Datum sprejetja članka: | 08.11.2014 |
|---|
| Datum objave: | 20.11.2014 |
|---|
| Založnik: | Electronic Journal of Combinatorics |
|---|
| 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: | 1884 |
|---|
| Število prenosov: | 264 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
