FANDOM


A Kibogozó (angolul untangled) készségfejlesztő játék lényege, hogy a felületen lévő pontokat úgy kell átrendezni, hogy egy vonaluk se keresztezze a másikat. Mintha gumiszalagok lennének a pontok között, vagy gráfok lennének.

Változatai Szerkesztés

  • Gyakorló változat, egyre nehezebb feladatokkal, néhány rögzített ponttal: Dont cross the line / ne keresztezd a vonalat
  • Testre szabható egyszerű változat, Type: 6-25 mozgatható csomóponttal: Untangle / kibogozó

Gráfelméleti alapok Szerkesztés

  • Egy struktúra lehet összefüggő vagy több egységre bomló
  • Ha egy rendszert áttekintéséhez rendezzük, az "kifeszítés"
  • Az elemek vagy csomópontok kapcsolati hálózata a topológia
  • Ha van egy jól meghatározható alap vagy kiindulópont, amihez minden kapcsolódik, akkor az egy Fa-gráf
  • Lehetséges olyan kapcsolat, amely csak egy irányú
  • Egy struktúra annál bonyolultabb, minél több elágazással rendelkező csomópontok vannak.
  • A kapcsolatokat lehet mélységében feltárni DFS (Depth First Search, magyarulMélységi keresés) vagy BFS (Szélességi keresés)
    • Mélységi - gyors: az útvonalat megjegyezve addig haladok előre, amíg lehetséges, ha elakadok, csak az előző elágazásig megyek vissza, akkor próbálok másik utat
    • Szélességi - alapos: Amikor a kiindulóponttól minden utat végigpróbálok, és csak akkor megyek tovább, ha az adot pontban mindent felderítettem.
  • A DFS algoritmus
Community content is available under CC-BY-SA unless otherwise noted.