Pagini recente » Diferente pentru utilizator/clubul_copiilor_anca intre reviziile 1 si 2 | Diferente pentru runda/oji-9-10-1/clasament intre reviziile 2 si 1 | Diferente pentru utilizator/clubul_copiilor_anca intre reviziile 3 si 2 | Diferente pentru blog/putina-recursivitate intre reviziile 8 si 4 | Diferente pentru blog/meet-in-the-middle intre reviziile 89 si 88
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.
!blog/meet-in-the-middle?12fig26.gif! The breadth first search algorithm is a standard approach for this problem. If the distance between two nodes is $k$ and the average degree in the network is $p$ BFS explores $O(p^k^)$ nodes.
!<blog/meet-in-the-middle?12fig26.gif 80%! The breadth first search algorithm is a standard approach for this problem. If the distance between two nodes is $k$ and the average degree in the network is $p$ BFS explores $O(p^k^)$ nodes.
A better solution starts from both nodes and sees when the two search spaces meet. This reduces the number of states explored to $O(p^k/2^)$.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
