Pagini recente » Diferente pentru problema/shield intre reviziile 21 si 20 | Excel | Atasamentele paginii try_it | Atasamentele paginii Profil 6evanc6191fr2 | Diferente pentru blog/meet-in-the-middle intre reviziile 70 si 71
Nu exista diferente intre titluri.
Diferente intre continut:
bq. Find the shortest path between two nodes nodes in a large graph which you can’t keep in memory, for example the Facebook friendship graph.
One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. If the distance between two nodes is $k$ and the average branching factor in the network is $p$ then we explore $O(p^k/2^)$ nodes instead of $O(p^k^)$ nodes.
The usual approach is to use a bread first search algorithm. If the distance between two nodes is $k$ and the average degree in the network is $p$ then we explore $O(p^k^)$ nodes.
One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. This way we only go through $O(p^k/2^)$ nodes.
This approach works well on both path finding problems on explicit graphs and on implicit state graphs like ones in games.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.