 Algorytm najkrótszej drogi w genealogii |
| Algorytm najkrótszej drogi w genealogii |
 6.09.2008, 08:31:53
Post
#1
|
|
 Grupa: Zarejestrowani Postów: 108 Pomógł: 0 Dołączył: 15.10.2006 Skąd: zewsząd :P Ostrzeżenie: (0%) 
 |
Witam. Piszę system genealogiczny pod moje drzewo o ok. 42000 osób i zastanawiam się nad algorytmem znajdowania najkrótszej ścieżki łączącej dwie dowolne osoby na drzewie. Nie chodzi tu tylko o pokrewieństwa, ale też o osoby spowinowacone itp.
Zastanawiam się jak podejść do tego problemu. Jakiego algorytmu użyć? Myślałem o algorytmie Dijkstry, ale ten polega na znalezieniu najkrótszej ścieżki z wielu możliwych, podczas gdy tu będzie zazwyczaj jedna. Myślałem o implementacji którejś z metod przeszukiwania grafu (BFS i DFS) ale wszystko sprowadza się do sprawdzenia po kolei każdej możliwej ścieżki w drzewie. Czy znacie jakiś ciekawy algorytm który nie wykorzystywałby metody siłowej? Pozdrawiam Ten post edytował Michu 6.09.2008, 08:32:27 |
 |
 
|
 |
|
9.09.2008, 16:39:11
Post
#2
|
|
 Grupa: Zarejestrowani Postów: 662 Pomógł: 45 Dołączył: 26.03.2007 Skąd: Warszawa Ostrzeżenie: (0%)
|
Może to Ci pomoże
|
|
|
|
|
10.09.2008, 09:39:05
Post
#3
|
|
 Developer Grupa: Moderatorzy Postów: 3 045 Pomógł: 290 Dołączył: 20.01.2007 |
Przenoszę na PHP.
|
|
|
|
|
14.09.2008, 08:56:20
Post
#4
|
|
|
Grupa: Zarejestrowani Postów: 108 Pomógł: 0 Dołączył: 15.10.2006 Skąd: zewsząd :P Ostrzeżenie: (0%)
|
Hmm, czyli jednak Dijkstra. Dzięki
|
|
|
|
 |
|
Wersja Lo-Fi | Aktualny czas: 14.08.2025 - 14:30 |
