개발자를 위한 AI 알고리즘 (3일차)

 

126쪽 코드는 파이썬 3.0 이상에서만 돌아가는것 같다. 

문제를 해결하려면 링크 코드 대신에 다음 코드를 사용하면 된다.

 

https://github.com/Youngjin-com/AI_Algorhythm/blob/main/Chapter04/Travelling_Salesman_Problem.md?plain=1

AI_Algorhythm/Chapter04/Travelling_Salesman_Problem.md at main · Youngjin-com/AI_Algorhythm

import random
from itertools import permutations
import matplotlib.pyplot as plt
from collections import Counter
from time import time


aCity = complex


def distance_points(first, second):
    return abs(first - second)


def distance_tour(aTour):
    return sum(distance_points(aTour[i - 1], aTour[i])
               for i in range(len(aTour)))


def generate_cities(number_of_cities):
    seed = 111
    width = 500
    height = 300
    random.seed(number_of_cities * seed)
    return frozenset(aCity(random.randint(1, width), random.randint(1, height))
                     for c in range(number_of_cities))


## 무차별 대입 알고리즘


def brute_force(cities):
    return shortest_tour(permutations(cities))


def shortest_tour(tours):
    return min(tours, key=distance_tour)


## 시각화


def visualize_tour(tour, style='bo-'):
    if len(tour) > 1000:
        plt.figure(figsize=(15, 10))
    start = tour[0:1]
    visualize_segment(tour + start, style)
    visualize_segment(start, 'rD')


def visualize_segment(segment, style='bo-'):
    plt.plot([X(c) for c in segment], [Y(c) for c in segment], style, clip_on=False)
    plt.axis('scaled')
    plt.axis('off')


def X(city):
    return city.real


def Y(city):
    return city.imag


## TSP 함수


def tsp(algorithm, cities):
    t0 = time()
    tour = algorithm(cities)
    t1 = time()
    assert Counter(tour) == Counter(cities)
    visualize_tour(tour)
    print("{}: {} cities => tour length {:.0f} (in {:.3f} sec)".format(
        name(algorithm), len(tour), distance_tour(tour), t1-t0))


def name(algorithm):
    return algorithm.__name__.replace('_tsp', '')


## 실행


tsp(brute_force, generate_cities(10))


## 2- 탐욕 알고리즘


def greedy_algorithm(cities, start=None):
    city_ = start or first(cities)
    tour = [city_]
    unvisited = set(cities - {city_})
    while unvisited:
        city_ = nearest_neighbor(city_, unvisited)
        tour.append(city_)
        unvisited.remove(city_)
    return tour


def first(collection):
    return next(iter(collection))


def nearest_neighbor(city_a, cities):
    return min(cities, key=lambda city_: distance_points(city_, city_a))


tsp(greedy_algorithm, generate_cities(2000))

plt.show()