Dokumentacja, zap
[ Pobierz całość w formacie PDF ]
Warszawa, dn. 20 marca 2011
Zasady programowania strukturalnego - projekt
Temat:
The 2003 ACM Programming Contest World Finals sponsored by IBM
Problem J
Toll
Autor: Kamil Szeląg
1. TematSindbad Żeglarz sprzedał 66 srebrnych łyżek Sułtanowi Samarkandu. Sprzedawanie było całkiem proste, ale dostarczanie było już wyzwaniem. Przedmioty były transportowane lądem, co wymagało przejścia przez kilka miasto i wiosek. Każde miasto i wioska wymagało zapłacania cła przy wejściu. Za opuszczenie miasta Sindbad już płacić nie musiał. Cło w wioskach to po prostu jeden przedmiot. W mieście cło to jeden przedmiot za każde 20 przedmiotów które były w posiadaniu. Na przykład, żeby wejść do miasta mając 70 przedmiotów, trzeba było zapłacić cło w wysokości 4 przedmiotów. Miasta i wioski były usytuowane strategicznie, pomiędzy górami, bagnami i rzekami, tak że nie można było ich w jakikolwiek sposób ominąć
Przykład 1: Aby osiągnąć Samarkand z 66 łyżkami podróżując przed miasto po którym następują dwie wioski musisz zacząć z 76 łyżkami.
Przykład 2: Najlepsza droga aby osiągnąć X z 39 łyżkami, startując z A, to A→b→c→X, zaznaczona na rysunku po lewej za pomocą strzałek. Najlepsza droga by osiągnąć X z 10 łyżkami to A→D→X, zaznaczona na rysunku po prawej za pomocą strzałek. Rysunki pokazują miasta jako kwadraty a wioski jako okręgi. Przewidywanie wysokości cła w każdej wiosce albo mieści jest bardzo proste, ale znajdowani najlepszej trasy (najtańszej trasy jest prawdziwym wyzwaniem. Najlepsza trasa zależy od ilości posiadanych przedmiotów. Dla numerów do 20, wioski i miasta pobierają takie same cła. Dla większych ilości przedmiotów, staje się senso
Musisz napisać program który rozwiąże problem Sindbada. Mając daną ilość przedmiotów, które mają być dostarczone do określonego miasta lub wioski oraz „mapę świata”, twój program musi zdeterminować ilość przedmiotów potrzebnych na początku najtańszej trasy.
wnym omijanie miast i podróżowanie przez wioski jak w przykładzie 2
Wejście
Wejście zawiera kilka testowych przypadków, Każdy przypadek składa się z dwóch części : “mapy świata” i szczegółów przesyłki.
Pierwsza linia „mapy świata” zawiera integera n, który jest ilością ścieżek na mapie (0<=n). Każda następna z n linii zawiera dokładnie dwie litery reprezentujące dwa krańce każdej ścieżki. Duża litera reprezentuje miasto a mała litera reprezentuje wioskę. Ścieżki mogą być pokonywane w obydwu kierunkach
The input consists of several test cases. Each test case consists of two parts: the roadmap followed by the delivery details.
Po ”mapie świata” w wejściu znajduje się pojedyncza linia dla szczegółow przesyłki. Linia składa się z trzech elementów : integer p (0<p<=1000) który jest ilością przedmiotów które mają być dostarczone, litera dla miejsca startu, i litera miejsca docelowego. Mapa świata jest tak dopasowana aby łyżki zawsze mogły być dostarczone. Ostatni przypadek zakończony jest linią która zawiera liczbę -1
Wyjście
Wyjście składa się z pojedynczych linijek dla każdego przypadku. Każda linia pokazuje numer przypadku i ilość przedmiotów potrzebną na początku podróży. Przykładowe wejście i wyjście poniżej.
Przykładowe wejście
Wyjście dla przykładowego wejścia
1
a Z
19 a Z
5
A D
D X
A b
b c
c X
39 A X
-1
Case 1: 20
Case 2: 44
2. Analiza, projektowanie
Problem postawiony w zadaniu sprowadza się do wyznaczania najkrótszych ścieżek w grafie o zmiennych wagach krawędzi. Przy tak zadanym wejściu rozwiązanie problemu sprowadza się do kilku podstawowych zadań:
a. Optymalnego przechowywania informacji o „mapie świata” tak by zawierała ona niezbędne informacje o trasie i pozwalała na łatwe obliczenia wielkości potrzebnych do rozwiązania problemu.
b. Obliczenia wag krawędzi grafu dla różnych tras przy jak najmniejszej ilości operacji.
c. Wyznaczenia najkrótszej trasy dla obliczonych wag krawędzi
d. Uwzględnienie dwóch przypadków gdy mamy dany koniec i gdy mamy dany początek, napisania programu by mógł liczyć kilka różnych przypadków na raz
Okazuje się, że problem wielości operacji wymaganych do obliczania wag krawędzi dla poszczególnych tras można rozwiązać w łatwy sposób. Rezygnujemy z pełnej informacji o wagach krawędzi dokonując redukcji na każdym etapie obliczania wag (sam mechanizm redukcji zostanie omówiony przy okazji omawiania algorytmu obliczania wag).
Decydując się na „szczątkową” analizę grafu należy dostosować w odpowiedni sposób rozwiązania poszczególnych podzadań.
2.1. „Mapa świata”W wejściu podawane są informacje o ilości ścieżek, by potem opisać każdą z nich. Pierwszą myślą jest pomysł utworzenia struktury, która da pełną informację o pojedynczej ścieżce. Po dalszej analizie okazuje się że ten pomysł jest wystarczający i w zupełności nadaje się do wykorzystania. Struktura ta musi zawierać kilka kluczowych elementów:
struct Path
{
char start;
int initial_state;
bool use;
char end;
int finish_state;
};
Elementy start i end są to chary określające początek i koniec trasy. Zgodnie z treścią zadani duża litera to miasto a mała to wioska. W tym miejscu nasuwa się myśl by kolejnym elementem była waga krawędzi. Takie rozwiązanie byłoby jednak niewłaściwe. Po pierwsze dlatego, że waga krawędzi byłaby rożna w zależności od tego w którą stronę ścieżka byłaby pokonywana, a po drugie dlatego że przy obliczaniu najkrótszej trasy dodaje to jedną operację dla każdej scieżki co jest nieoptymalne. Dlatego też w strukturze pojawiają się dwa elementy initial_stare oraz finish_state – są to ilości przedmiotów, które są w posiadaniu Sindbada po wejściu do danego miasta. Ostatni element, którym jest bool use, pozwala na zaznaczenie dla których ścieżek wykonywane były niezbędne obliczenia. Wiadomo że poruszanie się dwa razy po tej samej ścieżce jest niekorzystne bo dwa razy płacimy to samo cło. Takie przypadki można więc w „szczątkowym” rozwiązaniu pominąć. Zmniejsza to drastycznie ilość wykonywanych obliczeń.
Struktura pojedynczej ścieżki nie wystarcza do opisania „mapy świata”. Potrzebna jest jakaś struktura w której będziemy te struktury przechowywać. Okazuje się że najłatwiejsze w przeszukiwaniu i porównywaniu dla danych warunków są tablice jednowymiarowe. Dlatego też informacja o „mapie świata” jest przechowywana w jednowymiarowej tablicy struktur Path.
Aby zmniejszyć ilość obliczeń opłaca się wprowadzić jeszcze jedną strukturę, która informować będzie o ilości ścieżek ilości przedmiotów na początku trasy oraz o jej początku i końcu:
struct Data
{
int path_count;
int spoon_count;
char start;
char end;
};
Te dwie struktury w zupełności wystarczają do pełnego opisania „mapy świata”.
2.1. Obliczanie wag krawędziJest to najbardziej wymagająca część problemu. To w tej części wykonywana jest największa ilośc operacji i to tutaj dobry algorytm może najlepiej przyspieszyć działanie programu.
Sposób obliczania wag krawędzi musi być dostosowany do tego, jakie wielkości są w zadaniu istotne. Jak wynika z jego treści potrzebne są nam jedynie ilości łyżek na początku i końcu trasy. Nie musimy zapamiętywać którędy trasa przebiega. To pozwala na uproszczenie obliczeń. Tak więc, po kilku operacjach nie dostaniemy poprawnych wag poszczególnych krawędzi dla wszystkich możliwych przypadków, dostaniemy jedynie poprawne wagi dla jednej, najkrótszej trasy. Podstawowym narzędziem optymalizacji jest struktura Info, która zawiera dane o maksimach lub minimach posiadanych łyżek w poszczególnych miastach:
struct Info
{
char place;
int state;
};
Tak jak w przypadku ścieżek i tutaj tworzymy jednowymiarową tablicę tych struktur zawierająca wszystkie miasta.
Problem obliczania wag zostaje rozwiązany rekurencyjnie. Tworzy się funkcję, która dla zadanego początku ścieżki wyszukuje w strukturze Info ilość łyżek w tym punkcie i oblicza ilość łyżek na końcach ścieżek zaczynających się w tym punkcie. Następnie końce trasy stają się zadanymi początkami. Proces kończy się gdy żaden z zadanych początków nie jest początkiem żadnej ze ścieżek.
W tym procesie ważne jest to, że po każdym obliczeniu ilości łyżek na końcu trasy porównuje się ją z ilością łyżek przechowywaną w strukturze Info dla danego miasta/wioski, a przy kolejnych obliczeniach za ilość początkową przyjmuje się tą ze struktury Info. To pozwala na równoczesne obliczanie ilości dla najkrótszej ścieżki gdy jedna miejscowość jest końcem kilku ścieżek.
Po każdym obliczeniu ilości na końcu danej ścieżki i porównaniu z ilością zapamiętaną w strukturze Info parametr „use” dla tej ścieżki zostaje zmieniony, tak by obliczenia nie były już dla niej więcej wykonywane.
Taka procedura pozwala na przeliczenie wag tylko „na prawo” od miejsca uznanego za początek. Należy jeszcze uwzględnić obliczenia „na lewo” oraz te mieszane.
Aby uwzględnić te przpadki tworzymy funkcję analogiczną do tej liczącej dla zadanego początku z tym, że licżacą dla zadanego końca. Pozostałe czynności są te same.
Aby ostatecznie obliczyć wszystkie wagi musimy połączyć działanie obu funkcji.
Musi zostać utworzona funkcja, w której można wyróżnić następujące elementy:
· Funkcja licząca dla zadanego końca
· Funkcja licząca dla zadanego początku
· Funkcja zerująca parametr use w każdej ze ścieżek
Działanie tej funkcji jest bardzo podobne do działania funkcji działającej dla zadanego końca. Różnica po pierwsze polega na tym, że dla każdego elementu oprócz obliczania ilości łyżek na początku ścieżki zostaje wykonywana funkcja licząca wagi dla zadanego początku, dla której zadanym początkiem jest obliczony początek trasy.
Poszczególne kolory strzałek oznaczają kolejne etapy wykonywania obliczeń. Czerwone koło jest startem a niebieskie końcem trasy. Pierwszym etapem jest strzałka czerwona, drugim są strzałki niebieskie, trzecim zielone a czwartym pomarańczowe
Jak widać na rysunku potrzebne jest resetowanie wartości „use” dla poszczególnych grup ścieżek by optymalizacja była pełna. Reset tej wartości będzie odbywał się dla ścieżek, dla których wykonywana była funkcja obliczania wag dla zadanego startu.
Gdyby wartość use nie była resetowana optymalizacja byłaby niepełna, a gdyby jej w ogóle nie było to złożoność obliczeniowa algorytmu wynosiłaby n^n, co nie byłoby dobrym rozwiązaniem.
W ten sposób brane są pod uwagę wszystkie „logicznie sensowne” trasy jakimi mógłby się poruszać Sindbad przy stosunkowo małej ilości obliczeń.
2.1. Wyznaczanie najkrótszej trasy
Jeśli obliczanie wag krawędzi przebiegałoby zgodnie z podanym powyżej algorytmem to otrzymanie wartości na krańcach ścieżek sprowadza się do jej odczytu ze struktury Info.
2.1. Dwa przypadki, obliczanie wielu różnych przypadków.
Aby uwzględnić dwa przypadki tworzymy analogiczne funkcje dla przypadku odwrotnego zastępując koniec trasy jej początkiem a początek końcem, zmieniając sposób obliczania cła oraz tworząc funkcję, która zależnie od danego przypadku uruchomi pierwszą lub drugą procedurę.
[ Pobierz całość w formacie PDF ]