I problemi del commesso viaggiatore riguardano un venditore e un insieme di città. Il venditore deve visitare ciascuna delle città partendo da una certa (ad esempio, la città natale) e tornare nella stessa città. La sfida del problema è che il venditore ambulante deve ridurre al minimo la durata totale del viaggio.
Supponiamo che le città siano x1X2..... XNdove costo cijindica il costo del viaggio dalla città xioaxJ. Il problema del commesso viaggiatore è trovare un itinerario che inizi e termini in x1che porterà in tutte le città con il costo minimo.
Esempio: Un giornalaio consegna quotidianamente il giornale nella zona assegnata in modo tale da dover coprire tutte le case della rispettiva zona con una spesa di viaggio minima. Calcolare il costo minimo del viaggio.
L'area assegnata all'agente dove deve depositare il giornale è mostrata in fig:
Soluzione: La matrice costi-adiacenza del grafo G è la seguente:
costoij=
Il tour parte dall'area H1e poi selezionare la zona di costo minimo raggiungibile da H1.
Segna l'area H6perché è la zona di costo minimo raggiungibile da H1e poi selezionare la zona di costo minimo raggiungibile da H6.
Segna l'area H7perché è la zona di costo minimo raggiungibile da H6e poi selezionare la zona di costo minimo raggiungibile da H7.
Segna l'area H8perché è la zona di costo minimo raggiungibile da H8.
Segna l'area H5perché è la zona di costo minimo raggiungibile da H5.
Segna l'area H2perché è la zona di costo minimo raggiungibile da H2.
Segna l'area H3perché è la zona di costo minimo raggiungibile da H3.
Segna l'area H4e poi selezionare la zona di costo minimo raggiungibile da H4è H1.Quindi, utilizzando la strategia greedy, otteniamo quanto segue.
4 3 2 4 3 2 1 6 H<sub>1</sub> → H<sub>6</sub> → H<sub>7</sub> → H<sub>8</sub> → H<sub>5</sub> → H<sub>2</sub> → H<sub>3</sub> → H<sub>4</sub> → <sub>H<sub>1</sub></sub>.
Quindi il costo minimo del viaggio = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
come rifare in Photoshop
Matroidi:
Un matroide è una coppia ordinata M(S, I) che soddisfa le seguenti condizioni:
- S è un insieme finito.
- I è una famiglia non vuota di sottoinsiemi di S, detti sottoinsiemi indipendenti di S, tali che se B ∈ I e A ∈ I. Diciamo che I è ereditario se soddisfa questa proprietà. Si noti che l’insieme vuoto ∅ è necessariamente membro di I.
- Se A ∈ I, B ∈ I e |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>
Diciamo che un matroide M (S, I) è pesato se è associata una funzione peso w che assegna un peso strettamente positivo w (x) a ciascun elemento x ∈ S. La funzione peso w si estende a un sottoinsieme di S per somma :
w (A) = ∑<sub>x∈A</sub> w(x)
per ogni A ∈ S.