fork download
copy 
  1. import random
  2. import math
  3.  
  4. # functiile de baza
  5. def valid_state(x, y, z):
  6.  
  7.     return x >= 10 and y >= 5 and z >= 7 and (5*x + 3*y + z <= 150)
  8.  
  9. def calculate_impact(x, y, z):
  10.   # funcția obiectiv (impactul total). 
  11.     return 10*x + 15*y + 5*z
  12.  
  13. def get_random_valid_state():
  14.    # adaugam solutii la intamplare
  15.     x, y, z = 10, 5, 7 # pornim de la minime
  16.     pages_left = 150 - (5*x + 3*y + z)
  17.  
  18.     # adaugam aleator cantități valide
  19.     while pages_left > 0:
  20.         choice = random.choice(['x', 'y', 'z'])
  21.         if choice == 'x' and pages_left >= 5:
  22.             x += 1; pages_left -= 5
  23.         elif choice == 'y' and pages_left >= 3:
  24.             y += 1; pages_left -= 3
  25.         elif choice == 'z' and pages_left >= 1:
  26.             z += 1; pages_left -= 1
  27.         else:
  28.             break  
  29.     return x, y, z
  30.  
  31. def get_neighbors(x, y, z):
  32.      # generare vecini
  33.     neighbors = []
  34.     moves = [(1,0,0), (-1,0,0), (0,1,0), (0,-1,0), (0,0,1), (0,0,-1)]
  35.     for dx, dy, dz in moves:
  36.         nx, ny, nz = x + dx, y + dy, z + dz
  37.         if valid_state(nx, ny, nz):
  38.             neighbors.append((nx, ny, nz))
  39.     return neighbors
  40.  
  41. #   Greedy (introduce valoriile maxime pana nu mai incap)
  42. def greedy_optimization():
  43.     print("\n Algoritmul Greedy")
  44.     x, y, z = 10, 5, 7
  45.     pages_used = 5*x + 3*y + z
  46.  
  47.     while pages_used + 3 <= 150: # Cât timp mai încape un y
  48.         y += 1
  49.         pages_used += 3
  50.  
  51.     while pages_used + 1 <= 150: # Cât timp mai încape un z
  52.         z += 1
  53.         pages_used += 1
  54.  
  55.     impact = calculate_impact(x, y, z)
  56.     print(f"Soluție Greedy: x={x}, y={y}, z={z} | Impact: {impact}")
  57.     return impact
  58.  
  59. # Hill climbing (verifica constant vecinii sa vada care e mai bun)
  60. def hill_climbing():
  61.     current_x, current_y, current_z = get_random_valid_state()
  62.     current_impact = calculate_impact(current_x, current_y, current_z)
  63.  
  64.     while True:
  65.         neighbors = get_neighbors(current_x, current_y, current_z)
  66.         best_neighbor = None
  67.         best_impact = current_impact
  68.  
  69.         for nx, ny, nz in neighbors:
  70.             impact = calculate_impact(nx, ny, nz)
  71.             if impact > best_impact:
  72.                 best_impact = impact
  73.                 best_neighbor = (nx, ny, nz)
  74.  
  75.         if best_neighbor is None: 
  76.             break
  77.  
  78.         current_x, current_y, current_z = best_neighbor
  79.         current_impact = best_impact
  80.  
  81.     return current_x, current_y, current_z, current_impact
  82.  
  83. # Simulated annealing (asemanator cu hill, doar ca greseste intentionat pentru a isi face o idee despre date)
  84. def simulated_annealing(temp, cooling_rate, iterations):
  85.     current_x, current_y, current_z = get_random_valid_state()
  86.     current_impact = calculate_impact(current_x, current_y, current_z)
  87.  
  88.     best_x, best_y, best_z, best_impact = current_x, current_y, current_z, current_impact
  89.  
  90.     for _ in range(iterations):
  91.         neighbors = get_neighbors(current_x, current_y, current_z)
  92.         if not neighbors:
  93.             break
  94.  
  95.         nx, ny, nz = random.choice(neighbors)
  96.         new_impact = calculate_impact(nx, ny, nz)
  97.  
  98.         # daca e bun se accepta, daca nu, se accepta cu o probabilitate
  99.         if new_impact > current_impact or random.random() < math.exp((new_impact - current_impact) / temp):
  100.             current_x, current_y, current_z = nx, ny, nz
  101.             current_impact = new_impact
  102.  
  103.             # se salveaza cel mai bun rezultat intalnit
  104.             if current_impact > best_impact:
  105.                 best_x, best_y, best_z, best_impact = current_x, current_y, current_z, current_impact
  106.  
  107.         temp *= cooling_rate # Răcim temperatura
  108.  
  109.     return best_x, best_y, best_z, best_impact
  110.  
  111. # Rularea
  112.  
  113. # Greedy
  114. greedy_optimization()
  115.  
  116. # Hill
  117. print("\n Hill Climbing")
  118. for i in range(1, 4):
  119.     x, y, z, impact = hill_climbing()
  120.     print(f"Execuția {i}: x={x}, y={y}, z={z} | Impact: {impact}")
  121.  
  122. # SA
  123. print("\n Simulated Annealing")
  124. params = [
  125.     (100.0, 0.95, 100),  # T_start=100, Rata racire=0.95, Iterații=100
  126.     (500.0, 0.99, 500),  # Parametri pentru explorare agresivă
  127.     (10.0,  0.80, 50)    # Răcire foarte rapidă (devine similar cu Hill Climbing)
  128. ] # Odata ce racirea devine aproape de 0 algoritmul va refuza sa mai faca greseli intentionat
  129.  
  130. for p_idx, (t, cr, iters) in enumerate(params, 1):
  131.     print(f"\nConfigurația {p_idx} (Temp={t}, Răcire={cr}, Iterații={iters}):")
  132.     for i in range(1, 4):
  133.         x, y, z, impact = simulated_annealing(t, cr, iters)
  134.         print(f"  Execuția {i}: x={x}, y={y}, z={z} | Impact: {impact}")
  135.  
