daily pastebin goal
40%
SHARE
TWEET

Untitled

a guest Mar 26th, 2019 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import math
  2. from random import randint
  3. from time import perf_counter
  4.  
  5. my_list = ["ala", "ma", "Kota"]
  6. towns = [[2, 3], [3, 4], [5, 8], [7, 2], [7, 7], [3, 10], [8, 1], [1, 5], [4, 7],
  7.          [3, 6], [6, 4], [7, 4]]  # koordynaty miast
  8. generated_towns = []
  9. result = []  # tablica na miasta po uruchomieniu funkcji nearest_neighbor
  10.  
  11.  
  12. def distance_between_cities(city_a, city_b):
  13.     distance = math.hypot(city_b[0] - city_a[0], city_b[1] - city_a[1])
  14.     return distance
  15.  
  16.  
  17. def find_closest(town, towns_ls):
  18.     towns_list = towns_ls.copy()
  19.     start = town
  20.     distance = distance_between_cities(start, towns_list[0])
  21.     nearest = towns_list[0]
  22.     for x in range(len(towns_list)):
  23.         if (distance_between_cities(start, towns_list[x]) < distance):
  24.             distance = distance_between_cities(start, towns_list[x])
  25.             nearest = towns_list[x]
  26.     return nearest, distance
  27.  
  28.  
  29. # funkcja znajdujaca droge metodą najbliższego sąsaida
  30. # town - koordynaty miasta z którego zaczynamy
  31. # town_ls - lista miast do przeszukania
  32. # @return zwraca drogę jaką trzeba przejechać żeby odwiedzić wszystkie miasta
  33. def nearest_neighbor(town, towns_ls):
  34.     time = perf_counter()
  35.     towns_list = towns_ls.copy()
  36.     result.append(town)
  37.     cost = 0
  38.     start = town
  39.     towns_list.remove(town)
  40.     length = len(towns_list)
  41.     for x in range(length):
  42.         res = find_closest(start, towns_list)
  43.         cost += res[1]
  44.         start = res[0]
  45.         result.append(start)
  46.         towns_list.remove(start)
  47.     time = perf_counter() - time
  48.     return cost, time
  49.  
  50.  
  51. def generate_towns(numer_of_cities):
  52.     for i in range(numer_of_cities):
  53.         x = randint(1, 100)
  54.         y = randint(1, 100)
  55.         generated_towns.append([x, y])
  56.  
  57.  
  58. for x in range(40,60):
  59.     generate_towns(x)
  60.     res = nearest_neighbor(generated_towns[1], generated_towns)
  61.     print("Ilość miast : " + str(x) + " Długość drogi : " + str(res[0]) + " Czas : " + str(res[1]))
  62.  
  63. # for x in result:
  64. #     print(str(x[0]) + "\t" + str(x[1]))
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. OK, I Understand
 
Top