Podstawowe algorytmy

Listy, stosy, kolejki i kopce - tego chyba nie trzeba tłumaczyć.

Lista: mamy strukturę zawierającą właściwy obiekt oraz wskaźnik na następny i/lub poprzedni element w liście.

Wektor: po prostu tablica, do której dodajemy bądź z której usuwamy.

Kolejka: Pierwsze wrzucamy, pierwsze usuwamy. Najłatwiej i najwygodniej byłoby zrobić na liście jednokierunkowej, mając wskaźnik na pierwszy element (aby wiedzieć, co zdejmować z kolejki) i na ostatni (aby wiedzieć, gdzie dodawać kolejny).

W naszym przypadku założymy, że w kopcu największy element znajduje się na górze.

Ładnie opisane na stronie Liceum z Tarnowa.

Bierzemy pierwszy element, i wrzucamy go do kopca jako korzeń. Bierzemy drugi, i dołączamy do korzenia. W razie potrzeby zamieniamy elementy miejscami. Potem dołączamy następny element, i razie potrzeby zamieniasz z rodzicem, tak, żeby największy element był zawsze na górze. No i w sumie tak można robić do oporu, w końcu skończą się elementy do dorzucenia na kopiec.

Usuwamy korzeń, a w jego miejsce wstawiamy ostatni element z kopca. Następnie przywracamy strukturę kopca, czyli zamieniamy rodzica z największym dzieckiem. Przykład:

        3 ← wstawiony nowy korzeń
      /   \
    8       10
   / \     /  \
  5   6   4    1

Zamieniamy go z największym dzieckiem, czyli z 10.

       10 ←----+
     /   \     | Zamieniamy
    8      3 ←-+
   / \    / \
  5   6  4   1

Teraz okazuje się, że trójka jest większa od czwórki, ale mniejsza od jedynki. Czyli zamieniamy trójkę z czwórką, i znów mamy piękny kopczyk.

       10
     /   \
    8      4 ←––-+
   / \    / \    |  Zamieniamy miejscami
  5   6  3   1   |  te dwa
         ↑      |   elementy kopca.
         +–––––––+

Dodajemy element na koniec kopca i dokonujemy kopcowania. To znaczy, zamieniamy z rodzicem tak długo, dopóki warunek na kopiec nie zostanie spełniony.

Najprostsze sortowanie. Mamy okienko, przez które widzimy dwa elementy ciągu, i jeśli nie pasują (np sortujemy malejąco, a te dwa są ułożone rosnąco), to zamieniamy je miejscami, a następnie przesuwamy się o jedno miejsce dalej (nawet, jeśli nie zamieniliśmy). Jeździmy w ten sposób dopóki nie ułożymy wszystkiego. Są dwie opcje, po zamianie można wrócić z okienkiem na początek ciągu i jechać od początku, albo po prostu przesuwać się dalej.

Opisane niżej, przy zrównoważonych drzewach binarnych. Bo to polega w sumie na tym samym, tzn budujemy kopiec a potem rozbieramy.

Ta metoda opiera się na tym, że wybieramy sobie element środkowy w liście, po czym przerzucamy elementy mniejsze na lewo, a większe na prawo. Potem, mając dwie takie części, każdą z nich rekurencyjnie sortujemy w ten sam sposób.

W jaki sposób to zrobić w praktyce?

Zamieniamy piwot z ostatnim elementem listy. Bierzemy dwa wskaźniki, i i j, oba ustawiamy na pierwszy element listy. Następnie jedziemy w prawo i dopóki nie natrafimy na element mniejszy od piwota. Jak znajdziemy - zamieniamy miejscami elementy wskazywane przez i i j. Przesuwamy j o jedno miejsce w prawo. Powtarzamy do momentu, aż i nie najedzie na piwota. Zamieniamy więc piwot z elementem na pozycji wskazywanej przez j, i po lewej stronie od piwota mamy elementy mniejsze, a po prawej większe.

Teraz, dla każdej z partycji (po lewej i po prawej) robimy to samo.

Jak zwykle, najlepiej wszystko jest wytłumaczone na stronie legendarnego liceum.

Sortowanie to jest dość proste do zrozumienia. Polega na tym, że mamy dwie posortowane listy i scalamy je w jedną posortowaną listę. Robi się to tak, że bierzemy po kolei najmniejsze elementy z pierwszej i drugiej części, i wrzucamy ten najmniejszy do listy wynikowej usuwając jednocześnie z miejsca, gdzie się pierwotnie znajdował. W sumie proste.

W ten sposób można rekurencyjnie wszystko ładnie posortować - dzielimy najpierw na jednoelementowe części, i po kolei budujemy coraz większe, aż dojdziemy do końca.

Jak zwykle, ładnie jest to opisane na stronie Tarnowskiego liceum.

