1. Wprowadzenie teoretyczne
1.1 Ogólny opis zagadnienia
1.2 Opis metod ścisłych optymalizacji
1.3 Opis metod przybliżonych optymalizacji QAP
1.3.1 Metody konstrukcyjne
1.3.2 Metody interacyjne
1.4 Opis algorytmu Tabu Search
1.5 Dziedziny zastosowania QAP
2. Budowa narzędzia badawczego
2.1 Wstęp
2.2 Obsługa aplikacji
2.3 Budowa interfejsu graficznego
2.4 Opis funkcji obsługi zdarzeń
2.5 Opis struktury klas obiektów
3. Badanie problemów QAP
4. Wnioski
5. Bibliografia
1.1. Ogólny opis zagadnienia
Problem przydziału zadań do zasobów przy kwadratowym wskaźniku jakości QAP (ang. Qadratic Assignment Problem) należy do klasy NP-trudnych problemów optymalizacji kombinatorycznej.
Problem ten występuje w licznych zagadnieniach praktycznych w takich dziedzinach jak: ekonomia, ergonomia, elektronika, architektura, informatyka.
Po raz pierwszy problem QAP został sformułowany przez Koopmansa i Beckmana [5] do zastosowań ekonomicznych.
Problem QAP jest uogólnieniem liniowego problemu przydziału AP (ang. Assignment Problem), który należy do klasy P-problemów wielomianowych.
Definiuje się go w następujący sposób. Dane są n2 współczynników kosztów przydziału zadań do zasobów Cij oraz n4 współczynników kosztów powiązań Dijkl, takich że:
Należy znaleźc rozwiązanie 
takie, że:
1.2. Opis metod ścisłych optymalizacji QAP
Istnieje duża ilość metod ścisłych. Można je podzielić na dwie grupy. Pierwsza z nich bazuje na metodzie podziału i ograniczeń (ang. Branch and Bound Method), zaś druga wykorzystuje różnego rodzaju linearyzację funkcji celu.
W pierwszej podgrupie można wydzielić metody przyporządkowania prostego oraz metody podwójnego przyporządkowania. Metody prostego przyporządkowania sprowadzają się do przydziału jednego elementu (nie przydzielonego) zbioru zadań, do jednego elementu zbioru zasobów, na każdym etapie obliczeń, do chwili wyczerpania wszystkich przyporządkowań.
W grupie tych metod można wyróżnić metody wykorzystujące dekompozycję QAP. W tym przypadku dokonuje się redukcji macierzy A i B i przeprowadza się dekompozycję funkcji celu na funkcję liniową oraz zredukowaną funkcję kwadratową. Typowymi reprezentantami takiego podejścia są algorytmy Roucairola [9] oraz Christofidesa-Mingozziego i Totha [2].
Ponieważ algorytm Roucairola rozwiązuje w akceptowalnym przez użytkownika czasie zagadnienia o stosunkowo dużych rozmiarach, może być stosowany do testowania algorytmów aproksymacyjnych. Poniżej znajduje się opis algorytmu.
C. Roucairol przedstawia funkcję celu w postaci sumy funkcji liniowej oraz zredukowanej funkcji kwadratowej. Dekompozycja ta pozwala znaleźć w prosty sposób jednocześnie dolne i górne ograniczenie rozwiązania optymalnego. Następnie stosując standardowe podejście metody podziału i ograniczeń konstruuje się drzewo rozwiązań i przeprowadza pośredni przegląd rozwiązań. Poniżej przedstawiono podstawowe etapy tej metody dla następującej postaci funkcji celu:
Faza 1 algorytmu: redukcja macierzy A i B.
Definicja. Zredukować macierz kwadratową M = [mij] o elementach nieujemnych rzędu n oznacza znalezienie 2n liczb nieujemnych ai, bj (i,j = 1, ........, n) takich, że macierz M' = [m'ij] = [mij - ai - bj] jest macierzą o elementach nieujemnych i zawiera co najmniej jedno zero w każdym wierszu i każdej kolumnie.
Znane są dwa sposoby redukcji macierzy:
1) Sposób standardowy "wiersz-kolumna", znany z zastosowań w algorytmie węgierskim dla zagadnienia AP oraz w algorytmie Littla (i inni) dla zagadnienia TSP(ang. Travelling Salesman Problem).
2) Sposób zwany "element maksymalny w pierwszej kolejności" polega na znalezieniu maksymalnego elementu macierzy M:
Element maksymalny jest redukowany w pierwszej kolejności. W tym celu szukamy elementu minimalnego w wierszu i* :
elementu minimalnego w kolumnie j* :
jeżeli teraz
to redukujemy elementy wiersza i* o wartość mi*l i podstawiamy
1.3. Opis metod przybliżonych optymalizacji QAP
W zagadnieniach praktycznych wymiar n problemu spełnia na ogół warunek n > 20. Stąd wysiłek badaczy został skoncentrowany na rozwijaniu metod przybliżonych, które, w ogólnym przypadku, można podzielić na:
1) metody konstrukcyjne,
2) iteracyjne metody poprawiania rozwiązania.
1.3.1. Metody konstrukcyjne.
W pierwszym przypadku rozwiązanie jest konstruowane w ten sposób, że wykonanie jednej iteracji procedury polega na ustaleniu wartości jednej składowej rozwiązania. Najczęściej dopuszczalne rozwiązanie wyznaczane jest za pomocą reguły zachłannej, szeregowania listowego, a także przez losowanie. W ostatnim przypadku kolejność elementów ze zbioru N w permutacji p jest określona za pomocą generatora liczb losowych. Najpopularniejszą z metod inauguracyjnych jest procedura BEST_MATCH, która była wykorzystywana przez wielu badaczy zagadnienia QAP do generowania rozwiązania początkowego. Podstawą tej procedury jest proces przyporządkowania najbardziej powiązanych (duży przepływ materiałów, części, pacjentów, duża liczba połączeń, itp.) obiektów (zakładów przemysłowych, maszyn, klinik, modułów, itp.) do pozycji kluczowych (na przykład pozycji centralnych).
1.3.1.1. Procedura BEST MATCH
Krok 1. Dla j = 1, 2, ............., n oblicz wartości
Szeregując indeksy j w porządku nie rosnących wartości BBj utwórz wektor BB.
Krok 2. Dla i = 1, 2, ............., n oblicz wartości
Szeregując indeksy i w porządku nie malejących wartości AAi utwórz wektor AA.
Krok 3. Utwórz rozwiązanie zagadnienia przyporządkowując kolejno elementy wektora BB do elementów wektora AA.
1.3.2. Metody interacyjne.
Iteracyjne metody poprawiania polegają na poszukiwaniu, w każdej iteracji, rozwiązania lepszego od sukcesora, gdzie sukcesorem jest najlepsze znane rozwiązanie. Najbardziej popularne i efektywne są metody optymalizacji lokalnej, w zakresie których najczęściej poszukuje się rozwiązania lepszego w otoczeniu sukcesora otrzymanego przez zmianę położenia dwóch lub trzech elementów sukcesora, przy czym poszczególni autorzy proponują tu różne zasady zmiany położenia elementów w permutacji oraz różne reguły określające kolejność sprawdzania jakości rozwiązań z otoczenia. Reprezentatywnym przykładem generowania rozwiązań z otoczenia sukcesora poprzez zmiany położenia dwóch elementów permutacji jest algorytm Heidera.
Jeżeli sukcesorem jest permutacja p, to permutacje p' należące do otoczenia sukcesora N(p), definiuje się w następujący sposób:
Algorytm w sposób systematyczny sprawdza do n(n-1)/2 (ponieważ |N2(p)| = n(n-1)/2 ) rozwiązań z otoczenia sukcesora w kolejności ustalonej arbitralnie lub określonej za pomocą wybranej reguły. Sprawdzanie rozwiązań z otoczenia sukcesora jest realizowane do chwili otrzymania pierwszego rozwiązania lepszego od sukcesora, które zostaje nowym sukcesorem i proces szukania jest kontynuowany w otoczeniu nowego sukcesora. Jeśli w całym otoczeniu sukcesora algorytm nie znajdzie rozwiązania lepszego, to sukcesor jest rozwiązaniem lokalnie optymalnym i proces szukania kończy się. Koszt obliczeń wartości funkcji celu rozwiązań p' należących do otoczenia N2(p) redukuje się, jeżeli oblicza się tylko różnicę wartości funkcji celu sukcesora p i p':
Jeżeli df > 0, to permutacja p' jest rozwiązaniem lepszym od sukcesora p. Wyliczenie przyrostu df wymaga wykonania (2n-2) operacji mnożenia oraz (5n-4) operacji dodawania. Stąd algorytm Heidera jest zaliczany przez wielu autorów do najbardziej efektywnych algorytmów podwójnej zmiany.
W pracy tej skoncentrowano się na procedurze Tabu Search, która również bazuje na metodzie podwójnej zmiany i została opisana dokładnie w punkcie 1.3.
1.4. Opis algorytmu Tabu Search
Procedura Tabu opiera się na zasadzie działania algorytmu podwójnej zmiany, który został opisany w punkcie 1.3. Zawiera dodatkowo pamięć krótkoterminową nazwaną Listą Tabu (skr. LT), pamiętającą ostatnie przestawienia par elementów sukcesora,
w celu zabronienia przestawiania tych elementów sukcesora przez dany okres T zwany okresem karencji dla danej (przestawionej) pary. To oznacza, że Lista Tabu zawiera aktualne rozwiązanie i zabronione rozwiązania, które wystąpiły w przeszłości.
Wszystko po to, aby uniknąć cykli i przyspieszyć proces poszukiwania najlepszego rozwiązania. Lista Tabu zawiera również pamięć długoterminową, która pamięta wszystkie przestawienia danej pary, w celu zróżnicowania procesu poszukiwania rozwiązania.
Obie pamięci służą ku temu aby faworyzować przestawienia niewykonywane, a karać takie które były często dokonywane. Poniżej przedstawiono algorytm Tabu Search.
Krok 1.
Utwórz rozwiązanie startowe za pomocą procedury konstrukcyjnej. Podstaw:
Ustal dodatnie parametry algorytmu:
K - ilość iteracji,
T - okres karencji,
Alfa - kara za częste przestawienia pary elemntów.
Krok 2.
Dla k=1 do K wykonaj:
a) wyznacz najlepsze rozwiązanie w otoczeniu:
b) popraw rozwiązanie:
c) dokonaj korekty stanu pamięci:
gdzie:
DLT(i,j) - Dolna Lista Tabu (pamięć długoterminowa)
GLT(i,j) - Górna Lista Tabu (pamięć krótkoterminowa), zawiera pozostały "czas tabu" pary elementów (i,j). Jeżeli GLT(i,j) = 0 to para może być przestawiana w procesie poszukiwania lepszego rozwiązania, para nie ma warunku "tabu".
Jeżeli zaś np. GLT(i,j) = 2, to para elemantów (i,j) ma warunek "tabu" jeszcze przez dwie iteracje.
Opis kroku 1.
Na początku wybierany jest wektor rozwiązania startowego za pomocą procedury konstrukcyjnej.
Napisany program zawiera 3 algorytmy konstrukcyjne:
a) algorytm losowy - wyznacza rozwiązanie poprzez losowanie kolejnych elementów wektora rozwiązania startowego,
b) algorytm uśredniający nr 1 - sumuje elementy w poszczególnych wierszach macierzy A i B,
c) algorytm uśredniający nr 2 - sumuje elementy w poszczególnych kolumnach macierzy A i B,
Oba algorytmy uśredniające bazują na procedurze BEST-MATCH.
Utworzony wektor startowy podstawiany jest pod zmienne, obliczona zostaje wartość funkcji celu i również podstawiona pod odpowiednie zmienne.
Ustalane są parametry algorytmu.
Opis kroku 2.
Krok ten składa się z 3 części, wykonywanych kolejno po sobie:
a) wyznaczenie najlepszego rozwiązania w otoczeniu ,
b) poprawa rozwiązań,
c) korekta stanu pamięci.
Każda z powyższych części kroku 2 wykonywana jest K razy, gdzie K oznacza ilość iteracji.
Pierwsza część to wyznaczenie najlepszego rozwiązania w otoczeniu N.
Najpierw poszukiwane jest rozwiązanie według wzoru (*) w taki sposób, że przestawiana jest para elementów (i,j) w wektorze rozwiązań. Obliczone zostaje wyrażenie w klamrach, obliczana jest funkcja celu dla aktualnego wektora rozwiązania, do tej wartości
doliczana jest wartość równa iloczynowi kary za częste dokonywanie przestawienia pary (i,j) i częstotliwości przestawiania pary (i,j). Operacje te wykonywane są dla przestawienia pary (i,j) z całego otoczenia.
Otoczeniem są wszystkie możliwe przestawienia, tzn. takie dla których okres karencji T = 0. Zapamiętana zostaje ta para, której przestawienie dało najmniejszą wartość wyrażenia w klamrach (*). Następnie poszukiwane jest rozwiązanie według wyrażenia (**).
Tym razem otoczeniem są wszystkie przestawienia, dla których okres karencji jest większy od zera. Obliczana jest wartość funkcji celu dla każdej realizacji przestawienia (i,j) z otoczenia N. Jeśli rozwiązanie znalezione przy pomocy wyrażenia jest lepsze,
jest ono przyjmowane jako najlepsze znalezione rozwiązanie w kroku k. Następnie dokonywana jest korekta stanu pamięci. Okres karencji dla par, dla których przestawianie jest zabronione, jest zmniejszany o 1. Dla pary, której przestawienie dało najlepsze rozwiązanie
w kroku k, podstawiany jest okres karencji T na Górnej Liście Tabu oraz zwiększany jest o 1 licznik wystąpienia przestawienia tej pary na Dolnej Liście Tabu w procesie poszukiwania najlepszego rozwiązania.
Lista Tabu.
Lista Tabu może być zrealizowana za pomocą macierzy kwadratowej o wymiarze równym rozmiarowi badanego problemu, z tym że niedozwolone są odwołania do elementów na głównej przekątnej macierzy z prostego powodu - macierz pamięta permutację (przestawienie) dwóch różnych elementów.
Trudno jest mówić o permutacji tego samego elementu. Poniższy rysunek przedstawia realizację pamięci krótkoterminowej (GLT) i długoterminowej (DLT) za pomocą macierzy. Jest to przykład problemu o wymiarze n = 9, okresie karencji T = 5, a sytuacja na Liście Tabu przedstawiona jest po iteracji,
w której przestawiono elementy (5,8).
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| 1 | x | 2 | 3 | ||||||
| 2 | x | 4 | |||||||
| 3 | 5 | x | 1 | ||||||
| 4 | 1 | x | |||||||
| 5 | 3 | 2 | x | 5 | |||||
| 6 | 2 | x | |||||||
| 7 | 1 | 3 | x | ||||||
| 8 | 1 | 6 | x | 0 | |||||
| 9 | 1 | 2 | 1 | x |
Górna część macierzy GLT zawiera pamięć krótkoterminową. Pamięta, że elementy (5,8) nie mogą być przestawiane w procesie poszukiwania lepszego rozwiązania przez okres 5 iteracji. Podobnie elementy (1,4) przez 2 iteracje, elementy (1,7) przez 3, elementy (2,8) przez 4, a elementy (3,6) przez 1 iterację. Po każdej kolejnej iteracji czas zabronienia przestawienia danej pary jest zmniejszany o 1.
Dolna część macierzy DLT zawiera pamięć długoterminową. Pamięta wszystkie przestawienia par elementów, po każdym przestawieniu pary elementów zwiększa komórkę pamięci dla tej pary o 1. Para (3,2) przestawiana była już 3-krotnie, pary (4,1), (7,1), (9,1), (8,2), (9,7) tylko raz, itd.
Główna przekątna macierzy nie jest dostępna.
1.5. Dziedziny zastosowania QAP
Często rozważanym przykładem zastosowania modelu QAP jest lokalizacja zakładów produkcyjnych (maszyn w hali zakładu), gdzie zbiór N określa zbiór miejscowości (zbiór pozycji na hali), w których należy zbudować (ustawić) zakłady (maszyny).
W tym przypadku macierz A jest macierzą odległości pomiędzy miejscowościami (pozycjami), podczas gdy macierz powiązań B=[bij] opisuje wzajemną od siebie zależność zakładów lub przepływ materiałów (części) między zakładem (maszyną) j oraz l.
Składnik liniowy, opisany macierzą C=[cij] może być interpretowany jako koszt budowy zakładu j w miejscowości i.
W elektronice rozważane jest zagadnienie optymalnego rozmieszczenia obiektów elektronicznych (modułów, zintegrowanych układów) na płaszczyźnie w określony schemat połączeń. Przykładem może być problem rozważany w roku 1961 przez Steinberga [10],
optymalnego rozmieszczenia modułów sekcji maszyny cyfrowej UNIVAC-1. Pozycje na których mogą być rozmieszczone moduły są traktowane jako punkty w przestrzeni 2-wymiarowej 9*4, gdzie dwie pozycje są rezerwowe. Macierz A określa odległości między poszczególnymi pozycjami,
przy czym można wprowadzić różne metryki, np. Euklidesową, Kwadrat odległości euklidesowej, Łobaczewskiego. Macierz B=[bjl] określa liczbę połączeń między modułem j oraz l. Celem optymalizacji rozmieszczenia modułów jest minimalizacja całkowitej długości połączeń między modułami.
Dla potrzeb architektury rozważane są zagadnienia rozmieszczenia biur w zakładzie produkcyjnym, rozmieszczenie centrów handlowych, edukacyjnych i kulturalnych w nowo budowanej dzielnicy miasta oraz rozmieszczenie klinik w szpitalu. Reprezentatywnym przykładem w/g Elshafeia [3] jest zagadnienie
rozmieszczenia 19 klinik w szpitalu Ahmed Maher w Kairze. Element aik macierzy A określa odległość pomiędzy miejscami rozmieszczenia (i,k), zaś element bjl macierzy B określa średnią liczbę pacjentów przemieszczających się między klinikami (j,l) w czasie wykonywania badań i zabiegów.
Celem praktycznym optymalizacji jest minimalizacja odległości (pacjent/metr) przebytych przez pacjentów w ciągu roku.
Burkard i Offerman [1] zastosowali model zagadnienia QAP podczas projektowania nowej klawiatury maszyny do pisania tekstów w języku francuskim, angielskim i niemieckim.
Problem polegał na rozmieszczeniu 26 symboli liter na klawiszach w celu minimalizacji średniego czasu koniecznego do napisania tekstu. W tym przypadku element aik określa średnią częstotliwość występowania pary liter (i,k) oraz element bjl jest czasem potrzebnym do naciśnięcia klawisza j po uprzednim naciśnięciu klawisza l.
Model kwadratowego zagadnienia przydziału wykorzystywany jest również w informatyce. W tym przypadku poszukuje się optymalnego przydziału zadań obliczeniowych do takich podstawowych zasobów wieloprocesorowych systemów komputerowych jakimi są procesory obliczeniowe lub komunikacyjne.
Element aik macierzy odległości A określa odległość procesora i od procesora k (mierzoną na przykład w rozproszonym systemie komputerowym, liczbą procesorów pośredniczących w przekazywaniu wiadomości pomiędzy procesorem i oraz k), natomiast element bjl określa jednostkowy (na jednostkę odległości) koszt przesłania
wiadomości od zadania j do zadania l lub też koszt jednostkowy pomnożony przez prawdopodobieństwo przesłania wiadomości. Przy takiej definicji współczynników kosztów, funkcja celu określa całkowite koszty przesyłania wiadomości pomiędzy zadaniami realizowanymi na różnych procesorach.
Należy podkreślić, iż w cytowanych
tutaj pracach mamy do czynienia z pewnymi uogólnieniami standardowego zagadnienia QAP.
2.1. Wstęp
Program do badania problemów QAP bazujący na algorytmie Tabu Search został napisany w środowisku systemu Windows przy pomocy programu narzędziowego Bilder C++ wersja 4.0 firmy Borland International, jak sama nazwa wskazuje w języku programowania obiektowego C++. Projekt nazywa się Krzyś i składa się z 7 plików:
plik wykonywalny krzys.exe, plik źródłowy projektu krzys.cpp, pliki zawierające poszczególne klasy wektor.h, tablica.h, TS.h, QAP.h, pliki z formularzami okien Mform.h, Aform.h oraz odpowiadające im pliki o tej samej nazwie z rozszerzeniem .cpp, zawierające implementacje funkcji składowych klas.
Szczegółowy opis klas przedstawiono w dalszej części.
2.2. Obsługa aplikacji
Po uruchomieniu programu na ekranie pojawia się okienko w kształcie prostokąta zawierające tylko pasek narzędziowy. Znajdują się na nim przyciski umożliwiające sprawną obsługę programu.
Pierwszy przycisk od lewej Otwórz umożliwia wczytanie problemu z pliku. Naciśnięcie przycisku powoduje otwarcie okienka dialogowego, które umożliwia przeglądanie katalogów i plików na dyskach i wybór pliku z danymi do otwarcia.
Pliki z danymi powinny mieć następującą strukturę:
Pierwszą liczbą do odczytania z pliku powinien być rozmiar problemu, następnie kolejne liczby to elementy macierzy A, następnie elementy macierzy B, i ewentualnie elementy macierzy C. Naciśnięcie przycisku OK zamyka okienko dialogowe otwarcia pliku i jeśli format pliku będzie niezgodny z przedstawionym powyżej, program zgłosi błąd: Niepoprawny format pliku. Jeśli natomiast struktura pliku będzie poprawna dane zostaną wczytane pod odpowiednie zmienne tablicowe, główne okno programu powiększy się i będzie wyglądać jak na rysunku poniżej.
U góry znajduje się pole opisu, które zawiera informację o tym z jakiego pliku został wczytany problem i jaki jest jego rozmiar.
Algorytm Tabu Search (TS) w problemie Kwadratowego Zagadnienia Przydziału (ang. QAP). Problem wczytany z pliku ............dat. Rozmiar problemu ....
Poniżej znajduje się graf, w którym program kreśli przebieg funkcji celu podczas wykonywania obliczeń.
Po lewej u góry znajduje się pole do zadawania parametrów algorytmu. Znajdują się tutaj trzy pola edycyjne umożliwiające wpisanie nowych wartości. Pierwsze pole umożliwia zmianę ilości iteracji K, po których algorytm się zatrzymuje. Za pomocą drugiego pola można zmienić wartość okresu karencji dla danej pary T, tzn. wpisana liczba określa ilość iteracji przez które zamieniona para nie może być przestawiana w poszukiwaniu lepszego rozwiązania. Trzecie pole edycyjne daje możliwość zmiany parametru a, który jest karą jaką ponosi para, za to że była już przestawiana w procesie poszukiwania lepszego rozwiązania.
Poniżej znajduje się lista rozwijana, która umożliwia wybór algorytmu konstrukcyjnego do wyznaczenia rozwiązania startowego Pst.
Na liście dostępne są trzy algorytmy: losowy, algorytm 1, algorytm 2. Pierwszy wyznacza wektor rozwiązania startowego za pomocą generatora liczb losowych. Drugi i trzeci działa na zasadzie opisanej w punkcie 1.2.2 procedury Best_Match. Algorytm 1 sumuje kolejne elementy w poszczególnych wierszach macierzy B, sumy szereguje nie rosnąco i tworzy z nich wektor BB, następnie sumuje kolejne elementy kolumn macierzy A, sumy szereguje nie malejąco i tworzy z nich wektor AA, a następnie konstruuje wektor rozwiązania startowego przyporządkowujšc kolejne elementy wektora BB do elementów wektora AA. Algorytm 2 działa na tej samej zasadzie, lecz różni się tym, że sumuje elementy w poszczególnych kolumnach macierzy B, sumy szereguje nie rosnąco, sumuje elementy w kolejnych wierszach macierzy A, sumy szereguje nie malejąco, wektor rozwiązania startowego konstruuje w ten sam sposób co Algorytm 1.
W oknie programu poniżej pola do zadawania parametrów znajduje się pole, w którym wyświetlane są wartości funkcji celu. Wartość funkcji celu startowa obliczona na podstawie wektora startowego Pst, i pod spodem wartość funkcji celu minimalna, która zmienia się podczas obliczeń algorytmu i za każdą zmianą jej wartość jest w tym polu uaktualniana.
Pod spodem znajduje się wskaźnik postępu algorytmu, który pokazuje ile iteracji zostało już wykonanych.
Na dole znajduje się pole, w którym wyświetlane są wektory rozwiązania startowego i minimalnego.
Są to wszystkie potrzebne elementy w oknie do sprawnej obsługi algorytmu.
Następnym przyciskiem na pasku narzędziowym jest przycisk Drukuj. Naciśnięcie tego przycisku spowoduje otwarcie okienka dialogowego drukowania, którego wygląd przedstawiono na rysunku poniżej.
Okienko dialogowe drukowania wyświetla aktualny stan drukarki, jej nazwę, umożliwia wywołanie okna właściwości drukarki, w którym w zależności od typu i oprogramowania drukarki można dokonać m.in. zmiany jakości papieru, jakości wydruku, i wiele innych opcji; posiada pole do wpisania ilości kopii do druku. Naciśnięcie przycisku OK powoduje wydrukowanie bieżącego okna programu.
Następne trzy przyciski umożliwiają podgląd macierzy z danymi, tzn. naciśnięcie przycisku Macierz A powoduje wyświetlenie w oknie programu danych w macierzy A, podobnie działają przyciski Macierz B i Macierz C.
Następny przycisk Algorytm powoduje wyświetlenie okna algorytmu opisanego powyżej podczas opisu przycisku Otwórz.
Kolejny przycisk Start uruchamia algorytm Tabu Search i jest aktywny tylko wtedy gdy widoczne jest okno algorytmu. Po naciśnięciu przycisku na grafie rysowany jest przebieg funkcji celu, obok po lewej wyświetlana jest wartość aktualna funkcji celu, poniżej zmienia się wskaźnik postępu algorytmu do momentu gdy ilość iteracji osiągnie wartość parametru K. Wtedy w dole okna wyświetlany jest znaleziony wektor rozwiązania minimalnego.
Przycisk Historia wyświetla okno, w którym znajdują się wszystkie wywołania algorytmu, tzn. okno to zawiera listę, w której nowy rekord dopisywany jest po każdorazowym wywołaniu algorytmu. Rekord zawiera następujące informacje o danym wywołaniu algorytmu: plik skąd pochodzą dane, rozmiar problemu, czy problem zawiera macierz A, czy macierz B, czy macierz C, wartości parametrów K, T i alfa, wartość funkcji celu startową i minimalną, plik do którego zapisano kolejne wartości funkcji celu podczas poszukiwania rozwiązania.
Następny przycisk Pomoc wyświetla pomoc programu. Pomoc programu zawiera podstawowe informacje o problemie QAP i procedurze Tabu Search oraz instrukcję obsługi programu.
Ostatnim dostępnym przyciskiem jest przycisk Koniec, który kończy działanie programu.
Pasek narzędziowy zawiera jeszcze menu rozwijalne, które można wywołać klikając prawym przyciskiem myszki w obrębie paska.
Za pomocą menu rozwijanego można decydować o tym co ma być widoczne w oknie programu. Tzn. można wyświetlić menu główne programu, które normalnie jest niewidoczne, można wyłączyć pasek przycisków lub tylko etykiety przycisków, można włączyć lub wyłączyć wyświetlanie okna głównego, można włączyć lub wyłączyć wyświetlanie paska statusu. Pasek statusu zawiera podpowiedzi lub informację o obiekcie, nad którym znajduje się aktualnie wskaźnik myszy. Gdy pasek statusu jest niewidoczny, te same informacje wyświetlane są w oknie algorytmu nad grafem. Menu główne zawiera te same opcje co przyciski na pasku narzędzi. Można dodatkowo wyświetlić wizytówkę programu, zawierającą podstawowe informacje o programie i autorze. Są to wszystkie podstawowe informacje o obsłudze programu. W następnym punkcie przedstawiono szczegółowo w jaki sposób zrealizowano interfejs graficzny i opisano dokładnie funkcje obsługi poszczególnych zdarzeń np. naciśnięcie przycisku.
2.3. Budowa interfejsu graficznego
System BilderC++ zawiera bardzo wygodną bibliotekę gotowych obiektów Visual Component Library w skrócie VCL. Budowa aplikacji za pomocą tej biblioteki sprowadza się do stworzenia nowego formularza, na którym za pomocą myszki umieszcza się poszczególne komponenty. Każdy komponent posiada swoje właściwości, jak m.in. rozmiar, kolor, czcionka, i wiele innych. Właściwości te są zmieniane na etapie projektowania przy pomocy Inspektora Obiektów poprzez wpisanie odpowiednich wartości w pola poszczególnych właściwości.
Jako pasek narzędzi w programie został wykorzystany komponent ToolBar z biblioteki VCL. Zawiera on 10 przycisków czyli komponentów typu ToolButton. Do zarządzania widokiem w oknie głównym programu wykorzystano komponent PageControl, w którym zdefiniowano pięć stron (komponenty TabSheet): TabSheetMacierzA, TabSheetMacierzB, TabSheetMacierzC, TabSheetTS, TabSheetHistoria. Na trzech pierwszych stronach wyświetlane są macierze A, B, i C za pomocą umieszczonych na nich komponentów StringGrid, które ułatwiają wyświetlanie danych w tabelach. Czwarta strona poświęcona jest algorytmowi Tabu Search. Umieszczono na niej trzy komponenty typu Edit, które służą zadawaniu parametrów K, T, i alfa; jeden komponent typu ComboBox za pomocą którego można wybrać algorytm konstrukcyjny; jeden komponent typu PerformanceGraph za pomocą którego wykreślana jest funkcja celu; jeden komponent typu ProgressBar czyli wskaźnik postępu; 5 komponentów typu Bevel, czyli ramki wpływające na wygląd estetyczny okna; jeden komponent typu StringGrid wyświetlający wektory rozwiązań startowy i minimalny; 22 komponenty typu Label, czyli etykiety zawierające tekst, przy czym tekst w 19 etykietach jest stały i nie zmienia się podczas pracy programu, a tekst w trzech etykietach ulega zmianie, są to etykieta o nazwie LabelOpisAlgorytmu, która wyświetla nazwę pliku z którego pochodzą dane, oraz rozmiar problemu, etykieta o nazwie LabelQst wyświetlająca wartość funkcji celu startową, etykieta LabelQmin, która po każdorazowym wyznaczeniu lepszego rozwiązania wyświetla aktualną wartość funkcji celu. Na piątej stronie umieszczono komponent typu StringGrid, który wyświetla informacje o wszystkich wywołaniach algorytmu z poszczególnymi parametrami, nowe wywołanie algorytmu to nowy rekord na liście. Formularz główny posiada również komponent typu StatusBar, który pełni funkcje paska statusowego oraz komponent MainMenu, który jest głównym menu programu. Do zarządzania widokiem całości programu wykorzystano komponent CoolBar będący elastycznym paskiem narzędzi. Elastyczny pasek narzędzi podzielony jest na taśmy (ang. band). Komponent MainMenu umieszczony jest na taśmie o indeksie 0, komponent ToolBar na taśmie o indeksie 1, komponent PageControl na taśmie o indeksie 2, komponent StatusBar na taśmie o indeksie 3. Elastyczny pasek narzędzi dopuszcza zmianę wielkości poszczególnych taśm oraz ich kolejność podczas działania programu, jednak w tym programie takie działanie zostało zablokowane, ponieważ stwierdzono, że nie ma takiej potrzeby. Pasek statusowy pojawia się zawsze na samym dole okna, nad nim okno główne, w którym wyświetlane są poszczególne strony komponentu PageControl, nad nim pasek narzędziowy i na samej górze menu główne.
2.4. Opis funkcji obsługi zdarzeń
Pierwszą funkcją, która zostanie omówiona jest funkcja obsługi zdarzenia OnCreate formularza głównego i jest wywoływana w momencie uruchamiania programu. Poniżej znajduje się listing tej funkcji.
void __fastcall TMainForm::OnCreate(TObject *Sender)
{
Application->OnHint = OnHint;
OpisHistorii();
ileTS = 0;
}
W pierwszym wierszu funkcji, obsłudze zdarzenia OnHint formularza głównego przypisywana jest funkcja o tej samej nazwie OnHint. Zdarzenie OnHint jest generowane podczas przemieszczania kursora myszki nad danym komponentem i powoduje wyświetlanie podpowiedzi jeśli taka została wcześniej zdefiniowana dla tego komponentu. Domyślnie podpowiedzi wyświetlane są w pasku statusowym i nie trzeba definiować własnej funkcji obsługi zdarzenia OnHint. W programie zdecydowano się aby podpowiedzi wyświetlane były za pomocą etykiety LabelOpisTS, należącej do strony TabSheetTS, gdy pasek statusowy jest niewidoczny. Poniżej znajduje się zawartość funkcji OnHint.
void __fastcall TMainForm::OnHint(TObject *Sender)
{
if(!CoolBar->Bands->Items[3]->Visible)
LabelOpisTS->Caption = Application->Hint;
else
StatusBar->Panels->Items[0]->Text = Application->Hint;
}
Jeśli pasek statusowy jest niewidoczny wyświetlaj podpowiedzi za pomocą etykiety LabelOpisTS. W przeciwnym przypadku wyświetlaj je w pasku statusowym.
W drugim wierszu funkcji OnCreate wywoływana jest funkcja OpisHistorii , która ma za zadanie wyświetlić etykiety kolumn w komponencie StringGridHistoria na stronie TabSheetHistoria. Poniżej znajduje się zawartość tej funkcji.
void TMainForm::OpisHistorii(void)
{
StringGridHistoria->Cells[1][0] = "Otwarto z:";
StringGridHistoria->Cells[2][0] = " n";
StringGridHistoria->Cells[3][0] = " A";
StringGridHistoria->Cells[4][0] = " B";
StringGridHistoria->Cells[5][0] = " C";
StringGridHistoria->Cells[6][0] = " K";
StringGridHistoria->Cells[7][0] = " T";
StringGridHistoria->Cells[8][0] = "alfa";
StringGridHistoria->Cells[9][0] = " Qst";
StringGridHistoria->Cells[10][0] = " Qmin";
StringGridHistoria->Cells[11][0] = "Alg. konstr.";
StringGridHistoria->Cells[12][0] = "Zapisano do:";
StringGridHistoria->Cells[0][1] = "1";
}
W trzecim wierszu funkcji OnCreate zerowana jest zmienna globalna ileTS, która zlicza kolejne wywołania algorytmu Tabu Search, tzn. kolejne naciśnięcie przycisku Start. Wprowadzona została w celu automatycznej numeracji plików, do których zapisywane są kolejne wartości funkcji celu podczas obliczeń algorytmu.
Polecenia menu głównego posiadają takie same funkcje obsługi zdarzeń jak przyciski na pasku narzędziowym. Przycisk Otwórz posiada funkcję obsługi zamieszczoną poniżej.
void __fastcall TMainForm::MenuOpenClick(TObject *Sender)
{
int rozmiar = 0;
if(OpenDialog->Execute()){
ifstream file(OpenDialog->FileName.c_str());
file >> rozmiar;
if(pProblem != NULL){
delete pProblem;
pProblem = NULL;
}
pProblem = new QAP(rozmiar);
int Krzys = pProblem->WczytajMacierze(file);
if(Krzys > 0){
if(Krzys == 1){
pProblem->MacierzA = true;
ToolButtonMacierzB->Enabled = false;
ToolButtonMacierzC->Enabled = false;
}
if(Krzys == 2){
pProblem->MacierzA = true;
pProblem->MacierzB = true;
ToolButtonMacierzC->Enabled = false;
}
if(Krzys == 3){
pProblem->MacierzA = true;
pProblem->MacierzB = true;
pProblem->MacierzC = true;
}
if(!CoolBar->Bands->Items[2]->Visible)
CoolBar->Bands->Items[2]->Visible = true;
if(pTabu != NULL){
delete pTabu;
pTabu = NULL;
}
pTabu = new TS(pProblem);
LabelOpisProblemu->Caption = "Problem wczytany z pliku: " +
ExtractFileName(OpenDialog->FileName) +
". Rozmiar problemu: " + IntToStr(pProblem->ZwrocRozmiar()) + ".";
LabelOpisProblemu->Repaint();
StringGridPI->RowCount = 0;
StringGridPI->Repaint();
for(int i=0; i< rozmiar; i++){
StringGridPI->Cells[i][1] = 0;
StringGridPI->Repaint();
}
Wykres->Visible = false;
for(int i=0; i<100; i++){
Wykres->DataPoint(clRed,0);
Wykres->Update();
}
Wykres->Visible = true;
ButtonActivate(true);
ToolButtonStart->Enabled = false;
}
else{
delete pProblem;
Application->MessageBox("Niewlasciwy format pliku !", "Blad",
MB_ICONHAND | MB_OK);
}
file.close();
}
}
W pierwszym wierszu deklarowana jest zmienna typu całkowitego o nazwie rozmiar, która jest zmienną lokalną tej funkcji i ma za zadanie pamiętać rozmiar wczytanego problemu. W drugim wierszu wywoływane jest okienko dialogowe otwarcia pliku. Możliwość otwarcia pliku została ograniczona do plików z rozszerzeniem .dat poprzez wprowadzenie odpowiedniego filtru we właściwości filter komponentu okienka dialogowego. W przypadku kliknięcia przycisku Anuluj nie są wykonywane żadne instrukcje i funkcja MenuOpenClick() ulega zakończeniu. Jeśli plik z danymi został wybrany i kliknięto przycisk OK. wykonywany jest dalszy ciąg instrukcji. Tworzony jest obiekt file klasy ifstream i automatycznie otwierany plik o nazwie zapisanej we właściwości FileName okienka dialogowego otwarcia pliku. Ponieważ konstruktor obiektu file klasy ifstream wymaga parametru typu wskaźnika znakowego char*, a właściwość FileName jest typu obiekt klasy AnsiString dlatego wykorzystano standardowš metodę c_str(), która zapewnia odpowiednią konwersję. Następnie odczytana zostaje pierwsza liczba z pliku, która informuje o rozmiarze zdefiniowanego w pliku problemu. Dalej sprawdzane jest czy zmienna globalna pProblem, będąca wskaźnikiem typu QAP, zawiera adres obiektu. Jeśli tak obiekt jest niszczony i zerowany wskaźnik. Następnie dynamicznie przydzielana jest pamięć dla obiektu typu QAP o adresie wpisanym pod wskaźnik pProblem, za pomocą operatora new. Wywoływany jest konstruktor klasy QAP z jednym parametrem, w którym przekazywany rozmiar problemu. W następnym wierszu wywoływana jest funkcja WczytajMacierze(file) obiektu QAP, która odczytuje dane z pliku. Dokładny opis funkcji znajduje się w dalszej części pracy, gdy omawiane są dokładnie poszczególne klasy. Funkcja WczytajMacierze(file) zwraca ilość odczytanych macierzy z pliku. Jest to wykorzystywane w kolejnych wierszach do ustawienia zmiennych typu bool MacierzA, MacierzB, MacierzC, obiektu QAP odpowiednio na wartość true lub false, oraz w zależności od tego które macierze zostały odczytane, odpowiednie przyciski na pasku narzędziowym są blokowane.
Wcześniej wywoływana jest funkcja ButtonActivate(true), która udostępnia wszystkie przyciski nieaktywne. Gdy parametr funkcji posiada wartość false to wszystkie przyciski są blokowane.
void TMainForm::ButtonActivate(bool _aktywne)
{
ToolButtonTS->Enabled = _aktywne;
ToolButtonHistoria->Enabled = _aktywne;
ToolButtonDrukuj->Enabled = _aktywne;
ToolButtonMacierzA->Enabled = _aktywne;
ToolButtonMacierzB->Enabled = _aktywne;
ToolButtonMacierzC->Enabled = _aktywne;
MenuAMatrix->Enabled = _aktywne;
MenuBMatrix->Enabled = _aktywne;
MenuCMatrix->Enabled = _aktywne;
MenuTabuSearch->Enabled = _aktywne;
MenuStart->Enabled = _aktywne;
MenuHistoria->Enabled = _aktywne;
MenuPrint->Enabled = _aktywne;
MenuPrintSetup->Enabled = _aktywne;
}
Następnie jeśli widok programu ograniczał się do paska narzędzi okno programu zostaje powiększone, i widoczna jest strona TabSheetTS komponentu PageControl. W kolejnym wierszu sprawdzane jest czy istnieje obiekt TS, poprzez sprawdzenie czy wskaźnik pTabu zawiera adres obiektu , czy wartość NULL. Jeśli obiekt TS istniał jest niszczony i zerowany wskaźnik. Następnie dynamicznie przydzielana jest pamięć dla obiektu TS, za pomocą operatora new, wywoływany jest konstruktor klasy TS, oraz adres obiektu w pamięci przypisywany jest pod zmienną pTabu. W kolejnym wierszu uaktualniana jest informacja o problemie za pomocą etykiety LabelOpisProblemu na stronie TabSheetTS. Zmieniona zostaje nazwa pliku, z którego pochodzą dane, oraz rozmiar problemu. Metoda Repaint() zapewnia prawidłowe wyświetlenie nowych danych. Kolejne wiersze zerują dane w komponencie StringGridPI, który wyświetla wektory rozwiązań startowy i minimalny. Również zawartość grafu jest czyszczona. Zapewniają to kolejne wiersze. Następnie blokowany jest przycisk "Start", do momentu wybrania algorytmu konstrukcyjnego i ustalenia rozwiązania startowego. Wtedy przycisk "Start" jest udostępniany. Są to wszystkie czynności wykonywane w funkcji MenuOpenClick() jeśli wykonanie funkcji WczytajMacierze(file) powiodło się. W przeciwnym przypadku kasowany jest obiekt o adresie przechowywanym pod wskaźnikiem pProblem i wyświetlane jest okienko z informacją: Niewłaściwy format pliku !. Na koniec zamykany jest plik i niszczony obiekt file. Po wykonaniu funkcji MenuOpenClick() przydzielona została pamięć dla dwóch obiektów. Pierwszy obiekt powstały na bazie klasy QAP zawierający dane o problemie oraz drugi obiekt utworzony na podstawie klasy TS, przygotowany do obsługi algorytmu TabuSearch.
Przycisk Drukuj zawiera funkcję obsługi zdarzenia zamieszczoną poniżej.
void __fastcall TMainForm::MenuPrintClick(TObject *Sender)
{
if(PrintDialog->Execute())
Print();
}
Funkcja ta posiada tylko jeden wiersz, w którym wywoływane jest okienko dialogowe drukowania. Jeśli został naciśnięty przycisk OK, wtedy wywoływana jest metoda Print(), która powoduje wydrukowanie bieżącego okna. W zależności, która strona komponentu PageControl jest aktywna, taka zostanie wydrukowana.
Przyciski Macierz A, macierz B, Macierz C posiadają podobne funkcje obsługi.
void __fastcall TMainForm::MenuAMatrixClick(TObject *Sender)
{
if(PageControl->Visible == false)
PageControl->Visible = true;
PageControl->ActivePage = TabSheetMacierzA;
ToolButtonStart->Enabled = false;
}
void __fastcall TMainForm::MenuBMatrixClick(TObject *Sender)
{
if(PageControl->Visible == false)
PageControl->Visible = true;
PageControl->ActivePage = TabSheetMacierzB;
ToolButtonStart->Enabled = false;
}
void __fastcall TMainForm::MenuCMatrixClick(TObject *Sender)
{
if(PageControl->Visible == false)
PageControl->Visible = true;
PageControl->ActivePage = TabSheetMacierzC;
ToolButtonStart->Enabled = false;
}
W pierwszym i drugim wierszu funkcji włączane jest okno główne programu jeśli było nieaktywne. Wszystkie powyższe funkcje różnią się trzecim wierszem, w którym ustalana jest aktualna strona komponentu PageControl, czyli która macierz ma być wyświetlona. Instrukcja w Ostatnim wierszu blokuje przycisk Start, który jest uaktywniany jedynie po wyborze nowego algorytmu konstrukcyjnego.
Przycisk Algorytm posiada funkcję obsługi zamieszczoną poniżej.
void __fastcall TMainForm::ToolButtonTSClick(TObject *Sender)
{
if(PageControl->Visible == false) PageControl->Visible = true;
PageControl->ActivePage = TabSheetTS;
}
Funkcja posiada tylko dwa wiersze, instrukcja w pierwszym włącza okno główne programu jeśli było niewidoczne, instrukcja w drugim ustala aktywną stronę komponentu PageControl na TabSheetTS.
Przycisk Start posiada funkcję obsługi zamieszczoną poniżej.
void __fastcall TMainForm::ToolButtonStartClick(TObject *Sender)
{
int i;
int rozmiar = pProblem->ZwrocRozmiar();
String sk = EditK->Text;
String st = EditT->Text;
String sa = EditA->Text;
Wektor Pii;
int k, t;
float alfa;
try{
k = StrToInt(sk);
t = StrToInt(st);
alfa = StrToFloat(sa);
pTabu->NoweK(k);
pTabu->NoweT(t);
pTabu->NoweAlfa(alfa);
pTabu->AlgorytmTS();
DodajDoHistorii();
Pii = pTabu->ZwrocPImin();
StringGridPI->RowCount = 2;
StringGridPI->Repaint();
for(i=0; i< rozmiar; i++){
StringGridPI->Cells[i][1] = Pii(i)+1;
StringGridPI->Repaint();
}
TabSheetTS->Repaint();
LabelQmin->Caption = FloatToStr((float)pTabu->ZwrocQmin());
LabelQmin->Repaint();
ToolButtonStart->Enabled = false;
}
catch(...){
Application->MessageBox("Niewlasciwy parametr !",
"Blad", MB_ICONHAND | MB_OK);
}
}
W pierwszej części funkcji deklarowane są zmienne: dwie typu całkowitego, pierwsza o nazwie i wykorzystywana do indeksowania w pętli for, druga o nazwie rozmiar, która jest inicjowana wartością zwracaną przez funkcję ZwrocRozmiar() obiektu QAP; trzy obiekty typu String, które są inicjowane wartościami parametrów K,T,a pobranymi z pól edycyjnych znajdujących się na stronie TabSheetTS.; jeden obiekt typu Wektor o nazwie Pii; dwie zmienne typu całkowitego, k przechowująca ilość iteracji, t przechowująca wartość okresu karencji dla danej pary; jedną zmienną typu float o nazwie alfa przechowującą wartość parametru alfa. Następnie wykonywane są instrukcje następujące po instrukcji try. Jeśli wykonanie którejś z tych instrukcji nie powiedzie się, zostanie zgłoszony wyjątek, przechwycony przez instrukcję catch, i wykonane zostaną instrukcje obsługi wyjątku, tzn. wyświetlone zostanie okienko z informacją: Niewłaściwy parametr !. Oznacza to przechwycenie wyjątku o niemożliwości wykonania konwersji za pomocą instrukcji StrToInt() lub StrToFloat(). Konwersje te są dokonywane w pierwszych wierszach następujących po instrukcji try. Następnie nowe parametry k, t, alfa otrzymane po konwersji tekstu z pól edycyjnych są wpisywane do obiektu TS za pomocą funkcji zdefiniowanych dla tego obiektu: NoweK(), NoweT(), NoweAlfa(). W następnym wierszu wywoływana jest funkcja AlgorytmTS() obiektu TS, która zawiera ciało algorytmu TabuSearch. Funkcja ta zostanie omówiona w dalszej części pracy. Po zakończeniu obliczeń algorytmu TabuSearch wywoływana jest funkcja DodajDoHistorii(). Program zapamiętuje każde wywołanie algorytmu wraz z parametrami jego wywołania, i zapisuje je jako kolejny rekord w tabeli na stronie TabSheetHistoria. Dokonuje tego właśnie funkcja DodajDoHistorii().
void TMainForm::DodajDoHistorii()
{
String a,b,c;
int n = StringGridHistoria->RowCount;
if(pProblem->MacierzA == true)
a = "Tak";
else {a = "Nie";}
if(pProblem->MacierzB == true)
b = "Tak";
else
b = "Nie";
if(pProblem->MacierzC == true)
c = "Tak";
else
c = "Nie";
StringGridHistoria->Cells[1][n-1] = ExtractFileName(OpenDialog->FileName);
StringGridHistoria->Cells[2][n-1] = IntToStr(pProblem->ZwrocRozmiar());
StringGridHistoria->Cells[3][n-1] = a;
StringGridHistoria->Cells[4][n-1] = b;
StringGridHistoria->Cells[5][n-1] = c;
StringGridHistoria->Cells[6][n-1] = IntToStr(pTabu->ZwrocK());
StringGridHistoria->Cells[7][n-1] = IntToStr(pTabu->ZwrocT());
StringGridHistoria->Cells[8][n-1] = FloatToStr(pTabu->ZwrocAlfa());
StringGridHistoria->Cells[9][n-1] = FloatToStr((float)pTabu->ZwrocQst());
StringGridHistoria->Cells[10][n-1] = FloatToStr((float)pTabu->ZwrocQmin());
StringGridHistoria->Cells[11][n-1] = pProblem->ZwrocAlgorytmSt();
StringGridHistoria->Cells[12][n-1] = pTabu->ZwrocNazwePliku();
StringGridHistoria->RowCount = n + 1;
StringGridHistoria->Cells[0][n] = n;
}
W pierwszym wierszu deklarowane są trzy obiekty a, b, c klasy String. Następnie w zależności od zawartości zmiennych MacierzA, MacierzB, MacierzC, obiektu QAP, obiektom a, b, c, przypisywane są cišgi znaków Tak lub Nie. Następnie dla aktualnego rekordu do kolejnych kolumn tabeli wpisywane są poszczególne wartości. W pierwszym polu rekordu wpisywana jest nazwa pliku, z którego pochodzą dane, w drugim polu rozmiar problemu n pobrany wcześniej za pomocą funkcji ZwrocRozmiar() obiektu QAP. W kolejnych trzech polach wpisywana jest zawartość obiektów a, b, c, następne trzy pola zawierają wartości parametrów K, T, a pobranych z obiektu TS za pomocą funkcji ZwrocK(), ZwrocT(), ZwrocAlfa(), kolejne dwa pola to wartości funkcji celu startowa i minimalna pobrane również z obiektu TS za pomocš funkcji ZwrocQst() i ZwrocQmin(). Następne pole jest wypełniane ciągiem znaków zwracanym przez funkcję ZwrocAlgorytmSt() obiektu QAP, ostatnie pole rekordu zawiera nazwę pliku gdzie zostały zapisane kolejne wartości funkcji celu, nazwa ta wpisywana jest za pomocą funkcji ZwrocNazwePliku() obiektu TS. W przedostatnim wierszu funkcji DodajDoHistorii() tworzony jest nowy rekord w tabeli StringGridHistoria, a w ostatnim wierszu jest on numerowany kolejną wartością.
W następnym wierszu funkcji ToolButtonStartClick() lokalnemu obiektowi Pii klasy Wektor przypisywany jest wektor rozwiązania otrzymany po wykonaniu funkcji AlgorytmTS(). Wektor rozwiązania otrzymywany jest z obiektu TS za pomocą funkcji ZwrocPImin(). W kolejnych wierszach wektor Pii jest wpisywany do tabeli StringGridPI. Następnie odświeżana jest zawartość strony, oraz wartość funkcji celu obliczona dla znalezionego rozwiązania jest wyświetlana za pomocą etykiety LabelQmin, a dokładnie jej właściwości Caption.
Przycisk Historia posiada funkcję obsługi zamieszczoną poniżej.
void __fastcall TMainForm::ToolButtonHistoriaClick(TObject *Sender)
{
if(PageControl->Visible == false)
PageControl->Visible = true;
PageControl->ActivePage = TabSheetHistoria;
ToolButtonStart->Enabled = false;
}
Funkcja wyświetla okno główne programu jeśli było niewidoczne, przełącza aktywną stronę w komponencie PageControl na TabSheetHistoria oraz blokuje przycisk Start.
Przycisk Koniec posiada funkcję obsługi zamieszczoną poniżej.
void __fastcall TMainForm::MenuExitClick(TObject *Sender)
{
if(pProblem != NULL)
delete pProblem;
if(pTabu != NULL)
delete pTabu;
Application->Terminate();
}
Funkcja sprawdza czy istnieją obiekty QAP i TS. Jeśli tak są one niszczone. Następnie wywoływana jest metoda Terminate(), która kończy działanie programu.
Powyżej przedstawione zostały wszystkie funkcje obsługi zdefiniowane dla przycisków paska narzędziowego, oraz tych samych poleceń menu głównego. W programie istnieją inne zdarzenia, które posiadają swoje funkcje obsługi. Funkcje te zostały przedstawione poniżej.
Kliknięcie polecenia Macierze z menu głównego powoduje wykonanie funkcji obsługi zamieszczonej poniżej.
void __fastcall TMainForm::MenuMatricesClick(TObject *Sender)
{
if(PageControl->ActivePage == TabSheetMacierzA)
MenuAMatrix->Checked = true;
else
MenuAMatrix->Checked = false;
if(PageControl->ActivePage == TabSheetMacierzB)
MenuBMatrix->Checked = true;
else
MenuBMatrix->Checked = false;
if(PageControl->ActivePage == TabSheetMacierzC)
MenuCMatrix->Checked = true;
else
MenuCMatrix->Checked = false;
}
Funkcja ma za zadanie sprawdzać w momencie kliknięcia polecenia Macierze menu głównego, która strona komponentu PageControl jest aktywna, i ustawić znacznik w menu rozwijanym dla polecenia Macierze menu głównego na odpowiedniej pozycji.
Funkcja MenuWidokClick() obsługuje zdarzenie związane z wybraniem polecenia Widok menu głównego. Polecenie Widok zarządza widokiem programu, tzn. włącza lub wyłącza poszczególne elementy okna programu: pasek narzędzi, menu główne, okno główne programu (komponent PageControl), pasek statusu. Funkcja MenuWidokClick() ma za zadanie sprawdzać, które z elementów są widoczne w momencie wybrania polecenia Widok i na tej podstawie uaktualnić znaczniki obok elementów widocznych lub niewidocznych w menu rozwiniętym po wybraniu polecenia Widok.
void __fastcall TMainForm::MenuWidokClick(TObject *Sender)
{
if(ToolBar->Visible){
MenuPasekprzyciskow->Checked = true;
MenuTekstnaprzyciskach->Enabled = true;
}
else{
MenuPasekprzyciskow->Checked = false;
MenuTekstnaprzyciskach->Enabled = false;
}
if(PageControl->Visible)
MenuOknodanych->Checked = true;
else
MenuOknodanych->Checked = false;
if(StatusBar->Visible)
MenuPasekstatusowy->Checked = true;
else
MenuPasekstatusowy->Checked = false;
if(ToolBar1->Visible)
MenuMenuglowne->Checked = true;
else
MenuMenuglowne->Checked = false;
if(ToolBar->ShowCaptions)
MenuTekstnaprzyciskach->Checked=true;
else
MenuTekstnaprzyciskach->Checked = false;
}
Wybierając polecenie Widok z menu głównego wykonana zostaje funkcja MenuWidokClick() po czym rozwinięte zostaje podmenu pokazane na rysunku 10. Wybranie polecenia Pasek przycisków powoduje wykonanie funkcji obsługi zamieszczonej poniżej.
void __fastcall TMainForm::MenuPasekprzyciskowClick(TObject *Sender)
{
if(CoolBar->Bands->Items[1]->Visible){
if(!CoolBar->Bands->Items[0]->Visible)
CoolBar->Bands->Items[0]->Visible = true;
CoolBar->Bands->Items[1]->Visible = false;
}
else
CoolBar->Bands->Items[1]->Visible = true;
}
Funkcja ta włącza lub wyłącza widoczność drugiej bandy komponentu CoolBar na której umieszczono pasek z przyciskami. Dodatkowo funkcja posiada zabezpieczenie przed wyłączeniem paska przycisków, wtedy gdy menu główne jest niewidoczne. W takim przypadku funkcja automatycznie włącza widoczność menu głównego, a dokładnie bandy pierwszej (indeksowanie od 0) komponentu CoolBar.
Podobnie działa funkcja MenuMenuglowneClick(), którą zamieszczono poniżej.
void __fastcall TMainForm::MenuMenuglowneClick(TObject *Sender)
{
if(CoolBar->Bands->Items[0]->Visible){
if(!CoolBar->Bands->Items[1]->Visible)
CoolBar->Bands->Items[1]->Visible = true;
CoolBar->Bands->Items[0]->Visible = false;
}
else CoolBar->Bands->Items[0]->Visible = true;
}
Funkcja ta wywoływana jest po wybraniu polecenia Menu glówne z podmenu zamieszczonego na rysunku 10. Włącza lub wyłącza widoczność menu głównego, posiada takie samo zabezpieczenie jak funkcja MenuPasekprzyciskowClick().
Funkcja MenuOknodanychClick() wykonywana jest w momencie wybrania polecenia Okno główne z podmenu zamieszczonego na rysunku 10. Włącza lub wyłącza widoczność komponentu PageControl.
void __fastcall TMainForm::MenuOknodanychClick(TObject *Sender)
{
if(CoolBar->Bands->Items[2]->Visible)
CoolBar->Bands->Items[2]->Visible = false;
else
CoolBar->Bands->Items[2]->Visible = true;
}
Funkcja MenuPasekstatusowyClick() wykonywana jest w momencie wybrania polecenia Pasek statusowy z podmenu zamieszczonego na rysunku 10. Włącza lub wyłącza widoczność komponentu StatusBar.
void __fastcall TMainForm::MenuPasekstatusowyClick(TObject *Sender)
{
if(CoolBar->Bands->Items[3]->Visible)
CoolBar->Bands->Items[3]->Visible = false;
else
CoolBar->Bands->Items[3]->Visible = true;
}
Funkcja MenuTekstnaprzyciskachClick() ma za zadanie włączać lub wyłączać etykiety tekstowe na przyciskach paska narzędziowego.
void __fastcall TMainForm::MenuTekstnaprzyciskachClick(TObject *Sender)
{
if(ToolBar->ShowCaptions){
ToolBar->ShowCaptions = false;
ToolBar->ButtonHeight = 25;
ToolBar->ButtonWidth = 27;
}
else{
ToolBar->ShowCaptions = true;
}
}
Powyższa funkcja dodatkowo po wyłączeniu wyświetlania etykiet tekstowych na przyciskach, zmienia rozmiar przycisków. Do rozmiaru przycisków automatycznie dostosowuje się wielkość paska narzędziowego, poprzez ustawienie jego właściwości AutoSize na true.
Funkcja StatusBarDblClick() posiada funkcję obsługi zamieszczoną poniżej.
void __fastcall TMainForm::StatusBarDblClick(TObject *Sender)
{
StatusBar->Hide();
}
Funkcja ta ma za zadanie wyłączyć widzialność paska statusowego po dwukrotnym kliknięciu prawym przyciskiem myszy w obszarze paska.
Funkcja ComboBoxClick() jest wywoływana w momencie wybrania pozycji z listy rozwijanej umieszczonej na stronie TabSheetTS. Na liście umieszczone są trzy pozycje, nazwy dostępnych algorytmów konstrukcyjnych. Wybranie pozycji z listy poprzez jej kliknięcie lewym przyciskiem myszy powoduje wywołanie funkcji obsługi tego zdarzenia którą zamieszczono poniżej.
void __fastcall TMainForm::ComboBoxClick(TObject *Sender)
{
int i, rozmiar = pProblem->ZwrocRozmiar();
String alg = ComboBox->Text;
Wektor Pii;
if(pProblem->AlgorytmStartowy(alg)){
pTabu->UstalProblem();
Pii = pTabu->ZwrocPIst();
StringGridPI->ColCount = rozmiar;
StringGridPI->RowCount = 1;
StringGridPI->Repaint();
for(i=0; i< rozmiar; i++){
StringGridPI->Cells[i][0] = Pii(i)+1;
StringGridPI->Repaint();
}
TabSheetTS->Repaint();
LabelQst->Caption = FloatToStr((float)pTabu->ZwrocQmin());
LabelQst->Repaint();
LabelQmin->Caption = LabelQst->Caption;
LabelQmin->Repaint();
ToolButtonStart->Enabled = true;
}
else
Application->MessageBox("Nie wygenerowano rozwiazania startowego !",
"Blad", MB_ICONHAND | MB_OK);
}
Funkcja powyższa w pierwszym wierszu deklaruje dwie zmienne lokalne typu całkowitego, pierwsza o nazwie i wykorzystywana jako indeks w pętli for, druga rozmiar inicjowana w tym samym wierszu wartością zwracaną przez funkcję ZwrocRozmiar() obiektu QAP. W drugim wierszu deklarowany jest lokalny obiekt o nazwie alg klasy String, inicjowany tekstem wybranym z listy rozwijanej ComboBox, w trzecim wierszu deklarowany jest lokalny obiekt klasy Wektor o nazwie Pii. Następnie wywoływana jest funkcja AlgorytmStartowy obiektu QAP z parametrem alg. Funkcja ta zawiera trzy algorytmy generujące rozwiązanie startowe, w zależności od parametru alg wywoływany jest odpowiedni algorytm. Dokładny opis działania tej funkcji przedstawiony jest w dalszej części pracy podczas opisu funkcji i składowych obiektów.
Jeśli obliczenia algorytmu konstrukcyjnego zakończyły się pomyślnie, i wygenerowane zostało rozwiązanie startowe Pst funkcja zwraca wartość true, i wykonywane są wszystkie następne instrukcje umieszczone w klamrach instrukcji if. Wywoływana jest funkcja UstalProblem() obiektu TS, która ma za zadanie zainicjować trzy pola obiektu TS: PIst, Qst, Qmin. Dokładny opis funkcji jest przedstawiony w dalszej części pracy. W następnym wierszu pod obiekt lokalny Pii przypisane zostaje pole PIst obiektu TS, za pomocą funkcji ZwrocPIst() tegoż obiektu. Obiekt lokalny Pii jest wykorzystywany do wyświetlenia rozwiązania startowego Pst, które jest przechowywane w polu PIst obiektu TS. W następnych wierszach wyświetlany jest wektor rozwiązania startowego przechowywany w obiekcie lokalnym Pii, za pomocą komponentu StringGridPI umieszczonego na stronie TabSheetTS. Następnie za pomocą etykiet tekstowych LabelQst i LabelQmin umieszczonych na stronie TabSheetTS wyświetlana jest wartość startowa funkcji celu. W ostatnim wierszu funkcji udostępniany jest przycisk Start na pasku narzędzi. Jeśli wykonanie funkcji AlgorytmStartowy nie powiodło się wyświetlone zostaje okienko z informacją o błędzie: Nie wygenerowano rozwiązania startowego..
2.5. Opis struktury klas obiektów
2.5.1. Klasa wektor
Klasa Wektor została napisana w celu tworzenia obiektów typu wektorowego tzn. jednowymiarowej tablicy elementów typu całkowitego o zadanym rozmiarze. Klasa posiada dwa pola prywatne widoczne tylko dla funkcji składowych tej klasy, trzy funkcje do tworzenia obiektów tej klasy zwane konstruktorami: pierwszy konstruktor domyślny, drugi konstruktor z parametrem zawierajšcym rozmiar tworzonego obiektu klasy Wektor oraz trzeci konstruktor kopiujący, który jest wykorzystywany w momencie inicjacji obiektu za pomocą obiektu tego samego typu; klasa posiada również przeciążony operator porównania "=", oraz przeciążony operator wywołania funkcji: ( ) jako operator indeksowania czyli operator dostępu do poszczególnych elementów wektora; klasa posiada również destruktor do usuwania obiektów.
class Wektor
{
int* pwektor;
int n;
public:
Wektor(void);
Wektor(int);
Wektor(const Wektor&);
~Wektor(void);
Wektor& operator=(Wektor&);
int& operator()(int);
};
Pola prywatne klasy to wskaźnik pwektor typu całkowitego przechowujący adres obszaru w pamięci zarezerwowanego dla utworzonego obiektu tej klasy, oraz zmienna typu całkowitego n przechowująca rozmiar wektora. Przedstawiony na listingu 26 plik nagłówkowy Wektor.h zawiera jedynie strukturę klasy Wektor. Dokładna budowa funkcji, czyli jej implementacja znajduje się w pliku Wektor.cpp. Poniżej przedstawiono jedynie budowę funkcji konstruującej obiekty typu Wektor.
Wektor::Wektor(int _n)
{
pwektor = new int[_n];
n = _n;
for(int i=0; i< n; i++)
pwektor[i] = 0;
}
W pierwszym wierszu funkcji przydzielona dynamicznie zostaje pamięć dla tablicy elementów typu całkowitego o wymiarze przekazanym do funkcji przez parametr _n. Adres obszaru pamięci zostaje wpisany do zmiennej pwektor. W drugim wierszu funkcji zainicjowana zostaje zmienna prywatna klasy n wartością przekazaną przez parametr _n. W następnych dwóch wierszach obiekt klasy Wektor zostaje zainicjowany wartościami 0 przy pomocy pętli for.
2.5.2. Klasa Tablica.
Klasa Tablica została utworzona w celu konstruowania obiektów typu macierzy kwadratowych o elementach typu całkowitego. Klasa ta posiada dwa pola prywatne, wskaźnik ptab typu całkowitego do obszaru pamięci gdzie przydzielono pamięć dla tablicy dwuwymiarowej, oraz zmienna typu całkowitego n przechowująca rozmiar macierzy. Klasa posiada trzy konstruktory, destruktor, oraz przeciążone operatory przypisania i wywołania funkcji. Podobnie jak opisana powyżej klasa Tablica. Poniżej przedstawiono strukturę klasy Tablica.
class Tablica
{
public:
int **ptab;
int n;
Tablica(void);
Tablica(int);
Tablica(const Tablica&);
~Tablica(void);
Tablica& operator=(Tablica&);
int& operator()(int,int);
};
Powyższa struktura to plik nagłówkowy klasy o nazwie Tablica.h. Natomiast definicje funkcji tzn. budowa znajdują się w pliku Tablica.cpp. Poniżej przedstawiono jedynie budowę konstruktora klasy Tablica.
Tablica::Tablica(int _n)
{
ptab = new int*[_n];
for(int i=0;i<_n;i++)
ptab[i] = new int[_n];
for(int i=0;i<_n;i++)
for(int j=0;j<_n;j++)
ptab[i][j] = 0;
n = _n;
};
W pierwszym wierszu przy pomocy operatora new przydzielana jest dynamicznie pamięć dla tablicy wskaźników typu całkowitego o rozmiarze przekazanym w parametrze funkcji _n. Adres w pamięci pod którym przechowywana jest tablica wskaźników wpisany jest pod zmienną ptab. Następnie przy pomocy pętli for przydzielona zostaje pamięć dla tablicy elementów typu całkowitego, przy czym w każdej iteracji adres przydzielonego obszaru w pamięci jest wpisywany pod kolejny element z utworzonej wcześniej dynamicznie tablicy wskaźników. Kolejne dwie pętle for inicjują elementy tablicy wartościami 0. W ostatnim wierszu funkcji rozmiar przechowywany w zmiennej lokalnej _n przepisywany jest do zmiennej prywatnej obiektu o nazwie n.
2.5.3. Klasa QAP.
Klasa QAP została stworzona w celu konstrukcji obiektów, które będą przechowywały dane o aktualnie wczytanym problemie. Struktura klasy została przedstawiona poniżej.
class QAP
{
int rozmiar;
Tablica A, B, C;
Wektor P;
public:
QAP(int _rozmiar);
bool AlgorytmStartowy(String);
String ZwrocAlgorytmSt(void);
int ZwrocRozmiar(void);
void NowyPI(Wektor&);
int WczytajMacierze(ifstream _file);
void WypiszMacierze(void);
void Permutacja(Para&);
double Q();
Wektor& ZwrocPI();
bool MacierzA;
bool MacierzB;
bool MacierzC;
String AlgorytmSt;
void WypiszPI();
};
Klasa posiada pięć pól prywatnych, pierwsze to zmienna typu całkowitego rozmiar przechowująca rozmiar problemu jakiego ten obiekt dotyczy. Trzy kolejne pola to obiekty klasy Tablica służące do przechowywania macierzy odczytanych z pliku, definiujących aktualny problem. Kolejne pole to obiekt klasy Wektor przechowujący wektor rozwiązania. Wektor ten ulega zmianie podczas pracy algorytmu Tabu Search ze względu na zamianę poszczególnych par elementów wektora P. Ostatnie pole to obiekt AlgStartowy klasy String przechowujący nazwę wybranego z listy algorytmu startowego. Pierwsza publiczna funkcja składowa to konstruktor z jednym parametrem przekazującym rozmiar problemu. Funkcja ta wywołuje bezpośrednio konstruktory klasy Tablica oraz Wektor i utworzone obiekty przypisuje obiektom prywatnym klasy QAP.
Funkcja WczytajMacierze() ma na celu odczytanie danych z pliku i wpisanie ich pod obiekty prywatne A,B,C.
{
while(!_file.eof()){
_file >> liczba;
ile++;
}
_file.seekg(0,ios_base::beg);
_file >> temp;
if(ile == (rozmiar*rozmiar) || ile == (rozmiar*rozmiar)+1){
for(i=0;i< rozmiar;i++)
for(j=0;j< rozmiar;j++)
_file >> A(i,j);
WypiszMacierze();
return 1;
}
else if(ile == (rozmiar*rozmiar*2) || ile == (rozmiar*rozmiar*2)+1){
for(i=0;i< rozmiar;i++)
for(j=0;j< rozmiar;j++)
_file >> A(i,j);
for(i=0;i< rozmiar;i++)
for(j=0;j< rozmiar;j++)
_file >> B(i,j);
WypiszMacierze();
return 2;
}
else if(ile == (rozmiar*rozmiar*3) || ile == (rozmiar*rozmiar*3)+1){
for(i=0;i< rozmiar;i++)
for(j=0;j< rozmiar;j++)
_file >> A(i,j);
for(i=0;i< rozmiar;i++)
for(j=0;j< rozmiar;j++)
_file >> B(i,j);
for(i=0;i< rozmiar;i++)
for(j=0;j< rozmiar;j++)
_file >> C(i,j);
WypiszMacierze();
return 3;
}
else
return 0;
}
W pierwszym wierszu funkcji przy pomocy instrukcji while zliczane są wszystkie znaki w pliku. Działanie to ma na celu ustalenie ile macierzy z danymi znajduje się w pliku. Prawidłowo zdefiniowany problem posiada dwie lub trzy macierze. Program wychodzi z pętli po napotkaniu znaku końca pliku. W drugim wierszu funkcji wskaźnik plikowy ustawiany jest na początek pliku. Następnie odczytywana jest pierwsza liczba z pliku czyli rozmiar problemu. Jest to informacja niepotrzebna w tej funkcji i nie jest wykorzystywana. Pobieranie danych zaczyna się od drugiej liczby. W zależności od ilości zliczonych liczb w pliku, czyli od wartości zmiennej ile , odczytywane są kolejno liczby i wpisywane jako kolejne elementy prywatnych obiektów A,B,C. W zależności od ilości zdefiniowanych macierzy w pliku funkcja zwraca ilość odczytanych macierzy.
Funkcja AlgorytmStartowy(String) ma za zadanie utworzyć rozwiązanie startowe tzn. wektor rozwiązania startowego. W zależności od przekazanego parametru do funkcji, rozwiązanie startowe generowane jest za pomocą jednego z trzech dostępnych algorytmów.
bool QAP::AlgorytmStartowy(String _alg)
{
AlgorytmSt = _alg;
if(_alg == "losowy"){
int i,k,m;
int niestety;
bool nieroznisie;
bool nowelosowanie;
int los, nowylos;
for(i = 0; i < rozmiar; i++){
los = losuj(rozmiar);
if(i == 0)
P(0) = los;
else{
for(k = 0; k < i; k++){
if(P(k) == los){
nowelosowanie = true;
nieroznisie = true;
while(nieroznisie){
niestety = 0;
nowylos = losuj(rozmiar);
for(m = 0; m < i; m++){
if(P(m) == nowylos)
niestety++;
}
if(niestety == 0)
nieroznisie = false;
}
P(i) = nowylos;
}
}
if(!nowelosowanie) P(i) = los;
P(i) = los;
else
nowelosowanie = false;
}
}
}
Gdy parametrem funkcji jest ciąg znaków losowy rozwiązanie startowe generowane jest na podstawie losowania kolejnych elementów wektora. Algorytm działa w ten sposób, że losuje liczbę, jeśli jest to pierwsza wylosowana liczba to wpisuje ją jako pierwszy element wektora rozwiązania startowego. Jeśli jest to kolejna wylosowana liczba, algorytm sprawdza, czy wcześniej nie wylosowano już takiej liczby. Jeśli wektor zawiera już taki element, następuje nowe losowanie do momentu uzyskania liczby różniącej się od wszystkich wylosowanych dotąd elementów wektora.
Jeśli parametrem algorytmu jest ciąg znaków algorytm 1 rozwiązanie startowe generowane jest na podstawie metody szeregowania listowego opisanej w punkcie 1.2.2. Poniżej zamieszczono dalszy ciąg funkcji AlgorytmStartowy(String).
else if(_alg == "algorytm 1"){
Para *rA = new Para[rozmiar];
Para *rB = new Para[rozmiar];
int k,l;
for(k = 0; k < rozmiar; k++){
rA[k].i = 0;
rA[k].j = k;
rB[k].i = 0;
rB[k].j = k;
for(l = 0; l < rozmiar ; l++){
rA[k].i += A(k,l);
rB[k].i += B(k,l);
}
}
qsort((void*)rA,(size_t)rozmiar,(size_t)sizeof(Para),PorownajPary);
qsort((void*)rB,(size_t)rozmiar,(size_t)sizeof(Para),PorownajPary);
for(k = 0; k < rozmiar; k++)
P(rA[k].j) = rB[rozmiar-k-1].j;
delete[] rA;
delete[] rB;
}
W dwóch pierwszych wierszach przydzielana jest dynamicznie pamięć dla tablicy struktur typu Para i adres obszaru przydzielonej pamięci wpisany jest pod zmienne wskaźnikowe rA i rB. Każda para zawiera dwa pola. W tym przypadku pierwsze pole i pary rA wykorzystane zostało do przechowania sumy elementów w poszczególnych wierszach, drugie pole oznacza numer wiersza. Dwie pierwsze pętle for realizują sumowanie elementów w wierszach. Następnie przy pomocy funkcji qsort z biblioteki standardowej Stdlib systemu BilderC++ powstałe sumy sortowane są w kolejności rosnącej.
Ostatnia pętla for generuje wektor rozwišzania startowego w taki sposób, że minimalna wartość pola i pary rA przypisywana jest maksymalnej wartości pola i pary rB. Powoduje to uśrednienie wartości funkcji celu, a tym samym szybsze znalezienie rozwiązania optymalnego. W tej samej pętli zwalniana jest pamięć dla tablic struktur rA i rB.
Jeżeli parametrem funkcji jest ciąg znaków algorytm 2 wtedy wektor rozwiązania startowego generowany jest na podstawie algorytmu przedstawionego poniżej.
else if(_alg == "algorytm 2"){
Para *cA = new Para[rozmiar];
Para *cB = new Para[rozmiar];
int k,l;
for(k = 0; k < rozmiar; k++){
cA[k].i = 0;
cA[k].j = k;
cB[k].i = 0;
cB[k].j = k;
for(l = 0; l < rozmiar ; l++){
cA[k].i += A(l,k);
cB[k].i += B(l,k);
}
}
qsort((void*)cA,(size_t)rozmiar,(size_t)sizeof(Para),PorownajPary);
qsort((void*)cB,(size_t)rozmiar,(size_t)sizeof(Para),PorownajPary);
for(k = 0; k < rozmiar; k++)
P(cA[k].j) = cB[rozmiar-k-1].j;
delete[] cA;
delete[] cB;
}
return true;
Powyższy algorytm różni się od algorytmu przedstawionego na listingu 31 jedynie tym, że zlicza sumy elementów poszczególnych kolumn macierzy A i B, a nie wierszy. Jeśli macierze są symetryczne, wektor rozwiązania startowego wygenerowanego na podstawie algorytmu 1 jest taki sam jak wektor utworzony przez algorytm 2.
Funkcja WypiszMacierze() wywoływana jest wewnątrz funkcji WczytajMacierze() i ma za zadanie wyświetlić macierze A, B, i C na odpowiednich stronach komponentu PageControl. Na początku funkcja ustala właściwości stron - komponentów StringGrid: ColCount ustala ilość kolumn (wartość jest większa od rozmiaru problemu o jedną kolumnę ponieważ pierwsza kolumna zawiera poszczególne numery wierszy), RowCount ustala ilość wierszy (wartość jest większa od rozmiaru problemu ponieważ pierwszy wiersz zawiera numery poszczególnych kolumn), Cells[0][0] jest elementem lewego górnego rogu komponentu StringGrid i zawiera nazwę macierzy. Następnie są numerowane wiersze i kolumny macierzy, oraz pod poszczególne elementy Cells[i][j] komponentów StringGrid wpisywane są wartości macierzy A, B i C.
void QAP::WypiszMacierze(void)
{
MainForm->StringGridMacierzA->ColCount = rozmiar + 1;
MainForm->StringGridMacierzB->ColCount = rozmiar + 1;
MainForm->StringGridMacierzC->ColCount = rozmiar + 1;
MainForm->StringGridMacierzA->RowCount = rozmiar + 1;
MainForm->StringGridMacierzB->RowCount = rozmiar + 1;
MainForm->StringGridMacierzC->RowCount = rozmiar + 1;
MainForm->StringGridMacierzA->Cells[0][0] = "A";
MainForm->StringGridMacierzB->Cells[0][0] = "B";
MainForm->StringGridMacierzC->Cells[0][0] = "C";
for(int i=1; i< rozmiar+2; i++){
MainForm->StringGridMacierzA->Cells[0][i] = i;
MainForm->StringGridMacierzA->Cells[i][0] = i;
}
for(int i=1; i< rozmiar+2; i++){
MainForm->StringGridMacierzB->Cells[0][i] = i;
MainForm->StringGridMacierzB->Cells[i][0] = i;
}
for(int i=1; i< rozmiar+2; i++){
MainForm->StringGridMacierzC->Cells[0][i] = i;
MainForm->StringGridMacierzC->Cells[i][0] = i;
}
for(int i=0;i< rozmiar;i++)
for(int j=0;j< rozmiar;j++)
MainForm->StringGridMacierzA->Cells[j+1][i+1] = A(i,j);
for(int i=0;i< rozmiar;i++)
for(int j=0;j< rozmiar;j++)
MainForm->StringGridMacierzB->Cells[j+1][i+1] = B(i,j);
for(int i=0;i< rozmiar;i++)
for(int j=0;j< rozmiar;j++)
MainForm->StringGridMacierzC->Cells[j+1][i+1] = C(i,j);
}
Funkcja Permutacja(Para &p) ma za zadanie przestawić dwa elementy (przekazane jako parametr) w wektorze rozwiązania P. Funkcja posiada jedną zmienną lokalną służącą do zapamiętania jednego elementu pary przekazanej jako parametr. Jest to konieczne do prawidłowej zamiany dwóch elementów.
void QAP::Permutacja(Para &p)
{
int temp;
temp = P(p.i);
P(p.i) = P(p.j);
P(p.j) = temp;
};
Funkcja Q() liczy wartość funkcji celu. Poniżej przedstawiono jej strukturę.
double QAP::Q(void)
{
double Suma1=0, Suma2=0;
int i,k;
for(i=0;i< rozmiar;i++){
Suma1 += C(i,P(i));
}
for(i=0;i< rozmiar;i++){
for(k=0;k< rozmiar;k++){
Suma2 += A(i,k) * B(P(i),P(k));
}
}
return (Suma1 + Suma2);
};
Powyższa funkcja deklaruje dwie zmienne lokalne typu double, które przechowują wartości sum pomocniczych funkcji celu. Pierwsza zawiera sumę zliczonš na podstawie dodawania odpowiednich elementów macierzy C, druga zawiera sumę zliczoną na podstawie dodawania poszczególnych iloczynów elementów macierzy A i B. Funkcja zawiera jeszcze dwie zmienne lokalne typu całkowitego służące jako indeksy w pętli for.
Klasa QAP zawiera jeszcze różne funkcje dostępu do jej pól prywatnych. Umożliwiają one zapis nowych wartości z zewnątrz lub odczyt aktualnych wartości poszczególnych pól. Przykładem może być funkcja ZwrocRozmiar(), która zwraca wartość prywatnej zmiennej rozmiar.
int QAP::ZwrocRozmiar(void)
{
return rozmiar;
};
2.5.4. Klasa TS.
Klasa TS została stworzona w celu konstrukcji obiektów, które mają za zadanie wykonać jak i przechowywać dane o algorytmie Tabu Search. Klasa posiada 11 pól prywatnych, dwa typu całkowitego: K przechowuje ilość iteracji, T przechowuje wartość okresu karencji (zablokowania) dla danej pary; jedno pole typu zmiennoprzecinkowego alfa przechowuje wartość parametru będącego karą za częste dokonywanie przestawień pary; obiekt LT klasy Tablica będący listą tabu dla algorytmu Tabu Search; wskaźnik Problem typu QAP przechowujący adres obiektu, w którym zdefiniowano problem QAP; dwa obiekty PImin, PIst klasy Wektor przechowujące wektory startowy i minimalny; dwie zmienne Qst, Qmin typu double przechowujące wartości funkcji celu startową i minimalną; obiekt NazwaPliku klasy AnsiString przechowujący nazwę pliku do zapisania wartości funkcji celu; obiekt Plik klasy ofstream zapewniający operację zapisania do pliku.
class TS
{
int K;
int T;
float alfa;
Tablica LT;
QAP* Problem;
Wektor PIst;
Wektor PImin;
double Qst, Qmin;
AnsiString NazwaPliku;
ofstream Plik;
public:
TS(QAP*);
void UstalProblem();
void NoweK(int);
void NoweT(int);
void NoweAlfa(float);
double ZwrocQmin(void);
double ZwrocQst(void);
int ZwrocK(void);
int ZwrocT(void);
float ZwrocAlfa(void);
Wektor& ZwrocPImin(void);
Wektor& ZwrocPIst(void);
String ZwrocNazwePliku(void);
bool AlgorytmTS(void);
}
Klasa posiada jeden konstruktor z parametrem, w którym przekazywany jest adres obiektu, gdzie zdefiniowano problem QAP. Funkcja UstalProblem() ma za zadanie, zainicjować trzy pola prywatne klasy TS. Poniżej przedstawiono jej budowę.
void TS::UstalProblem(void)
{
PIst = Problem->ZwrocPI();
Qst = Problem->Q();
Qmin = Qst;
}
Obiekt prywatny PIst inicjowany jest wektorem rozwiązania startowego otrzymanego z obiektu QAP poprzez publiczną funkcję ZwrocPI() klasy QAP. Zmienna prywatna Qst inicjowana jest wartością funkcji celu obliczoną za pomocą publicznej funkcji Q() dostępnej w klasie QAP. Zmienna prywatna Qmin inicjowana jest wartością zmiennej Qst, ponieważ na początku wartość minimalna funkcji celu jest wartością startową.
Funkcja AlgorytmTS() ma za zadanie wyznaczyć najlepsze rozwiązanie problemu zdefiniowanego w obiekcie QAP, przy pomocy algorytmu Tabu Search.
bool TS::AlgorytmTS(void)
{
int k;
bool NoweQprim;
bool NoweQprimodQmin;
Para gwiazdka;
Para prim;
Para loop;
double Qprim;
double Qakt;
double Qgwiazdka;
int rozmiar = Problem->ZwrocRozmiar();
MainForm->ProgressBar->Max = K;
NazwaPliku = "Q" + IntToStr(ileTS) + ".dat";
Plik.open(NazwaPliku.c_str());
Plik << Qst << " \n";
ileTS++;
Pierwsza część funkcji przedstawiona została powyżej. Deklarowane są jedna zmienna typu całkowitego k zawierająca numer bieżącej iteracji, dwie zmienne typu bool: NoweQprim przyjmująca wartość true gdy znaleziona aktualna wartość funkcji celu jest wyznaczona na podstawie formuły Qprim; NoweQminodQprim() przyjmująca wartość true gdy znaleziono nową minimalną wartość funkcji celu Qmin na podstawie formuły Qprim; trzy struktury gwiazdka, prim, loop typu Para do pamiętania pary przestawionych elementów tzn. gwiazdka pamięta parę elementów, po których przestawieniu wystąpiło polepszenie wartości funkcji celu obliczonej przy pomocy formuły Qgwiazdka, prim pamięta parę elementów, po których przestawieniu wystąpiło polepszenie wartości funkcji celu obliczonej przy pomocy formuły Qprim, loop służy jako para pomocnicza wykorzystywana w pętlach for. W dalszej części deklarowane są trzy zmienne lokalne typu double, do pamiętania wartości funkcji celu Qakt, Qprim, Qqwiazdka. Następnie deklarowana jest zmienna typu całkowitego rozmiar inicjowana wartością rozmiaru problemu z obiektu QAP. Następnie maksymalna wartość wskaźnika postępu ustawiana jest na wartość jaką posiada zmienna K. W kolejnym wierszu tworzona jest nazwa pliku z następnym numerem otrzymanym ze zmiennej globalnej ileTS oraz otwierany jest plik o tej nazwie do zapisu, gdzie zapisana zostaje wartość funkcji celu startowa, oraz zwiększony zostaje licznik wywołań algorytmu.
for(k=1; k<(K+1); k++){ <-- początek pętli głównej
MainForm->ProgressBar->Position = k;
MainForm->Wykres->DataPoint(clRed,(Longint)Qmin);
MainForm->Wykres->Update();
MainForm->LabelQmin->Caption = FloatToStr((float)Qmin);
MainForm->LabelQmin->Repaint();
W dalszej części uruchamiany jest algorytm, który działa w pętli for. Ilość iteracji jest równa wartości zmiennej K. Pierwsze pięć wierszy pętli odpowiedzialne jest za wizualizację procesu poszukiwania rozwiązania, na stronie TabSheetTS komponentu PageControl. Zmieniana jest wartość wskaźnika postępu na wartość przechowywaną w zmiennej k, następnie kreślona jest wartość funkcji celu w oknie grafu, oraz wyświetlana za pomocą etykiety LabelQmin.
Qprim = Problem->Q();
Qgwiazdka=((float)Qprim)+alfa*((float)(LT(loop.j,loop.i)))/((float)k);
for(loop.i=0, plum=0; loop.i<(rozmiar-1);loop.i++)
for(loop.j=loop.i+1; loop.j< rozmiar; loop.j++){
Problem->Permutacja(loop);
Qakt = Problem->Q();
if(LT(loop.i,loop.j) > 0 && Qakt < Qprim){
Qprim = Qakt;
prim = loop;
NoweQprim = true;
}
else if(LT(loop.i,loop.j) == 0 &&
(((float)Qakt)+alfa*((float)LT(loop.j,loop.i))/((float)k)) < Qgwiazdka){
Qgwiazdka = ((float)Qakt)+alfa*((float)LT(loop.j,loop.i))/((float)k);
gwiazdka = loop;
}
else
;
Problem->Permutacja(loop);
}
}
Pierwsza część algorytmu zgodnie z jego strukturą opisaną w punkcie 1.3 pracy dotyczy wyznaczenia najlepszego rozwiązania w otoczeniu. Realizuje to część algorytmu zamieszczona na listingu 43. Zmienna Qprim inicjowana jest wartością funkcji celu. Zmienna Qgwiazdka taką samą wartością, gdyż w pierwszej iteracji każdy element listy tabu ma wartość zero, więc wartość drugiego członu wzoru jest równa zero. Następne działania odbywają się w dwóch pętlach for, które mają za zadanie przestawić parami wszystkie elementy wektora rozwiązania za pomocą funkcji Permutacja() i po każdym przestawieniu obliczać aktualną wartość funkcji celu za pomocą funkcji Q() obiektu klasy QAP. Następnie sprawdzane są dwa warunki określone w kroku 2 algorytmu opisanym w punkcie 1.3, a realizowane przez pętlę if / else if. Jeśli nastąpiła poprawa wartości funkcji celu to zapamiętywana jest para elementów, po przestawieniu których nastąpiło polepszenie wartości funkcji celu. Jeśli nastąpiło polepszenie wartości funkcji celu Qgwiazdka, to pamiętana jest para gwiazdka, jeśli nastąpiła poprawa wartości Qprim to pamiętana jest para prim. Na koniec każdej iteracji elementy przestawione wracają na swoją pozycję początkową. Poniżej przedstawiono dalszą część algorytmu (krok 3), w którym następuje poprawa rozwiązań.
Problem->Permutacja(gwiazdka);
Qakt = Problem->Q();
if(Qmin > Qakt){
Qmin = Qakt;
PImin = Problem->ZwrocPI();
}
Problem->Permutacja(gwiazdka);
NoweQminodQprim = false;
if(NoweQprim){
Problem->Permutacja(prim);
Qakt = Problem->Q();
if(Qmin > Qakt){
PImin = Problem->ZwrocPI();
Qmin = Qakt;
NoweQminodQprim = true;
}
Problem->Permutacja(prim);
}
Za pomocą funkcji Permutacja() przestawiane są dwa elementy pamiętane w zmiennej gwiazdka. Następnie obliczana jest wartość funkcji celu i jeśli jest lepsza od obecnej wartości minimalnej to zapamiętany zostaje wektor rozwiązania w zmiennej PImin . Następnie przestawione elementy wracają na swoją pozycję. Jeśli wystąpiła zmiana wartości funkcji celu Qprim to obliczona zostaje aktualna wartość funkcji celu po przestawieniu elementów pamiętanych w zmiennej prim i jeśli jest lepsza od obecnej wartości Qmin zostaje zapamiętany nowy wektor rozwiązania w zmiennej PImin. Następnie przestawione elementy wracają na swoją pozycję. Poniżej znajduje się ostatnia część algorytmu, w której następuje korekta stanu pamięci, czyli uaktualnienie zawartości listy tabu.
for(loop.i=0;loop.i<(rozmiar-1);loop.i++)
for(loop.j=loop.i+1;loop.j< rozmiar;loop.j++)
LT(loop.i,loop.j) = max(0,LT(loop.i,loop.j) - 1);
if(NoweQminodQprim){
LT(prim.i,prim.j) = T;
Problem->Permutacja(prim);
++(LT(prim.j,prim.i));
loop = prim;
}
else{
LT(gwiazdka.i,gwiazdka.j) = T;
Problem->Permutacja(gwiazdka);
++(LT(gwiazdka.j,gwiazdka.i));
loop = gwiazdka;
}
Plik << Qmin << " \n";
} <-- koniec pętli głównej
Plik.close();
MainForm->ProgressBar->Position = 0;
return true;
}
Za pomocą dwóch pętli for przeszukiwana jest górna część listy tabu i wartość każdego elementu górnej listy tabu większego od zera jest zmniejszana o jeden. Tzn. okres zablokowania dla danej pary w każdej iteracji jest zmniejszany o jeden. Następnie za pomocš instrukcji if else dokonywana jest dalsza korekta listy tabu. Jeśli poprawa rozwiązań nastąpiła na skutek przestawienia pary elementów prim (instrukcja if) to pozycja na górnej liście tabu dla tych elementów jest inicjowana wartością parametru T, jest to okres karencji dla danej pary, który jest wprowadzany za pomocą pola edycyjnego umieszczonego na stronie TabSheetTS; przestawiane są dwa elementy w wektorze rozwiązania za pomocą funkcji Permutacja() obiektu klasy QAP; zwiększana jest o jeden wartość dolnej listy tabu dla elementów pary prim, tzn. licznik wystąpienia danej pary zwiększany jest o jeden. Jeśli poprawa rozwiązania nastąpiła na skutek przestawienia elementów pary gwiazdka to wykonywane są opisane powyżej operacje jednak dla pary gwiazdka (instrukcja else). Ostatnia instrukcja w głównej pętli algorytmu zapisuje aktualną wartość funkcji celu do pliku. Gdy licznik w głównej pętli for osiągnie wartość K , wykonywanie instrukcji w pętli zostaje zakończone i tym samym jest to koniec algorytmu Tabu Search. Funkcja AlgorytmTS() w trzech ostatnich wierszach zamyka plik do zapisu, ustawia wskaźnik postępu ajgorytmu na wartość zero, i zwraca wartość logiczną true.
2.5.5. Struktura Para.
Struktura Para została stworzona w celu pamiętania dwóch elementów typu całkowitego. Posiada dwa publiczne pola i oraz j, funkcję konstruującą nowy obiekt struktury Para i inicjującą jej pola wartościami zero, przeciążony operator przypisania, który zapewnia prawidłowe przypisanie jednej struktury typu Para do drugiej, struktura posiada również funkcję zaprzyjaźnioną PorownajPary(), która jest wykorzystywana przez funkcję qsort() do sortowania tablicy struktur typu Para w funkcji AlgorytmStartowy() klasy QAP.
struct Para
{
int i,j;
Para(void):i(0),j(0){}
Para& operator=(Para &P)
{
this->i = P.i;
this->j = P.j;
return *this;
}
protected:
friend int PorownajPary(const void *, const void *);
}
Funkcja PorownajPary() porównuje dwie struktury typu Para według pola i struktur. Zwraca wartość dodatnią jeśli struktura przekazana w pierwszym parametrze do funkcji posiada większą wartość w polu i od struktury przekazanej w drugim parametrze lub funkcja zwraca wartość ujemną jeśli pole i struktury przekazanej w pierwszym parametrze ma wartość mniejszą od pola i struktury przekazanej przez drugi parametr do funkcji.
int PorownajPary(const void *arg1, const void *arg2)
{
return (((Para*)arg1)->i)-(((Para*)arg2)->i);
}
3. Badanie problemów QAP
Poniżej przedstawiono proces badania problemów QAP przy pomocy algorytmu Tabu Search.
Standardowe problemy zdefiniowane w plikach dostępnych w sieci Internet wczytywano kolejno do napisanego programu.
Dla każdego problemu wykonywano wiele serii prób, zmieniając wartości parametrów K, T i Alfa oraz Algorytmy Startowe.
Stworzone narzędzie zaprojektowano w taki sposób, aby po naciśnięciu jednego przycisku na pasku narzędziowym wyniki można było otrzymać w czytelnej formie w tabeli, zawierającej zarówno znalezioną
minimalną wartość funkcji celu, jak też parametry wywołania algorytmu oraz zdefiniowany badany problem QAP. Każdy wpis w tabeli przedstawia kolejne przeprowadzone badanie - nowe wywołanie procedury Tabu Search.
4. Wnioski
Przebadano wiele standardowych problemów danych w plikach z rozszerzeniem ".dat". W procesie poszukiwania najlepszego rozwiązania zmieniano wartości parametru T oraz parametru Alfa.
Rozwiązanie startowe generowano na podstawie trzech różnych algorytmów w tym jeden losowy i dwa uśredniające początkową wartość funkcji celu zbudowane na zasadzie procedury BEST-MATCH.
Zmieniano również ilość iteracji.
Poniżej przedstawiono przebieg wartości funkcji celu w procesie poszukiwania najlepszego rozwiązania problemu Sko42 o rozmiarze 42. Na wykresie przedstawiono cztery przebiegi funkcji celu dla różnych wartości parametru T (okres karencji dla przestawionej pary elementów), odpowiednio T = 25, 15, 10, 5.
Parametry K=250 i Alfa=3000 pozostawały niezmienione.
Jak widać z powyższego wykresu zmiana parametru T ma wpływ na przebieg poszukiwania rozwiązania w problemie Kwadratowego Zagadnienia Przydziału za pomocą algorytmu Tabu Search. Dla T = 25 minimalna wartość funkcji celu wynosi 16036, dla T = 15 znaleziona wartość funkcji celu dla najlepszego rozwiązania wynosi 15576, dla T = 10 Qmin = 16048, dla T = 5 Qmin = 16008.
Jak widać parametr ten służy do różnicowania procesu poszukiwania najlepszego rozwiązania w algorytmie Tabu search. Drugim parametrem, który zmieniano podczas testowania algorytmu był parametr Alfa. Na poniższym wykresie przedstawiono przebiegi wartości funkcji celu dla różnych wartości parametru Alfa.
Parametr Alfa jest karą za częste dokonywanie przestawienia pary elemntów w procesie poszukiwania najlepszego rozwiązania. Z powyższego wykresu zauważono, że gdy kara jest mała algorytm szybko zmierza do pewnego minimum, lecz nie jest to rozwiązanie zadowalające. Gdy zwiększono karę do 1500 stwierzono, że algorytm wolniej zmierza do minimum, przy czym w tym przypadku znalezione rozwiązanie jest lepsze niż gdy kara wynosiła 500.
Dalej zwiększając karę zaobserwowano podobny efekt powolnego zmierzania do minimum. W ostatnim przypadku gdy kara wynosi 3000 przyjęto zdecydowanie zbyt małą ilość iteracji. Najlepsze rozwiązanie znaleziono dla kary równej 1500. Dla wszystkich przypadków okres karencji dla danej pary wynosił 5.
Wykonano wiele serii prób dla wielu problemów Kwadratowego Zagadnienia Przydziału zdefiniowanego w postaci macierzy. Napisany program w środowisku Bilder C++ działa poprawnie, a zaimplementowany algorytm Tabu Search minimalizuje wartość funkcji celu i znajduje przybliżone rozwiązanie w zależności od wprowadzonych parametrów K, T oraz Alfa.
Aby znaleźć optymalne rozwiązanie danego problemu należy wykonać wiele serii prób zmieniając wartości parametrów algorytmu doświadczalnie, gdyż każdy problem wymaga innych wartości parametrów dla znalezienia najlepszego rozwiązania.
5. Bibliografia
[1]. Burkard R.E. Offerman J. Entwurf von Schreibmaschinen tastatwen mittels quadratischer Zuordnungsprobleme. Band 21, 1977.
[2]. Christofides, Mingozzi, Toth. Contribution to the Qadratic Assignment Problem. European Journal of Operational Research 4, 1980.
[3]. Elshafei A.N. Hospital Layout as a Quadratic Assignment Problem. Discrete Appl. Maths 5, 1983.
[4]. Garett J. Plyter N.V The Optimal Assignment of Facilities to Location by Branch and Bound. Operations Resarch, vol.28, 1977.
[5]. Koopmans T.C. Beckman M. Assignment Problem and the Location of Economic Activities. Econometica, vol.25, 1957.
[6]. Land A.M. A Problem of Assignment with Interpelated Costs. Operational Resarch Quarterly, vol.14, 1963.
[7]. Lawler E.L The Quadratic Assignment Problem. Management Science, vol.9
[8]. Pierce J.F. Crowston W.B. Tree Search Algorithm of Quadratic Assignment Problems. Naval Research Logistics Quarterly, vol.18
[9]. Roucairol C. Un nouvel algorithme pour le probleme d'affectation quadratique. RAIRO, vol.13, 1979.
[10]. Steinberg L. The Backaboard Wiring Problem: A Placement Algorithm. Siam Review, vol.3, 1961.
[11]. Wala K. Badania Operacyjne. Wykłady, 1997-1999.