W pracy rozważono problem eksploracji anonimowego nieskierowanego grafu przez bezpamięciowego robota. Zaprojektowane strategie eksploracji cechują się własnością lokalnej sprawiedliwości, tj. kolejne krawędzie trawersowane przez robota wybierane są na podstawie lokalnych informacji tak, aby zapewnić równomierne wykorzystanie krawędzi w sensie pewnego kryterium. Okazuje się, że odpowiedni dobór kryterium jest kluczowy do zapewnienia parametrów eksploracji, porównywalnych z błądzeniem losowym. Pokazano, że pierwsza ze zbadanych strategii (OF), która wybiera lokalnie najdawniej użytą krawędź, prowadzi do nieokresowych eksploracji z nierównomiernym obciązeniem krawędzi. Z kolei strategia LUF, która wybiera lokalnie najrzadziej użytą krawędź, osiąga równomierność eksploracji w O(D|E|) krokach, gdzie D oznacza średnicę grafu, a E zbiór jego krawędzi.
Autorzy
- Colin Cooper,
- David Ilcinkas,
- Ralf Klasing,
- dr inż. Adrian Kosowski link otwiera się w nowej karcie
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1007/978-3-642-02930-1_34
- Kategoria
- Publikacja monograficzna
- Typ
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Język
- angielski
- Rok wydania
- 2009