Całkiem ładny opis jest na wikipedii. W takim drzewie chodzi o to, że po lewej stronie korzenia masz elementy mniejsze, a po prawej większe. I w sumie tyle. Poza tym, to to niewiele się różni od kopca, no ale algorytmy działania na tym są już inne.

Plus jest taki, że łatwo jest coś w takim drzewie znaleźć. No, i najmniejszy element zawsze będzie najdalej na lewo, a największy na prawo.

Mamy kilka liczb. Posortujmy je od najmniejszego do największego. Zyskamy coś takiego:

Wybieramy stąd środkowy element. Będzie on korzeniem kopca.

Teraz dodajmy elementy poniżej korzenia. Będą to środkowe liczby z pozostałych dwóch części.

Chodzi w sumie o to, aby po lewej stronie dowolnego elementu znajdowały się tylko mniejsze liczby, a po prawej tylko większe. W następnym kroku postępujemy w sumie podobnie, i otrzymujemy następujące drzewo:

      17           ← Pierwszy krok - zaznaczyliśmy 17
    /    \
  12      19       ← Drugi krok - środkowymi zaznaczonymi były 12 i 19
 /  \    /  \
6   15  18  22     ← W trzecim kroku zaznaczylibyśmy 6, 15, 18 i 22
 \          /
  7       20       ← No i na końcu zostałoby to

Pamiętaj, że jeśli drzewo utworzone w ten sposób wygląda trochę inaczej, to nie znaczy, że jest złe! Jeśli spełnia warunek podany zaraz przed tym rysuneczkiem, to jest to prawidłowe drzewo.

Zaczynamy od korzenia. Czy element, który chcemy wstawić jest większy, czy mniejszy od korzenia? W zależności od tego, jaka jest odpowiedź, idziemy w dół w odpowiednim kierunku.

Schodzimy w dół w ten sposób do momentu, aż natrafimy na puste miejsce - i tam wstawiamy nasz nowy element.

W projektach stosowaliśmy dwie metody zapisu grafów - Lista Sąsiedztwa i Macierz Incydencji.

Przykład:

 +-------+---------------+-----------------+
 |Wierz- | Waga,         | Waga,           |
 |chołek | Wierzchołek   | Wierzchołek     |
 |   1   | docelowy      | docelowy        |
 +-------+---------------+-----------------+
 |Wierz- | Waga,         | Waga,           |
 |chołek | Wierzchołek   | Wierzchołek     |
 |   2   | docelowy      | docelowy        |
 +-------+---------------+-----------------+

Czyli, mamy listę, gdzie każdy element listy to lista zawierająca krawędzie, czyli wagę krawędzi i wskaźnik na wierzchołek docelowy.

Ładnie jest to opisane na wikipedii. Chodzi o to, że każda kolumna symbolizuje jedną krawędź. W tej kolumnie znajduje się jedynka, jeśli dany wierzchołek jest podłączony do tej krawędzi, czyli w każdej kolumnie są tylko dwie jedynki.

W ten sposób można też zapisywać grafy skierowane, dając -1 tam, dokąd zmierza krawędź.

W przypadku macierzy ciężej jest znaleźć wszystkie krawędzie odchodzące od danego wierzchołka, gdyż w najgorszym wypadku trzeba przeszukać wszystkie kolumny. W przypadku listy wystarczy tylko przejść pod odpowiedni adres.

Mamy listę krawędzi z wagami. Wybieramy krawędź o najmniejszej wadze, po czym łączymy ją. Potem następną o najmniejszej wadze spośród tych, co zostały, i następną, i następną. Jeśli połączenie danej krawędzi stworzy cykl, to olewamy ją. Robimy to, dopóki zostaną nam krawędzie w kolejce.

Przykład kodu w C#:

public void kruskal(graf grafZrodlowy)
{
	KolejkaKopcowa krawedzie = grafZrodlowy.kolejkujKrawedzie();
	this.zmienRozmiar(grafZrodlowy.iloscWierzcholkow());
	coll.List<int> podlaczoneWierzcholki = new coll.List<int>();
	while (!krawedzie.isEmpty())
	{
		// dla każdej krawędzi w kolejce
		ElementKopca obecne = krawedzie.Dequeue();
		// czy drugi wierzchołek jest już podłączony do naszego grafu? Jak tak, to tworzymy cykl, a tak NIE MOŻE BYĆ!
		if (!podlaczoneWierzcholki.Contains(obecne.Wierzcholki.Drugi))
			this.laczWierzcholki(obecne.Wierzcholki.Pierwszy,obecne.Wierzcholki.Drugi,obecne.Waga);
	}
}

