5032124662

1.1. OD PROBLEM U DO PROGRAMU

(2) Przejrzyj listę wszystkich niepokolorowanych jeszcze wierzchołków i dla każdego z nich sprawdź, czy jest połączony krawędzią z jakimś wierzchołkiem mającym aktualnie używany kolor. Jeżeli nie jest, opatrz go tym kolorem.

„Zachłanność” algorytmu wynika stąd, że w każdym kroku (tj. przy każdym z używanych kolorów) stara się on pokolorować jak największą liczbę wierzchołków, niezależnie od ewentualnych negatywnych konsekwencji tego faktu. Nietrudno wskazać przypadek, w którym mniejsza zachłanność prowadzi do zastosowania mniejszej liczby kolorów. Graf przedstawiony na rysunku 1.3 można pokolorować przy użyciu tylko dwóch kolorów; jednego dla wierzchołków 1, 3 i 4, drugiego dla pozostałych. Algorytm zachłanny, analizujący wierzchołki w kolejności wzrastającej numeracji, rozpocząłby natomiast od przypisania pierwszego koloru wierzchołkom / i 2, po czym wierzchołki 3 i 4 otrzymałyby drugi kolor, a dla wierzchołka 5 konieczne byłoby użycie trzeciego koloru.

Zastosujmy teraz „zachłanne” kolorowanie do grafu z rysunku 1.2. Rozpoczynamy od wierzchołka AB, nadając mu pierwszy z kolorów — niebieski; kolorem tym możemy także opatrzyć¹ wierzchołki AC, AD i BA, ponieważ są one „osamotnione”. Nie możemy nadać koloru niebieskiego wierzchołkowi BC, gdyż jest on połączony z (niebieskim) wierzchołkiem AB; z podobnych względów nie możemy także pokolorować na niebiesko wierzchołków BD, DA i DB, możemy to jednak zrobić z wierzchołkiem DC. Wierzchołkom EA, EB i EC nie można przyporządkować koloru niebieskiego — w przeciwieństwie do „osamotnionego” wierzchołka ED.

Weźmy kolejny kolor — czerwony. Przyporządkowujemy go wierzchołkom BC i BD; wierzchołek DA łączy się krawędzią z BD, więc nie może mieć koloru czerwonego, podobnie jak wierzchołek DB łączący się z BC. Spośród niepokolorowanych jeszcze wierzchołków tylko EA można nadać kolor czerwony.

Pozostały cztery niepokolorowane wierzchołki: DA, DB, EB i EC. Jeżeli przypiszemy DA kolor zielony, możemy go także przyporządkować DB, jednakże dla EB i EC musimy wtedy użyć kolejnego (żółtego) koloru. Ostateczny wynik kolorowania przedstawiamy w tabeli 1.2. Dla każdego koloru w kolumnie Ekstra prezentujemy te wierzchołki, które nie są połączone z żadnym wierzchołkiem w tym kolorze i przy innej kolejności przechodzenia zachłannego algorytmu przez wierzchołki mogłyby ten właśnie kolor uzyskać.

Zgodnie z wcześniejszymi założeniami, wszystkie wierzchołki w danym kolorze (kolumna Wierzchołki) odpowiadają zakrętom „uruchamianym” w danej fazie. Oprócz nich można także uruchomić inne zakręty, które z nimi nie kolidują (mimo że reprezentujące je wierzchołki mają inny kolor), są one wyszczególnione w kolumnie Ekstra.

Tak więc wedle otrzymanego rozwiązania, sygnalizacja sterująca ruchem na skrzyżowaniu pokazanym na rysunku 1.1 powinna być sygnalizacją czterofazową. Po doświadczeniach z grafem przedstawionym na rysunku 1.3 nie można nie zastanawiać się, czy jest rozwiązanie optymalne, tzn. czy nie byłoby możliwe rozwiązanie problemu przy użyciu sygnalizacji trój- czy dwufazowej.

1

Zgodnie z kolejnością przyjętą w tabeli na rysunku 1.3 — przyp. tłum.

Wyszukiwarka

Podobne podstrony:
21 1.1. OD PROBLEM U DO PROGRAMU {2}    for <v reprezentujący każdy niepokolorowan
17 1.1. OD PROBLEM U DO PROGRAMU RYSUNEK 1.1. Przykładowe skrzyżowanie zwłaszcza przy zawracaniu.
kulturystyka161 W ćwiczeniach od 15! do 156 działa przede wszystkim część środkowa mięśni czworobocz
> Od abaków do maszyny ENIAC i Internetu <U> Wszystko zaczęto się od maszyny ENIAC, do tego
> Od abaków do maszyny ENIAC i Internetu < 19 > > Od abaków do maszyny ENIAC i Internetu
Kurs C+ + Tutorial ten jest kompletnym opisem języka C++. Rozpoczyna się od wstępu do programowania
78251 str 062 063 (2) 30. OD PŁATNERZA DO FABRYKI Jak we wszystkich gałęziach wytwórczości, tak i w
W>y V r^ j3 ! ■ M
Szkoła zawodowa w latach 19^-1956 /problemy do pisemnych wypowiedzi/ 1,    Odbudowa,
^ %ZACZYNA SIĘ OD CIEBIETylko do 8 marca zniżka na wszystkie #kursoksiążki! 99 zł 79 zł 129 zł 99 zł
Od grosika do złotówki(*D(33E£QC£E© Projekt edukacji finansowej dla uczniów klas drugich i trzecich
Od grosika do złotówki 37-Jsi PS;Pakiet materiałów dydaktycznych dla nauczycieli: ★
skanuj0030 (171) 198 II. OD POCZĄTKÓW — DO UPADKU POWSTANIA sze ręce dźwigają jeszcze oręż wytępieni
Adam Rusek OD „GRZESIA" DO „GAZETKI MIKI”.. .63 Następne samodzielne periodyki rozrywkowe dla
Zadanie 19. (0-3) Z okazji dnia sportu w godzinach od 9:00 do 12:00 przeprowadzono połowę z wszystki
Zadanie 19. (0-3) Z okazji dnia sportu w godzinach od 9:00 do 12:00 przeprowadzono połowę z wszystki
Zadanie 19. (0-3) Z okazji dnia sportu w godzinach od 9:00 do 12:00 przeprowadzono połowę z wszystki

więcej podobnych podstron