ullman123 (2)

■ł DZIAŁANIA W MUUU.U KU At»JNYM

Najprostsze pytanie rckurencyjne, jakie się nasuwa, brzmi: ..Które par> miast (x,y) są połączone lotami, tzn. żc można dostać się z miasta x do miasta y w jednym lub więcej rejsach? Te pary miast będą tworzyć relację Dostępne (X/ y), a opisuje ją następujący zestaw reguł:

1. Dostępne (x, y) ♦- Rejsy {a, x, y, d, r)

2. Dostępne (x, y) •— Dostępne (x, z) AND Dostępne (z, y)

Inne postacie rckurencji

W przykładach 4.34 i 4.36 korzy staliśmy z tak zwanej rekurencji prawostronnej, w której relacja rckurencyjna Następny występowała po relacji liDB Kolejny. Można tworzyć analogiczną regułę z rckurcncją lewostronną, wówczas relacja rckurencyjna zostaje umieszczona w regule jako pierwsza. Zapis naszych reguł w postaci lewostronnej przedstawia się następująco:

1.    Następny(x, y) <- Kolejny (x, y)

2.    Następny(x, y) <- Następny(x, z) AND Kolejny (z, y)

Mówiąc bardziej obrazowo: y następuje po x, jeśli jest albo kolejnym odcinkiem x. albo jest kolejnym odcinkiem pewnego filmu następującego po x Rckurcncyjnej relacji można użyć nawet dwa razy. wówczas otrzymuje się tak zwaną rekurcncję nieliniową:

1.    Następny(x, y) <- Kolejny (x, y)

2.    Następny(x_f y) <- Następny(x, z) AND Następny (z, y)

Mówiąc bardziej obrazowo: y następuje po .t, jeśli jest albo kolejnym odcinkiem albo jest następnym odcinkiem pewnego filmu następującego po*. Wszystkie te trzy postacie reguł definiują tę sama relację Następny: zbiór wszystkich par (x, y) takich, że odcinek y jest kolejnym po kolejnym, ...(dowolnie dużo razy) kolejnym odcinku x.

Z pierwszej reguły wynika, że do relacji Dostępne należą te pary miast, między którymi bezpośrednio kursują samoloty; wartości określające linię a. czas odlotu d oraz czas przylotu r są dobrane tutaj arbitralnie. W drugiej regule zapisano takt. że jeśli można dolecieć z miast x do miasta z oraz można dolecieć z miasta z do miastay, to można dolecieć również z miasta x do miasta y. Zauważmy, żc w tej regule występuje rekureneja w postaci nieliniowej, którą szczegółowo omów iono w ramce zatytułowanej ..Inne postacie rckuren-cji’\ Ta postać jest trochę dogodniejsza w tym miejscu, ponieważ inny zapis

tej reguły wymagałby użycia trzech dodatkowych zmiennych, potrzebnych do opisu krotek relacji Re i yy.

Obliczenie relacji Dostępne polega na przetworzeniu tego samego algorytmu itcracyjnego, który przedstawiliśmy w p. 4.4.2. Z zastosowania reguły numer 1 do relacji Dostępne należą następujące pary: (SF, DEN), (SF, DAL), (DEN, CHI), (DAL, CHI). (DAL, NY) oraz (CHI, NY). To tc siedem par. które są oznaczone krawędziami na rys. 4.19.

W następnym kroku rekurencji stosujemy rekurcncyjną regułę numer 2 i otrzymujemy pary krawędzi, które mają wspólny wierzchołek. Stąd otrzymuje się dodatkowo pary (SF, CHI), (DEN, NY) oraz (SF, NY).Kolejny krok polega na połączeniu w pary wierzchołków połączonych drogami o długości do czterech krawędzi. W tym konkretnym przypadku nie wprowadza to już żadnych nowych elementów do relacji Dos- opnę. A więc relacja Dostępne dla danych opisanych grafem z rys. 4.19 zawiera dziesięć par (¹. y), takich że w grafie istnieje pomiędzy nimi jakaś droga. Są to przypadkowo dokładnie takie pary (x, y), że na ry s. 4.19 >• wy stępuje na prawo od x.

□

PRXYKt.AD4.38

Sytuacja ustalenia właściwej relacji łączenia dwóch lotów w jedną podróż komplikuje się, gdy zostanie dołączone ograniczenie, żc rejs może być łączony z innym rejsem, jeśli odlot drugiego z jakiegoś lotniska następuje nie wcześniej niż. godzinę po przylocie pierwszego na to lotnisko. lak określony predykat IDB nazwiemy Połączenia (x, y, d, r) i jest on spełniony, gdy podróż zaczyna się w miejscu .t w czasie ci, a przylot następuje do portu y w czasie r. Jeśli taka krotka istnieje, to na przesiadkę między jednym a drugim rejsem jest co najmniej godzina.

Następujące reguły definiują Połączenia¹:

1. Połączenie (x, y, d, r) «— Rejs (a, x, y, d, r)

2. Połączenie (x, y, d, r) <— Połączenie (x, z, d, tl)

AND Połączenie (z, y, t2, r) AND tl — t2 + 100

W pierwszym kroku iteracji otrzymuje się osiem Połączeń, które przedstawiono no rys. 4.21. Każde z nich jest powiązane z jednym rejsem z rys. 4.19; jest ich więcej niż krawędzi w grafie, ponieważ niektóre krawędzie oznaczają kilka rejsów w różnym czasie między tymi samymi portami.

Teraz tworzymy nowe krotki, korzystając z reguły (2). Na przy kład druga i piąta krotka tworzą nowe połączenie o parametrach (SF, CHI, 900, 1730). Natomiast nic można utworzyć nowego połączenia z krotek drugiej

1

Reguły le działają jedynie, gdy Żaden rejs nie odbywa się o północy.