Рандомизированный алгоритм

Revision ru2, by Kvark161, 2015-10-10 15:52:38

Задача: дан ориентированный граф. У каждой вершины есть некая величина H, нужно для каждой вершины посчитать H', равное минимуму из всех значений H вершин, до которых можно добраться из текущей. Количество вершин и ребер до 105.

Например, граф

1->2
2->3
2->5
3->4
5->6

H1 = 3, H2 = 30, H3 = 5, H4 = 1, H5 = 20, H6 = 10

Ответ:

H1' = 1, H2' = 1, H3' = 1, H4' = 1, H5' = 10, H6' = 10

И есть такое презабавное решение

G[N]; // список смежных вершин
H[N]; // те самые H
used[N] = {false}

dfs(v)
    used[v] = true
    suffle(G[v])
    for to in G[v]
        if used[to] = false
            dfs(to)
        H[v] = min(H[v], H[to])

main()
    for step = 0..25
        used = {false}
        P[N] = {0,1,2...,N-1}
        shuffle(P)
        for v in P
            dfs(v)

Завалить решение без shuffle довольно просто, а как быть с shuffle? Кто-нибудь умеет делать тесты для подобных решений? Или кто-нибудь может посчитать вероятность того, что решение выдаст правильный ответ? =)

Tags shuffle, рандом, random, dfs, graph, граф, дфс

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian Kvark161 2015-10-10 15:52:38 2 Мелкая правка: '~~~~\n\nЗалить реше' -
ru1 Russian Kvark161 2015-10-10 15:20:12 1119 Первая редакция (опубликовано)