Akademska digitalna zbirka SLovenije - logo
ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • The number of moves of the largest disc in shortest paths on Hanoi graphs [Elektronski vir]
    Aumann, Simon ...
    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.
    Source: The Electronic journal of combinatorics [Elektronski vir]. - ISSN 1077-8926 (Vol. 21, iss. 4, 2014, P4.38 (22 str.))
    Type of material - e-article
    Publish date - 2014
    Language - english
    COBISS.SI-ID - 17173081

    Link(s):

    http://www.combinatorics.org/ojs/index.php/eljc/article/download/v21i4p38/pdf
    Digital Library of the University of Maribor – DLUM

Shelf entry