Wybieramy jeden wierzchołek jako punkt wyjścia. Łączymy krawędź o najmniejszej wadze, która wychodzi z wierzchołka. Teraz mamy już dwa punkty wyjścia ;) Powtarzamy to, dopóki nie połączymy wszystkich wierzchołków. Oczywiście nie może pojawić się cykl - jeśli połączenie jakiejś krawędzi powodowałoby cykl, to olewamy ową krawędź.

public void prim(graf grafZrodlowy)
{
	// zacznijmy zawsze od zerowego, w sumie to i tak nie ma wielkiej różnicy
	int wierzcholekPoczatkowy = 0;
	KolejkaKopcowa krawedzie = new KolejkaKopcowa();
	this.zmienRozmiar(grafZrodlowy.iloscWierzcholkow());
	coll.List<int> zbadaneWierzcholki = new coll.List<int>();
	// dodajemy do kolejki krawędzie z początkowego wierzchołka
	System.Collections.Generic.List<Krawedz> polaczoneZObecnym = grafZrodlowy.polaczoneWierzcholki(wierzcholekPoczatkowy);
	foreach (Krawedz obecna in polaczoneZObecnym)
		krawedzie.Queue(new ParaWierzcholkow(wierzcholekPoczatkowy,obecna.NrWierzcholka), obecna.WagaKrawedzi);
	zbadaneWierzcholki.Add(wierzcholekPoczatkowy);
	while (!krawedzie.isEmpty())
	{
		ElementKopca obecnyElement = krawedzie.Dequeue(); // no to mamy obecnie przetwarzany element kopca.
		if (!zbadaneWierzcholki.Contains(obecnyElement.Wierzcholki.Drugi))
		{ // jeśli się już nim zajmowaliśmy, to utworzyłoby nam to cykl! Uniknijmy tego!
			// ale skoro nie zajmowaliśmy się, to możemy wziąć i się zająć
			polaczoneZObecnym = grafZrodlowy.polaczoneWierzcholki(obecnyElement.Wierzcholki.Drugi);
			// zakolejkujmy wszystkie jego krawędzie
			foreach (Krawedz obecna in polaczoneZObecnym)
				krawedzie.Queue(new ParaWierzcholkow(obecnyElement.Wierzcholki.Drugi, obecna.NrWierzcholka), obecna.WagaKrawedzi);
			// dodajmy obecnie dołączany wierzchołek do listy wierzchołków obsłużonych
			zbadaneWierzcholki.Add(obecnyElement.Wierzcholki.Drugi);
			// i łączymy wierzchołki
			this.laczWierzcholki(obecnyElement.Wierzcholki.Pierwszy, obecnyElement.Wierzcholki.Drugi, obecnyElement.Waga);
		}
	}
}

Ten algorytm wymaga trochę dłuższego opisu, ale nie jest specjalnie trudny.

Mamy listę krawędzi, każda krawędź ma swoją wagę, i mamy listę wierzchołków. Wierzchołki też mają swoje wagi. Na początek ustawiamy wagę każdego wierzchołka na ∞. Wybieramy jeden wierzchołek, i jego wagę ustawiamy na 0.

Teraz patrzymy, jakie krawędzie odchodzą z tego wybranego wierzchołka. Sprawdzamy, które krawędzie będą miały największą wagę po podpięciu do tego zerowego. Skąd bierzemy wagę wierzchołka? Waga to suma wagi wierzchołka początkowego i wagi krawędzi, którą podpinamy wierzchołek końcowy. Czyli, w tym wypadku, waga to 0+7 lub 0+20, zależnie od wierzchołka.

Podpięcie daną krawędzią rozważamy tylko, jeśli waga po podpięciu byłaby mniejsza od wagi obecnej. Jako, że wierzchołków jeszcze nie podpinaliśmy, to waga to ∞, a więc zawsze waga po podpięciu będzie mniejsza. Podpinamy więc tylko ten wierzchołek, który po podpięciu będzie miał najmniejszą wagę - w tym wypadku będzie to górny wierzchołek.

Następnie robimy to samo, ale tym razem bierzemy nowy wierzchołek pod uwagę. I teraz też podpinamy ten wierzchołek, który dostałby najmniejszą wagę.

To powtarzamy w kółko - aż nie podłączymy wszystkich wierzchołków.

Kod jest trochę dłuższy, więc go pominę.

Na początku ustawiamy wagi wszystkich wierzchołków na ∞, oprócz pierwszego, którego wagę ustawiamy na 0.

Zaczynamy od wybranego wierzchołka, po czym łączymy wszystkie wychodzące od niego krawędzie. Zapisujemy wagi w świeżo podłączonych wierzchołkach. Potem idziemy po wszystkich innych wierzchołkach (pamiętajmy, że do zakończenia iteracji traktujemy wierzchołki podłączane w obecnej iteracji jako jeszcze niepodłączone) i robimy to samo - tzn. podłączamy wszystkie wychodzące od nich krawędzie - pod warunkiem, że można obliczyć wagę przyłączanych wierzchołków, a jeśli wierzchołek źródłowy ma wagę ∞, to nie możemy. Jeśli okaże się, że wyliczymy wagę dla wierzchołka mniejszą, niż wcześniej ustawiona, to odłączamy dotychczasowe połączenie i łączymy z nowym wierzchołkiem źródłowym, dla którego waga jest mniejsza.

