Autor

Marek Langiewicz
nr indeksu: 130008

Opis problemu

Stosując algorytm zachłanny, wyznaczyć pewna drogę komiwojażera.

Algorytm

Zastosowałem zwykły algorytm zachłanny. Algorytm rekurencyjnie szuka najdłuższej ścieżki i jeśli nie może już iść głębiej, a ścieżka jest krótsza niż ilość wierzchołków grafu, to cofa się rekurencyjnie do ostatniego rozwidlenia. Przyjąłem że krawędzie grafu nie mają wag (kosztów). Jeśli powinny mieć, to mogę to poprawić. Wtedy algorytm szedłby zawsze najpierw najtańszą drogą.

Informacje o implementacji

Użycie programu

Możemy podać programowi jako parametr nazwę pliku z danymi wejściowymi, albo jeśli nie podamy, to program będzie czytać dane ze standartowego wejścia. Przykładowe dane wejściowe są w plikach przyklad1.in przyklad2.in (wierzchołki startowe są również zapisane w tych plikach - na końcu) więc możemy napisać:
./dluga_sciezka przyklad2.in
albo:
./dluga_sciezka < przyklad2.in
i program będzie w trakcie działania wypisywać odwiedzane wierzchołki; na końcu program wypisze czy znalazł drogę komiwojażera, czy nie.

Format danych wejściowych

Kompilacja programu

Program kompilujemy poleceniem make (wydanym w katalogu programu). Potrzebny jest GNU Make. Można też skompilować pod M$ Windowsem używając albo MinGW albo Cygwin - one mają GNU Make i GCC. Trzeba mieć też zainstalowaną bibliotekę WX Widgets. A po co ten wxWidgets? Używam z tego dynamicznych tablic do zapamiętywania sąsiadów każdego wierzchołka. Tam są napisane szybkie tablice i dynamiczne (w sensie: można zmieniać ich rozmiar) i bezpieczne (w sensie: w trybie 'debug' sprawdzają czy nie odwołują się do elementów poza tablicą). Są szybsze i prostsze w obsłudze od standartowych tablic C++ (czyli od vector z Standard Template Library). Poza tym te tablice są oparte na makrach a nie szablonach, więc można je kompilować praktycznie dowolnym kompilatorem C++. Biblioteka wxWidgets jest darmowa i open-source i crossplatformowa.

Pliki programu

komiwojazer
Skompilowany program (pod linuxa). Jesli podamy plik jako parametr (np. przyklad1.in) to pobierze dane wejsciowe z podanego pliku. A jak nie podamy to pobierze dane ze standartowego wejscia. Format danych wejsciowych jest podany wyżej.
komiwojazer.cpp
Główny plik źródłowy programu. Zawiera funkcję main i parę innych pomocniczych i rekurencyjną funkcję Komiwojazer która to właśnie szuka drogi komiwojażera od podanego wierzchołka. Szczegły są w komentarzach w pliku komiwojazer.h.
komiwojazer.h
Plik nagłówkowy dla pliku komiwojazer.cpp . Zawiera komentarze.
Graph.cpp
Plik źródłowy z definicjami metod klas CGraph i CVertex. Właściwie w tej chwili zawiera tylko funkcję CVertex::isolate bo reszta jest inline w pliku Graph.h.
Graph.h
Plik definiujący klasy CVertex i CGraph reprezentujące odpowiednio wierzchołek i graf. Szczegły w komentarzach w pliku Graph.h.
Makefile
Plik dla programu GNU Make definiujący co ma być skompilowane i jak po wpisaniu polecenia make będąc w katalogu programu.
przyklad1.in przyklad2.in
Pliki zawierające przykładowe dane wejściowe dla programu. Zawierają grafy i na końcu numery wierzchołków startowych. Ten przykładowe grafy narysowałem sobie w programie Open Office Draw i można je zobaczyć otwierając pliki: przyklad1.sxd przyklad2.sxd albo pliki: przyklad1.pdf przyklad2.pdf.
przyklad1.pdf przyklad2.pdf
Przykładowe grafy wyeksportowane do plików PDF.
przyklad1.sxd przyklad2.sxd
Przykładowe grafy narysowane w programie Open Office Draw.
przyklad1.out przyklad2.out
Wyniki działania algorytmu dla danych wejściowych: przyklad1.in przyklad2.in
README.html
To TEN plik. Czyli dokumentacja programu.