HLP POSL, wisisz, wydzial informatyki, studia zaoczne inzynierskie, badania operacyjne, lab3
[ Pobierz całość w formacie PDF ]
Program MODGRAF służy do rozwišzywania problemów decyzyjnych za pomocš modeli i algorytmów grafowych bšd sieciowych.TYPOWY PROCES MODELOWANIA I ROZWIĽZYWANIA PROBLEMU:===================================================1) Zdefiniowanie grafu w postaci pliku tekstowego ("Plik/Nowy graf") lub wczytanie grafu z istniejšcego pliku ("Plik/Wczytaj graf").2) Po wczytaniu pliku ze zdefiniowanym grafem może wystšpić jedna z trzech sytuacji:* Graf wczytuje się poprawnie i w głównym oknie pojawia się jego graficzna reprezentacja. W zależnoci od potrzeb poszczególne wierzchołki grafu można wtedy przesuwać za pomocš przecišgania myszš z wciniętym jej lewym klawiszem. Przesunięcie całego grafu realizowane jest podobnie, ale z wciniętym klawiszem Shift. Zmienione rozmieszczenie wierzchołków grafu może zostać dopisane do pliku wejciowego i zapamiętane poprzez wybranie z menu "Plik" pozycji "Zachowaj topologię jako".* Graf wczytuje się poprawnie, ale pojawia się komunikat informujšcy, że graf nie będzie wywietlany. Następuje to w przypadku wczytywania dużych grafów. Ich pełna reprezentacja graficzna jest wtedy niemożliwa, a w głównym oknie wywietlona jest tylko zastępcza winieta, która informuje o parametrach wczytanego grafu. Pomimo braku reprezentacji graficznej wszystkie algorytmy i operacje na grafie sš dostępne.* Pojawia się komunikat o błędzie i numer linii, w której zidentyfikowano błšd. W takim przypadku należy poprawić opis grafu w pliku tekstowym, wybierajšc z menu "Plik" pozycję "Edytuj graf".3) Wybranie odpowiedniego algorytmu (patrz opis poniżej) spowoduje rozwišzanie problemu i wywietlenie wyniku, skšd może on zostać zapisany w osobnym pliku. W większoci przypadków rozwišzanie zobrazowane jest także w postaci reprezentacji graficznej.ZESTAW DOSTĘPNYCH OPCJI PROGRAMU:====================================[Plik] - OPERACJE NA PLIKACH{Nowy graf}Otwiera okno edycyjne, pozwalajšce zdefiniować graf w postaci pliku tekstowego (patrz "Format pliku wejciowego").{Wczytaj graf}Wczytuje graf z wczeniej zapisanego pliku, utworzonego za pomocš opcji "Plik/Nowy graf" lub zewnętrznego edytora tekstowego.{Edytuj graf}Otwiera okno edycyjne, zawierajšce opis aktualnie wczytanego grafu, pozwalajšc na zmodyfikowanie jego postaci.{Zachowaj topologię jako}Pozwala na zapisanie w pliku akualnego położenia wierzchołków grafu na ekranie.{Koniec}Wyjcie z programu.------------------------------------[Trasy] - ALGORYTMY WYZNACZANIA TRAS{Drzewo rozpinajšce}Algorytm znajduje podgraf analizowanego grafu, który jest drzewem zawierajšcym wszystkie jego wierzchołki i suma wag krawędzi jest najmniejsza (minimalne drzewo rozpinajšce) lub największa (maksymalne drzewo rozpinajšce). Algorytmy wymagajš grafu nieskierowanego.Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - reprezentujšcy wagę krawędzi.{Najkrótsze drogi - Alg. Dijkstry}Algorytm znajduje najkrótsze drogi z podanego wierzchołka do wszystkich pozostałych wierzchołków grafu.Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - wagę krawędzi. Wagi krawędzi muszš być nieujemne.{Najkrótsze drogi - Alg. Floyda}Algorytm znajduje najkrótsze drogi pomiędzy wszystkimi parami wierzchołków. Jako wynik powstaje tablica odległoci pomiędzy wierzchołkami.Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - wagę krawędzi.{Komiwojażer}Problem komiwojażera polega na znalezieniu w grafie cyklu, który przechodziłby przez każdy jego wierzchołek dokładnie raz, a suma wag poszczególnych krawędzi cyklu była najmniejsza z możliwych. Algorytmy Near i FI znajdujš pewne zgrubne przybliżenie rozwišzania o najmniejszej sumie wag i mogš zostać poprawione poprzez zastosowanie dodatkowych heurystyk poprawy: 2Opt i 3Opt. Istota algorytmu 2Opt nie pozwala na zastosowanie go do grafu skierowanego. Algorytm dokładny znajduje optymalne rozwišzanie problemu komiwojażera, zarówno dla grafów skierowanych, jak i nieskierowanych. Możliwoć znalezienia rozwišzania dokładnego okupiona jest jednak znacznym wydłużeniem czasu obliczeń.Krawędzie grafu powinny mieć zdefiniowany jeden parametr - wagę krawędzi.{Cykl Eulera}Algorytm znajduje taki cykl w grafie, w którym każda krawęd (łuk) występuje dokładnie raz. Po wykonaniu algorytmu kolejnoć przechodzenia krawędzi zaznaczona jest numerami.Krawędzie grafu nie muszš mieć podanych żadnych parametrów liczbowych.------------------------------------[Przepływy] - ALGORYMY WYZNACZANIA PRZEPŁYWÓW W SIECIACH{Maksymalny przepływ}Algorytm wyznacza maksymalny przepływ pomiędzy podanš parš wierzchołków.Krawędzie grafu powinny mieć okrelony jeden parametr - przepustowoć krawędzi (łuku).{Najtańszy przepływ}Algorytm wyznacza najtańszy przepływ o zadanej wielkoci pomiędzy podanš parš wierzchołków.Krawędzie grafu powinny mieć dwa parametry. Pierwszy parametr oznacza górnš przepustowoć krawędzi (dolne ograniczenie na przepływ jest przyjmowane jako 0). Drugi parametr okrela jednostkowy koszt przepływu przez krawęd.------------------------------------[Kolorowanie] - ALGORYTMY KOLOROWANIA GRAFÓW{Kolorowanie wierzchołków}Problem ten polega na takim pokolorowaniu wierzchołków, aby żadne dwa wierzchołki ze sobš połšczone nie miały przypisanego takiego samego koloru i liczba użytych kolorów była jak najmniejsza. Do dyspozycji znajduje się kilka algorytmów heurystycznych o różnych dokładnociach i czasach działania.{Kolorowanie krawędzi}Algorytm przyporzšdkowuje kolory krawędziom grafu w taki sposób, aby żadne dwie krawędzie wychodzšce z jednego wierzchołka nie były pomalowane takim samym kolorem i liczba użytych kolorów była jak najmniejsza.W obu modelach kolorowania krawędzie nie muszš mieć okrelonych parametrów liczbowych.------------------------------------[Skojarzenia] - ALGORYTMY WYZNACZANIA SKOJARZEŃ{Maksymalne skojarzenie}Algorytm wyznacza maksymalnš liczbę krawędzi w grafie, sporód których żadne dwie nie wychodzš z tego samego wierzchołka.{Maksymalna klika}Maksymalna klika, to największy podgraf grafu, w którym wszystkie pary wierzchołków sš ze sobš połšczone. Dostępne sš dwa algorymy wyznaczania maksymalnej kliki - przybliżony i dokładny.W obu powyższych modelach krawędzie nie muszš mieć okrelonych parametrów liczbowych.------------------------------------[Pomoc] - POMOC PODRĘCZNA------------------------------------ [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl chiara76.opx.pl
Program MODGRAF służy do rozwišzywania problemów decyzyjnych za pomocš modeli i algorytmów grafowych bšd sieciowych.TYPOWY PROCES MODELOWANIA I ROZWIĽZYWANIA PROBLEMU:===================================================1) Zdefiniowanie grafu w postaci pliku tekstowego ("Plik/Nowy graf") lub wczytanie grafu z istniejšcego pliku ("Plik/Wczytaj graf").2) Po wczytaniu pliku ze zdefiniowanym grafem może wystšpić jedna z trzech sytuacji:* Graf wczytuje się poprawnie i w głównym oknie pojawia się jego graficzna reprezentacja. W zależnoci od potrzeb poszczególne wierzchołki grafu można wtedy przesuwać za pomocš przecišgania myszš z wciniętym jej lewym klawiszem. Przesunięcie całego grafu realizowane jest podobnie, ale z wciniętym klawiszem Shift. Zmienione rozmieszczenie wierzchołków grafu może zostać dopisane do pliku wejciowego i zapamiętane poprzez wybranie z menu "Plik" pozycji "Zachowaj topologię jako".* Graf wczytuje się poprawnie, ale pojawia się komunikat informujšcy, że graf nie będzie wywietlany. Następuje to w przypadku wczytywania dużych grafów. Ich pełna reprezentacja graficzna jest wtedy niemożliwa, a w głównym oknie wywietlona jest tylko zastępcza winieta, która informuje o parametrach wczytanego grafu. Pomimo braku reprezentacji graficznej wszystkie algorytmy i operacje na grafie sš dostępne.* Pojawia się komunikat o błędzie i numer linii, w której zidentyfikowano błšd. W takim przypadku należy poprawić opis grafu w pliku tekstowym, wybierajšc z menu "Plik" pozycję "Edytuj graf".3) Wybranie odpowiedniego algorytmu (patrz opis poniżej) spowoduje rozwišzanie problemu i wywietlenie wyniku, skšd może on zostać zapisany w osobnym pliku. W większoci przypadków rozwišzanie zobrazowane jest także w postaci reprezentacji graficznej.ZESTAW DOSTĘPNYCH OPCJI PROGRAMU:====================================[Plik] - OPERACJE NA PLIKACH{Nowy graf}Otwiera okno edycyjne, pozwalajšce zdefiniować graf w postaci pliku tekstowego (patrz "Format pliku wejciowego").{Wczytaj graf}Wczytuje graf z wczeniej zapisanego pliku, utworzonego za pomocš opcji "Plik/Nowy graf" lub zewnętrznego edytora tekstowego.{Edytuj graf}Otwiera okno edycyjne, zawierajšce opis aktualnie wczytanego grafu, pozwalajšc na zmodyfikowanie jego postaci.{Zachowaj topologię jako}Pozwala na zapisanie w pliku akualnego położenia wierzchołków grafu na ekranie.{Koniec}Wyjcie z programu.------------------------------------[Trasy] - ALGORYTMY WYZNACZANIA TRAS{Drzewo rozpinajšce}Algorytm znajduje podgraf analizowanego grafu, który jest drzewem zawierajšcym wszystkie jego wierzchołki i suma wag krawędzi jest najmniejsza (minimalne drzewo rozpinajšce) lub największa (maksymalne drzewo rozpinajšce). Algorytmy wymagajš grafu nieskierowanego.Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - reprezentujšcy wagę krawędzi.{Najkrótsze drogi - Alg. Dijkstry}Algorytm znajduje najkrótsze drogi z podanego wierzchołka do wszystkich pozostałych wierzchołków grafu.Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - wagę krawędzi. Wagi krawędzi muszš być nieujemne.{Najkrótsze drogi - Alg. Floyda}Algorytm znajduje najkrótsze drogi pomiędzy wszystkimi parami wierzchołków. Jako wynik powstaje tablica odległoci pomiędzy wierzchołkami.Krawędzie grafu powinny mieć zdefiniowany jeden parametr liczbowy - wagę krawędzi.{Komiwojażer}Problem komiwojażera polega na znalezieniu w grafie cyklu, który przechodziłby przez każdy jego wierzchołek dokładnie raz, a suma wag poszczególnych krawędzi cyklu była najmniejsza z możliwych. Algorytmy Near i FI znajdujš pewne zgrubne przybliżenie rozwišzania o najmniejszej sumie wag i mogš zostać poprawione poprzez zastosowanie dodatkowych heurystyk poprawy: 2Opt i 3Opt. Istota algorytmu 2Opt nie pozwala na zastosowanie go do grafu skierowanego. Algorytm dokładny znajduje optymalne rozwišzanie problemu komiwojażera, zarówno dla grafów skierowanych, jak i nieskierowanych. Możliwoć znalezienia rozwišzania dokładnego okupiona jest jednak znacznym wydłużeniem czasu obliczeń.Krawędzie grafu powinny mieć zdefiniowany jeden parametr - wagę krawędzi.{Cykl Eulera}Algorytm znajduje taki cykl w grafie, w którym każda krawęd (łuk) występuje dokładnie raz. Po wykonaniu algorytmu kolejnoć przechodzenia krawędzi zaznaczona jest numerami.Krawędzie grafu nie muszš mieć podanych żadnych parametrów liczbowych.------------------------------------[Przepływy] - ALGORYMY WYZNACZANIA PRZEPŁYWÓW W SIECIACH{Maksymalny przepływ}Algorytm wyznacza maksymalny przepływ pomiędzy podanš parš wierzchołków.Krawędzie grafu powinny mieć okrelony jeden parametr - przepustowoć krawędzi (łuku).{Najtańszy przepływ}Algorytm wyznacza najtańszy przepływ o zadanej wielkoci pomiędzy podanš parš wierzchołków.Krawędzie grafu powinny mieć dwa parametry. Pierwszy parametr oznacza górnš przepustowoć krawędzi (dolne ograniczenie na przepływ jest przyjmowane jako 0). Drugi parametr okrela jednostkowy koszt przepływu przez krawęd.------------------------------------[Kolorowanie] - ALGORYTMY KOLOROWANIA GRAFÓW{Kolorowanie wierzchołków}Problem ten polega na takim pokolorowaniu wierzchołków, aby żadne dwa wierzchołki ze sobš połšczone nie miały przypisanego takiego samego koloru i liczba użytych kolorów była jak najmniejsza. Do dyspozycji znajduje się kilka algorytmów heurystycznych o różnych dokładnociach i czasach działania.{Kolorowanie krawędzi}Algorytm przyporzšdkowuje kolory krawędziom grafu w taki sposób, aby żadne dwie krawędzie wychodzšce z jednego wierzchołka nie były pomalowane takim samym kolorem i liczba użytych kolorów była jak najmniejsza.W obu modelach kolorowania krawędzie nie muszš mieć okrelonych parametrów liczbowych.------------------------------------[Skojarzenia] - ALGORYTMY WYZNACZANIA SKOJARZEŃ{Maksymalne skojarzenie}Algorytm wyznacza maksymalnš liczbę krawędzi w grafie, sporód których żadne dwie nie wychodzš z tego samego wierzchołka.{Maksymalna klika}Maksymalna klika, to największy podgraf grafu, w którym wszystkie pary wierzchołków sš ze sobš połšczone. Dostępne sš dwa algorymy wyznaczania maksymalnej kliki - przybliżony i dokładny.W obu powyższych modelach krawędzie nie muszš mieć okrelonych parametrów liczbowych.------------------------------------[Pomoc] - POMOC PODRĘCZNA------------------------------------ [ Pobierz całość w formacie PDF ]