• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Mar 26th, 2019 74 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.
Not a member of Pastebin yet?