• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# 2-approximation

a guest Apr 6th, 2020 132 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. from lib import *
2. from random import seed
3. from random import randint
4.
5. # seed random number generator
6. seed(1)
7.
9.
11.
12. result = {}
13. V = len(G)
14. E = edgeList(G)
15. print(E)
16.
17.
18. def VC(E):
19.     # E to graf złożony z niepokrytych jeszcze krawędzi
20.     # k liczba wierzchołków, które możemy użyć
21.     # S to zbiór wierzchołków, który budujemy
22.
23.     E1 = E.copy()
24.     S = set()
25.
26.     while len(E1) > 0:  # and k:
27.         # if k == 0:
28.         #     return None  # nie ma rozwiązania
29.
30.         index = randint(0, len(E1) - 1)
31.         print(f"index: {index}")
32.         edge = E1[index]
33.         # u = edge[0]
34.         # v = edge[1]
35.         # print(f"E111111111111: {E1}")
38.
39.         # E1.remove(edge)
40.         # print(E1)
41.
42.         # print("EDGE: " + str(edge))
43.
44.         E1 = [e for e in E1 if e[0] != edge[0] and e[1] != edge[0] and e[0] != edge[1] and e[1] != edge[1]]
45.         # print(E1)
46.         # k -= 1
47.
48.     return S
49.
50.
51. tries_count = 1000
52.
53. # while not result:
54. # k += 1
55. best_result = G
56. for i in range(0, tries_count):
57.     result = VC(E)
58.     if len(result) < len(best_result):
59.         print(f"UUUUUUUUU, {len(result)}")
60.         best_result = result
61.
62. print("\n\n\nZnaleziono rozwiązanie")
63. print(best_result)
64. saveSolution(filename + ".sol", best_result)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top