Ciekawy problem algorytmiczny

[krzyszp]

Byłem ostatnio na spotkaniu określanym terminem "Networking meeting", a polegający na zawieraniu nowych znajomości biznesowych wśród świeżo powstałych firm z regionu, w którym mieszkam. Spotkanie było zorganizowane w dość ciekawy sposób, a więc:

1. Lista zaproszonych zawierała 48 nazwisk (a więc 48 uczestników - ale obecnych było 42).
2. Sala zawierała 8 stolików po 6 miejsc siedzących.
3. Każdy uczestnik ma 60 sekund, aby pozostałym osobom przy stoliku opowiedzieć, czym zajmuje się jego firma, po czym (na sygnał) zmienia stolik lub zostaje jeszcze jedną 60s kolejkę.
4. Stoliki mają oznaczenie literowe (a,b,c,d,e,f,g,h), a miejsca przy stolikach cyfrowe (1..6).

Problem zakłada znalezienie algorytmu wyliczającego możliwie najmniejszą liczbę przejść dla każdej osoby, tak aby:
1. Opowiedzieć wszystkim o swojej firmie.
2. Wysłuchać informacji od wszystkich pozostałych.

Jako dodatkowe utrudnienie można potraktować fakt, że ilość zaproszonych/stolików jest zmienna (dla kolejnych spotkań).
Generalnie dane wyjściowe powinny być w formie:

Jan Kowalski

1. Stolik i krzesło: f4
2. Stolik i krzesło: d5
3. Postój
4. Stolik i krzesło c3

Problemem tym zainteresowałem się, gdy na tym spotkaniu na którym byłem - w pewnym momencie pojawił się niezły bałagan ;-) Organizatorzy nie przemyśleli tej sprawy i w pewnym momencie wylądowałem przy stoliku z tymi samymi osobami, z którymi rozmawiałem wcześniej :-).

Wczoraj spędziłem ze dwie godziny próbując wymyślić algorytm, ale poległem - w ogóle taki istnieje?

[sesef]

czy to nie jest przypadkiem coś w rodzaju problemu komiwojażera?

[Bober]

Proponuję tak:
- usiąść przy jednym stoliku, z kijem w ręku i zostać;
- powiedzieć swoje, przepytać pozostałe 5 osób, po czym przepędzić wszystkich,  żeby przyszło nowych 5 osób (oczywiście jakby chciał usiąść ktoś, kto już siedział wcześniej - przepędzamy dziada)
- i tak do końca :P

Posadzić przy każdym stoliku jednego takiego strażnika, i chociaż parę osób wyjdzie posiniaczonych, zadanie rozwiąże się samo  XP

No i na koniec narada strażników, którzy wcześniej nie mieli szansy pogadać, a że wszyscy uzbrojeni, może być to ciekawa debata...

[krzyszp]

czy to nie jest przypadkiem coś w rodzaju problemu komiwojażera?

Tak mi też się wydaje, ale jest to problem chyba trochę bardziej skomplikowany (48 komiwojażerów?) 8)

Niemniej, sam problem powoduje u mnie wydzielanie dymu z uszu, więc chyba sobie odpuszczę...  :wth:

Proponuję tak:
- usiąść przy jednym stoliku, z kijem w ręku i zostać;
- powiedzieć swoje, przepytać pozostałe 5 osób, po czym przepędzić wszystkich,  żeby przyszło nowych 5 osób (oczywiście jakby chciał usiąść ktoś, kto już siedział wcześniej - przepędzamy dziada)
- i tak do końca :P

Posadzić przy każdym stoliku jednego takiego strażnika, i chociaż parę osób wyjdzie posiniaczonych, zadanie rozwiąże się samo  XP

No i na koniec narada strażników, którzy wcześniej nie mieli szansy pogadać, a że wszyscy uzbrojeni, może być to ciekawa debata...

I to jest chyba jedyne (proste w implementacji) rozwiązanie problemu :attack:

[Pantarhei]

Phi! To banalnie proste!jeśli się ma kolegę matematyka. ;)

So- Wystarczy siedem stolików po siedem krzeseł, co da 49 osób. Każda osoba ma numer od 1 do 7 i każdy stół ma numery od 1 do 7. W pierwszej rundzie mówią tylko osoby 1, po czym przesiadają się do następnego stolika po prawo (stoły stoją w kole). Po szóstej rundzie każdy wraca do swojego stolika, a swoje rundy odbywają następne numery. Na razie każdy opowiedział o swojej firmie 7x6 czyli 42 osobom
Po tym etapie do każdego stołu siadają osoby z numerem nominalnym stołu, czyli jedynki razem, dwójki razem itd. i każda po kolei opowiada o swojej firmie, co daje dodatkowe 6x i pula uzupełnia się do 48 poinformowanych o firmie osób.
:D  :D  :D

[Aegis Maelstrom]

Fajne rozwiązanie, oczywiście stosowalne też dla dowolnych n stolików x m miejsc i nie trzeba na końcu wracać do stolika początkowego.

Jeśli ktoś tego jeszcze nie widzi - tak opisany problem tak naprawdę sprowadza się do problemu sprawdzenia każdej kombinacji w zamku szyfrowym.  :P Rozmowy przy stolikach odbywają się synchronicznie, a jeśli każdy opowiedział każdemu swoją historią to oznacza przecież, że każdy jej wysłuchał. :> Różnica jest taka, że w jednym obrocie sprawdzanie jest n kombinacji - ale to detal pomijalny.

Początkowo chciałem być taki optymalny, by strzelić algorytm oszczędzający czas - wszyscy obecni przy stole opowiadają sobie w jednym rundzie, a potem się rozchodzą. Na moje oko oznacza to konieczność wyznaczenia m-1 dróg na grafie (dróg takich, że osoby startujące z tego samego węzła zeszłyby się dopiero po przejściu wszystkich pozostałych stolików; drogą m-tą są ci, którzy będą siedzieć aż do ostatniego cyklu). Dalej jest analogicznie do algorytmu Nuriela: każda z m dróg ma n osób, z których pierwsza przechodzi na pozycję drugiej, druga na trzeciej... a ostatnia na pierwszej).

Mam goraczkę i moge się mylić, ale IMVHO nawet już widzę iteracyjny sposób konstrukcji takiej drogi: powiedzmy, że jesteśmy w węźle 1. Droga 1. to 1-->2-->3-->...-->n. Droga 2. to 1-->n-->2-->3-->...-->n-1, i tak dalej... jak widać, drogi też zmieniają się "cyklicznie". Ostatnia droga to 1-->3-->4-->...-->n-->2. Nie jest to jedyna mozliwa kombinacja dróg, ale najbardziej oczywista.

Na końcu oczywiście musi dojść do spotkania wszystkich tych, którzy byli na jednej drodze i nie mogli się spotkać. Jednym z takich stolików będzie stolik wiecznie siedzących.

Tyle okiem nieinformatyka i niematematyka w ciężkiej gorączce. Gdybym się mylił, niech mnie ktoś poprawi. :D

[gielo]

Jeżeli ktoś lubi algorytmy to może posiedzieć nad tym i pomyśleć, ja jednak po ostatnim roku studiów mam ich powyżej uszów i nie chce mi się za to brać. Lubie programowanie ale dzięĸi mojemu wykładowcy trochę mi ta dziedzina zbrzydła   :wth:

[krzyszp]

Nie wiem czemu, ale nie dostałem na maila powiadomienia o odpowiedziach :-(

Przetłumacze wasze odpowiedzi na ang. i zarzucę problem wspólnikowi  XD - niech spróbuje to ugryźć "praktycznie".

Generalnie fajny pomysł na aplikację dla osób zajmujących się tego typu problematyką (może warto poszukać klientów?).