Wykonujemy to albo n-1 razy, gdzie n to ilość wierzchołków, albo do momentu, gdy po przeleceniu wszystkich wierzchołków nie dokonamy żadnej zmiany.

Tak, wiem, że bez sensu to opisałem i nie da się tego zrozumieć. Polecam obejrzeć bardzo dobrą prezentację na ten temat, a wszystko stanie się jasne.

Mówiąc po ludzku, Programowanie Dynamiczna dla P2||C_max to rozdzielenie zadań na dwa procesory tak, aby łączny czas potrzebny na wykonanie wszystkich zadań był najkrótszy.

Jak to się robi? Tak samo, jak rozwiązuje się problem plecakowy (a nawet prościej), z tą różnicą, że zamiast wagi przedmiotu mamy czas wykonywania zadania. A nasz plecak ma pojemność równą ½ * Σ wag wszystkich elementów. Dzięki temu, jeśli uda nam się upakować tyle zadań, aby zajęły dokładnie połowę tego zsumowanego czasu, to druga część zadań też będzie się wykonywać połowę, a poniżej tego czasu już się nie da zejść. W sumie, to jest nawet prościej, niż w plecakowym, bo zadania nie mają swoich wartości. Zróbmy więc przykład.

p_j = 3,4,5,7,2 (to są zadania do wykonania, a te liczby to czas, w którym dane zadanie się wykona)
Σp_j/2 = 21/2 = 10,5 - widzimy, że nie da się podzielić doskonale na równo, więc przyjmijmy, że spróbujemy znaleźć podział najbliższy 10.

Tworzymy sobie tabelkę:

Oczywiście, jeśli przyjmiemy maksymalny czas za zero, to nie wykonamy żadnego zadania. Możemy wpisać tam od razu T.

Zajmijmy się teraz pierwszym zadaniem. Wykona się ono w czasie 3 jednostek, wpiszmy więc T w kolumnie zatytułowanej 3. Można od razu wypełnić T do samego dołu tabeli, powód jest dość intuicyjny i ciężko mi go opisać. Ale chodzi mniej więcej o to, że przy następnych zadaniach w razie olania ich zawsze można wykonać tylko zadanie 1.

Teraz zadanie 2. Tutaj podobnie, dajemy T w kolumnie 4. Ale przecież możemy wykonać teraz dwa zadania! 3+4=7, więc w kolumnie numer 7 też wstawiamy T.

Zadanie 3 - o czasie 5. Wstawiamy T do kolumny piątej. Zastanówmy się też nad poprzednimi zadaniami, tzn po prostu zobaczmy, gdzie w poprzednim wierszu znajdują się T.
3+5=8 ≤ 10 - ok, można zaznaczyć.
4+5=9 ≤ 10 - ok, można zaznaczyć.
7+5=12 ≤ 10 - nie, nie mieści się.

Zadanie czwarte i piąte wykonujemy w ten sam sposób co poprzednie, chyba nie ma potrzeby dalej tłumaczyć. W czwartym, które ma czas 7, stawiamy T w kolumnie 7 (tam już jest T, więc zostawiamy jak jest) i 10 (bo 7+3=10≤10), inne się nie mieszczą.

Piąte, ostatnie zadanie robimy tak samo, ale ono pasuje praktycznie wszędzie - w końcu ma wagę 2. Zapełniamy więc kolumnę 2, 3+2=5, 4+2=6, 5+2=7, 7+2=9, 8+2=10.

Teraz tylko backtracking. Czyli - patrzymy, kiedy w ostatniej kolumnie pojawiło się T (jeśli w ogóle się nie pojawiło, to patrzymy na przedostatnią kolumnę, przedprzedostatnią itd). U nas jest w czwartym wierszu.

Zadanie czwarte trwało 7 jednostek czasu. Cofamy się więc o 7 kolumn i trafiamy do kolumny 3. Tam też patrzymy, kiedy T pojawiło się po raz pierwszy.

Zadanie 1 trwało 3 jednostki czasu. Odejmujemy i widzimy, że żadne zadanie nie zostało przed nim wykonane. Tak więc na jednym procesorze wykonamy zadania 4 i 1, a na drugim resztę. Zadania zostają rozdzielone optymalnie, bo na jednym procku tracimy 10 jednostek czasu, a na drugim 4+5+2=11. Gołym okiem widać, że lepiej być nie może.