Algorytm liczenia maksymalnego oddalenia

Odpowiedz Nowy wątek
2015-01-02 19:46
Krwawy Mleczarz
0

Witam
Poszukuję gotowego algorytmu który pozwalałby na wyznaczenie maksymalnej liczby połączeń dla danego wierzchołka w grafie

Pozostało 580 znaków

2015-01-02 19:49
0

Jest na to co najmniej tyle algorytmów ile istnieje reprezentacji grafów, nie wspominając już o tym że temat: - "maksymalnej liczby połączeń dla danego wierzchołka" - to właściwie nie wiadomo o co biega.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-02 20:10
Krwawy Mleczarz
0

Mam do przeanalizowania sieć tramwajową we Wrocławiu, gdzie za wierzchołek przyjmuje się przystanek. Jak że ilość przystanków jest na tyle duża że ręczne liczenie jest bardzo czasochłonne poszukuje jakiegoś algorytmu który pozwoli mi na wyznaczenie maksymalnej ilości krawędzi dla każdego wierzchołka, co następnie posłuży mi do wyznaczenia punktu centralnego oraz peryferyjnego. kierunek ruchu nie ma znaczenia. Nie znam się na programowaniu więc nie potrafię się posługiwać programistycznymi nazwami, czy tez samemu coś napisać.

Pozostało 580 znaków

2015-01-02 20:33
Krwawy Mleczarz
0

Możę graficzna wersja trochę rozjaśni mój problem

Pozostało 580 znaków

2015-01-02 21:06
0

No to albo zaczniesz oprować programistycznymi nazwami, albo zaczniesz pisać po polsku. Bo ja na przykład nadal nie rozumiem co to jest twoje "maksymalne oddalenie". W jaki sposób to liczysz? Co to jest "maksymalna ilośc krawędzi dla wierzchołka"? Jakich krawędzi?
Jeśli chodzi o wyznaczanie centralności to istnieją formalne matematyczne miary dla grafów, takie jak degree, betweenness, closeness (i wiele innych). Chodzi ci o którąś z nich? Bo tak na oko to może ci chodzić o betweenness -> to jest liczba najkrótszych ścieżek pomiędzy dowolnymi 2 węzłami grafu, które przechodzą przez dany wierzchołek.

Napisz nam JAK liczysz te swoje wartości ręcznie a my ci powiemy jakiego algorytmu szukasz...


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 1x, ostatnio: Shalom, 2015-01-02 21:07

Pozostało 580 znaków

2015-01-02 21:21
Krwawy Mleczarz
0

W załączniku jest prosty graf przykładowy na podstawie którego wyjaśnię jak liczy się maksymalne oddalenie.
Graf posiada wierzchołki dajmy na ten przykład wierzchołek A dla niego maksymalne oddalenie jest równe 6 ponieważ najdalszy wierzchołek względem wierzchołka A jest oddalony o 6 krawędzi, czyli linii łączących sąsiednie wierzchołki. podobnie sytuacja ma się w przypadku punktu B z tą jednak różnica, że maksymalne oddalenie wynosi 5 ponieważ najdalszy wierzchołek od wierzchołka B znajduje się w odległości 5 krawędzi od niego. I teraz tak o ile w przypadku tak prostego grafu jest to do ogarnięcia to w przypadku grafu z 200 wierzchołkami jest to problematyczne, wyżej wymienioną czynność należny powtórzyć dla każdego wierzchołka w grafie. Podsumowując szukam najdłuższą możliwą drogę, którą da się wyznaczyć (oczywiście bez powielania tego samego punktu, droga może przechodzić tylko raz przez dany punkt) dla danego punktu. w Załączniku dodaję również graf właściwy na podstawie którego przeprowadzam analizę.

Pozostało 580 znaków

2015-01-02 21:29
0

A jak sie mają do tego cykle? Co jeśli mogę dojść z wierzchołka A do wierzchołka B dwiema drogami i jedna z nich jest krótsza a druga dłuższa?
Bo jeśli szukasz dla każdego wierzchołka najdłuższej najkrótszej ścieżki pomiędzy tym wierzchołkiem a dowolnym innym to:
http://pl.wikipedia.org/wiki/Algorytm_Floyda-Warshalla + wybranie dla każdego wierzchołka maksa.

Ten algorytm tworzy tablicę, która dla pary wierzchołków A,B zwraca najkrótszą ścieżkę między tymi wierzchołkami. Możesz więc sprawdzić ścieżkę z A do każdego innego wierzchołka i wybrać najdłuższą, a potem powtórzyć to dla innych wierzchołków.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.
edytowany 1x, ostatnio: Shalom, 2015-01-02 21:31

Pozostało 580 znaków

2015-01-02 21:44
Krwawy Mleczarz
0

Ja nie jestem informatykiem, pojęcie o programowaniu mam raczej nikłe. Źle to ująłem ja poszukuję albo gotowego programu albo kodu. Sprecyzuję problem, bo ja potrzebuję takiego programu do analizy który wykonuje działania na ściśle określonych warunkach. Widzę że źle się zrozumieliśmy w wyniku odliczeń chciałbym dostać coś takiego, że najdalszy punkt od wierzchołka A oddalony jest o 5 krawędzi(połączeń), dla wierzchołka B najdalszy punkt oddalony jest o 4 krawędzie itd dla każdego po kolei. Chodzi mi o coś w tym stylu http://www.algorytm.org/algor[...]-wszerz-bfs-i-w-glab-dfs.html "Przeszukiwanie w głąb (DFS)"

Pozostało 580 znaków

2015-01-02 21:47
Krwawy Mleczarz
0

Zaproponowany przez ciebie sposób jest jak najbardziej dobry z tym że nie wiem jak to użyć w praktyce, krótko mówiąc nie potrafię napisać kodu.

Pozostało 580 znaków

2015-01-02 22:04
0

Więc dla każdego węzła odpalasz algorytm DSijkstry (ponieważ krawędzie nie mają wag to można również DFS lub A+) i wyznaczasz z tych minimalnych dróg co on znajdzie maksymalną drogę.
Skoro graf nie jest skierowany to można na zmniejszyć ilość odpaleń Dijkstry o jeden węzeł, z tym że tak mała oszczędność raczej nie warta sporej komplikacji algorytmu.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-02 22:11
0

@Krwawy Mleczarz dla trywialnego przypadku z nieskierowanym i nieważonym grafem to wszytko jest jeden pies, czy odpalisz sekwencyjnie Dijkstre/Bellmana Forda/BFS czy odpalisz Floyda-Warshalla czy Johnsona. Efekt będzie taki sam a implementacja dość podobna.

Jeśli chodzi o gotowe narzędzie to pewnie wisi z setka takich w internecie, wystarczy poszukać po nazwach algorytmów.


Na PW przyjmuje tylko (ciekawe!) zlecenia. Masz problem? Pisz na forum, nie do mnie.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0