Feb 2017
1 / 8
Feb 2017
Feb 2017
quenthui
Feb '17

To jest specyficzne zadanie. Zastanów się nad komentarzem pod zadaniem.
Nie wiem, czy ten algorytm ma jakąś nazwę. Po prostu szukasz, które korytarze generują cykle.

lisensolikum
Feb '17

Tak, próbuję dodać tunel, jeśli powoduje cykl to go usuwam i wypisuję. Może nie trzeba analizować za każdym razem od zera, ale na to nie mam pomysłu.

quenthui
Feb '17

Raczej nie, skoro masz tle cały czas
Nie musisz sprawdzać całego grafu od zera dla kazdego polaczenia. Wystarczy sprawdzić, czy z wyjscia połączenia da się dostac do jego wejscia. Albo do innego połączenia,które doprowadzi nas do wejścia aktualnie badanego przejscia

lisensolikum
Feb '17

Wystarczy sprawdzić, czy z wyjscia połączenia da się dostac do jego wejscia.

To akurat oczywiste, tylko jak zrobić to odpowiednio szybko? Zwykły BFS z b do a, jakieś wykrywanie cykli, próby spamiętywania... na razie nie zdają rezultatu.

narbej
Feb '17
lisensolikum

Może nie trzeba analizować za każdym razem od zera? :wink:

PS
Komentarz pod zadaniem dotyczył, a raczej nie uwzględnił, że w treści zadania "mówi się" o instalacji pilotażowej, a dopiero potem zaczęto wdrażać końcową instalację tuneli, już według znanych, poprawionych założeń. :wink:

narbej
Feb '17
1
  1. Dodajemy nowy tunel.
  2. IF Gdy nie wiemy, czy spowoduje on "zacycklenie" analizujemy od zera i ewentualnie usuwamy
    ELSE go to 1

PS
Nie wiem, czy można sprawdzać cykliczność/acykliczność nie od zera, może można?
Ale w zadaniu nie musimy tego robić za każdym razem, raz po raz [oczywiście jak musimy to ja chyba robiłem to od zera].
A kiedy nie musimy tego robić, ani od zera ani w ogóle?:

  1. Gdy nowy tunel łączy dwie nieodwiedzane, wolne, komnaty
  2. Gdy łączy odwiedzoną z nieodwiedzoną
  3. Gdy łaczy dwie odwiedzone komnaty, ale wiemy,że nie spowoduje to cyklu. Ciekawostka - a skąd to niby możemy wiedzieć? Puszczając się od zera? A może jakiś inny, szybszy, sprytny algorytm zaczynający się na literę Z..... ........?
  4. Dopiero wtedy, gdy nie umiemy tego stwierdzić inaczej, zapuszczamy nasze sprawdzenie od zera.

PS 2
Oczywiście nie pamiętam jak ja to zrobiłem, w końcu 5 latek to trochę czasu jest, a nie mam ochoty oglądać [tylko zerknąłem] na swoj stary, brzydki kod.