Problema del venditore ambulante
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 x 1 X 2 ..... X N dove costo c ij indica il costo del viaggio dalla città x io ax J . Il problema del commesso viaggiatore è trovare un itinerario che inizi e termini in x 1 che 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:
costo ij =
Il tour parte dall'area H 1 e poi selezionare la zona di costo minimo raggiungibile da H 1 .
Segna l'area H 6 perché è la zona di costo minimo raggiungibile da H 1 e poi selezionare la zona di costo minimo raggiungibile da H 6 .
Segna l'area H 7 perché è la zona di costo minimo raggiungibile da H 6 e poi selezionare la zona di costo minimo raggiungibile da H 7 .
Segna l'area H 8 perché è la zona di costo minimo raggiungibile da H 8 .
Segna l'area H 5 perché è la zona di costo minimo raggiungibile da H 5 .
Segna l'area H 2 perché è la zona di costo minimo raggiungibile da H 2 .
Segna l'area H 3 perché è la zona di costo minimo raggiungibile da H 3 .
Segna l'area H 4 e poi selezionare la zona di costo minimo raggiungibile da H 4 è H 1 .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
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.
![Cane incatenato davanti a casa in Texas, l'acqua arriva fino alla testa [VIDEO SALVATAGGIO]](https://techcodeview.com/img/trending/65/dog-chained-to-front-of-house-in-texas-flood-waters-up-to-her-head-rescue-video.webp)
