Algorithms

Voyageur de commerce

import numpy as np
import matplotlib.pyplot as plt

villes = np.random.rand(20, 2)
villes[:5]

array([[0.90080623, 0.2350022 ],
       [0.56755441, 0.54858335],
       [0.60316886, 0.99559521],
       [0.87287745, 0.22318813],
       [0.21085165, 0.0701609 ]])

fig, ax = plt.subplots(1, 1, figsize=(3, 3))
indices = list(range(-1, villes.shape[0]))
ax.plot(villes[indices, 0], villes[indices, 1], "o-")

[<matplotlib.lines.Line2D at 0x73893a0a5370>]

def distance(v1, v2):  # v1= np.array([0, 1]), v2= ....
    return ((v1 - v2) ** 2).sum() ** 0.5


def plus_proche_non_visitee(villes, chemin):
    depart = chemin[-1]
    dmin, imin = None, None
    for i in range(villes.shape[0]):
        if i not in chemin:
            d = distance(villes[depart], villes[i])
            if dmin is None or d < dmin:
                dmin, imin = d, i
    return imin


def algo_proche_en_proche(villes):
    chemin = [0]
    while len(chemin) < villes.shape[0]:
        # trouver la ville la plus proche non visitée de la dernière
        # ville visitée et l'ajouter au chemin
        inext = plus_proche_non_visitee(villes, chemin)
        chemin.append(inext)
    return chemin


chemin = algo_proche_en_proche(villes)
indices = chemin + chemin[:1]
fig, ax = plt.subplots(1, 1, figsize=(3, 3))
ax.plot(villes[indices, 0], villes[indices, 1], "o-")

[<matplotlib.lines.Line2D at 0x738939c39b50>]

def elimine_croisements(villes, chemin):
    C = chemin
    while True:
        mieux = 0
        for i in range(-1, villes.shape[0]):
            for j in range(i + 2, villes.shape[0] - 1):
                delta = (
                    -distance(villes[C[i]], villes[C[i + 1]])
                    - distance(villes[C[j]], villes[C[j + 1]])
                    + distance(villes[C[i]], villes[C[j]])
                    + distance(villes[C[i + 1]], villes[C[j + 1]])
                )
                if delta < 0:
                    mieux += 1
                    print("mieux", i, j, delta, chemin[i + 1 : j + 1], chemin[j:i:-1])
                    # c'est mieux... on retourne les villes du chemin
                    # entre i+1 et j inclus
                    if i >= 0:
                        chemin[i + 1 : j + 1] = chemin[j:i:-1]
                    else:
                        chemin[i + 1 : j + 1] = chemin[j::-1]
        if mieux == 0:
            break


elimine_croisements(villes, chemin)
fig, ax = plt.subplots(1, 1, figsize=(3, 3))
indices = chemin + chemin[:1]
ax.plot(villes[indices, 0], villes[indices, 1], "o-")
ax.plot(villes[chemin[:1], 0], villes[chemin[:1], 1], "or")
ax.plot(villes[chemin[-1:], 0], villes[chemin[-1:], 1], "og")

mieux -1 3 -0.15191965099971733 [0, 3, 14, 19] []
mieux -1 11 -0.5172511323315206 [19, 14, 3, 0, 16, 6, 10, 17, 15, 11, 18, 2] []
mieux 11 13 -0.0513745444570991 [1, 12] [12, 1]
mieux 11 17 -0.0044994455150375035 [12, 1, 7, 9, 4, 5] [5, 4, 9, 7, 1, 12]
mieux 15 17 -0.03444152981270798 [1, 12] [12, 1]
mieux 11 13 -0.12384307859548493 [5, 4] [4, 5]

[<matplotlib.lines.Line2D at 0x738937b2a870>]

Distance d’édition

def distance_edition(m1, m2):
    cout = np.empty((len(m1) + 1, len(m2) + 1))
    predi = np.empty((len(m1) + 1, len(m2) + 1), dtype=np.int64)
    predj = np.empty((len(m1) + 1, len(m2) + 1), dtype=np.int64)
    cout[:, 0] = np.arange(len(m1) + 1)
    cout[0, :] = np.arange(len(m2) + 1)
    predi[:, 0] = np.arange(len(m1) + 1) - 1
    predj[:, 0] = 0
    predi[0, :] = 0
    predj[0, :] = np.arange(len(m2) + 1) - 1
    for i in range(1, len(m1) + 1):
        for j in range(1, len(m2) + 1):
            c_sup = cout[i - 1, j] + 1
            c_ins = cout[i, j - 1] + 1
            c_cmp = cout[i - 1, j - 1] + (1 if m1[i - 1] != m2[j - 1] else 0)
            if c_cmp <= min(c_sup, c_ins):
                cout[i, j], predi[i, j], predj[i, j] = c_cmp, i - 1, j - 1
            elif c_sup <= c_ins:
                cout[i, j], predi[i, j], predj[i, j] = c_sup, i - 1, j
            else:
                cout[i, j], predi[i, j], predj[i, j] = c_ins, i, j - 1
    # alignement
    alignement = [(len(m1), len(m2))]
    while min(alignement[-1]) >= 0:
        i, j = alignement[-1]
        i, j = predi[i, j], predj[i, j]
        alignement.append((i, j))
    alignement = alignement[::-1][2:]
    lettres = [(m1[i - 1], m2[j - 1]) for i, j in alignement]
    return cout, alignement, lettres


cout, alignement, lettres = distance_edition("ENSAE", "ESANE")
print(alignement)
print(lettres)
cout

[(np.int64(1), np.int64(1)), (np.int64(2), np.int64(1)), (np.int64(3), np.int64(2)), (np.int64(4), np.int64(3)), (np.int64(4), np.int64(4)), (5, 5)]
[('E', 'E'), ('N', 'E'), ('S', 'S'), ('A', 'A'), ('A', 'N'), ('E', 'E')]

array([[0., 1., 2., 3., 4., 5.],
       [1., 0., 1., 2., 3., 4.],
       [2., 1., 1., 2., 2., 3.],
       [3., 2., 1., 2., 3., 3.],
       [4., 3., 2., 1., 2., 3.],
       [5., 4., 3., 2., 2., 2.]])

---

Notebook on github