Marek Langiewicz
nr indeksu: 130008
Stosując algorytm zachłanny, wyznaczyć pewna drogę komiwojażera.
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ą.
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.
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.