Problem krzyczących beduinów

Michał ‘mina86’ Nazarewicz | 19 lutego 2008

Na pustyni stoją beduini (na początku każdy wie tylko jak ma na imię), z których każdy ma swoje unikalne, w skali całej pustyni, imię. Są usytuowani w ten sposób, że jeżeli jakiś beduin coś krzyknie to z pewnością, przynajmniej jeden, inny beduin go usłyszy. Beduini maja na tyle podzielną uwagę, że jeżeli słyszą głosy wielu innych beduinów to są w stanie je rozróżnić i niejako "zakolejkować" otrzymane wiadomości, ale nie są w stanie rozpoznać, z której strony ani od kogo usłyszeli konkretną informację (zarówno, gdy odbierają wiele wiadomości jednocześnie jak i gdy odbierają tylko jedną wiadomość).

Należy opracować taki protokół komunikacji, aby dowolny beduin mógł przekazać informację dowolnemu innemu beduinowi, którego imię zna. Protokoły powinny generować jak najmniej szumu na pustyni, w końcu to nie problem krzyczeć dalej każdą otrzymaną informację tak, że dotrze ona nawet w najdalsze zakątki pustyni. Rozpatrywać następujące cechy i ograniczenia pojedynczo lub łącznie:

  1. na pustynię mogą przychodzić nowi beduini,
  2. beduini mogą umierać z głodu lub pragnienia (i) pozostawiając jednak spójność grafu połączeń lub (ii) dzieląc graf połączeń na dwie lub więcej części,
  3. beduini mają ograniczoną pamięć i dlatego nie są w stanie pamiętać drogi do każdego z beduinów będących na pustyni, ale są w stanie pamiętać wszystkich swoich sąsiadów (tzn. beduinów, którzy są w zasięgu ich głosu) oraz
  4. beduini znają swoje położenie geograficzne.

Część druga

Na pustyni są również małe beduidziątka, które są na tyle niesforne, że nie są w stanie usiedzieć w jednym miejscu i wędrują po całej pustyni. Nie ustępują jednak swoim rodzicom pod względem siły głosu i niezależnie gdzie sie nie znajdują są w zasięgu głosu przynajmniej jednego beduina (i nigdy nie ma sytuacji, gdy przechodzą "nagle" z zasięgu jednego beduina do drugiego beduina nie będąc przez pewien czas w zasięgu obu tych beduinów). Każde z beduidziątek ma, podobnie jak rodzice, swoje unikalne, w skali całej pustyni, imię.

Należy opracować taki protokół komunikacji, aby dowolne beduidziątko mogło przekazać informację dowolnemu innemu beduidziątkowi, którego imię zna. Poza cechami i ograniczeniami z części pierwszej rozpatrzeć sytuację, gdy beduidziątka znają swoje położenie geograficzne (a więc jeżeli również beduini znają swoje położenie, to beduidziątka są w stanie określić obszar, na którym słychać głoś danego beduina).