Success #stdin #stdout 0.1s 14196KB
comments (?)
stdin
copy 
30 499887702
128990795 137274936
575374246 989051853
471048785 85168425
640066776 856699603
819841327 611065509
704171581 22345022
536108301 678298936
119980848 616908153
117241527 28801762
325850062 478675378
623319578 706900574
998395208 738510039
475707585 135746508
863910036 599020879
340559411 738084616
122579234 545330137
696368935 86797589
665665204 592749599
958833732 401229830
371084424 523386474
463433600 5310725
210508742 907821957
685281136 565237085
619500108 730556272
88215377 310581512
558193168 136966252
475268130 132739489
303022740 12425915
122379996 137199296
304092766 23505143
stdout
copy 
 Algoritmul Greedy
Soluție Greedy: x=10, y=31, z=7 | Impact: 600

 Hill Climbing
Execuția 1: x=17, y=17, z=14 | Impact: 495
Execuția 2: x=18, y=14, z=18 | Impact: 480
Execuția 3: x=19, y=13, z=16 | Impact: 465

 Simulated Annealing

Configurația 1 (Temp=100.0, Răcire=0.95, Iterații=100):
  Execuția 1: x=14, y=22, z=14 | Impact: 540
  Execuția 2: x=19, y=13, z=16 | Impact: 465
  Execuția 3: x=15, y=17, z=24 | Impact: 525

Configurația 2 (Temp=500.0, Răcire=0.99, Iterații=500):
  Execuția 1: x=10, y=26, z=22 | Impact: 600
  Execuția 2: x=12, y=21, z=26 | Impact: 565
  Execuția 3: x=10, y=28, z=16 | Impact: 600

Configurația 3 (Temp=10.0, Răcire=0.8, Iterații=50):
  Execuția 1: x=19, y=12, z=19 | Impact: 465
  Execuția 2: x=18, y=15, z=15 | Impact: 480
  Execuția 3: x=18, y=14, z=18 | Impact: 480
https://ideone.com/ebrFWu
language:
Python 3 (python  3.12)
created:
2 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!