Проблемите с пътуващия търговец се съобразяват с търговец и набор от градове. Продавачът трябва да посети всеки един от градовете, като започне от определен (напр. родния град) и да се върне в същия град. Предизвикателството на проблема е, че пътуващият търговец трябва да минимизира общата дължина на пътуването.

Да предположим, че градовете са x₁х₂..... х_нкъдето цена c_ijобозначава разходите за пътуване от град x_iдо х_й. Проблемът на пътуващия продавач е да намери маршрут, който започва и завършва на x₁който ще приеме всички градове с минимални разходи.

Пример: Един вестникарски агент ежедневно пуска вестника в определения район по такъв начин, че трябва да покрие всички къщи в съответния район с минимални разходи за пътуване. Изчислете минималните разходи за пътуване.

Областта, определена за агента, където той трябва да пусне вестника, е показана на фиг.

Решение: Матрицата на съседство на разходите на графика G е както следва:

цена_ij=

Обиколката започва от местност Х₁и след това изберете зоната с минимални разходи, достъпна от H₁.

Маркирайте зона H₆защото това е зоната с минимални разходи, достъпна от H₁и след това изберете зона с минимални разходи, достъпна от H₆.

Маркирайте зона H₇защото това е зоната с минимални разходи, достъпна от H₆и след това изберете зона с минимални разходи, достъпна от H₇.

Маркирайте зона H₈защото това е зоната с минимални разходи, достъпна от H₈.

Маркирайте зона H₅защото това е зоната с минимални разходи, достъпна от H₅.

Маркирайте зона H₂защото това е зоната с минимални разходи, достъпна от H₂.

Маркирайте зона H₃защото това е зоната с минимални разходи, достъпна от H₃.

Маркирайте зона H₄и след това изберете зоната с минимални разходи, достъпна от H₄това е Х₁.И така, използвайки алчната стратегия, получаваме следното.

 4 3 2 4 3 2 1 6 H<sub>1</sub> &#x2192; H<sub>6</sub> &#x2192; H<sub>7</sub> &#x2192; H<sub>8</sub> &#x2192; H<sub>5</sub> &#x2192; H<sub>2</sub> &#x2192; H<sub>3</sub> &#x2192; H<sub>4</sub> &#x2192; <sub>H<sub>1</sub></sub>. 

Така минималните разходи за пътуване = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25

document.queryselector

Matroids:

Матроидът е подредена двойка M(S, I), която отговаря на следните условия:

1. S е крайно множество.
2. I е непразно семейство от подмножества на S, наречени независими подмножества на S, така че ако B ∈ I и A ∈ I. Казваме, че I е наследствено, ако удовлетворява това свойство. Забележете, че празното множество ∅ е задължително член на I.
3. Ако A ∈ I, B ∈ I и |A|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>

Казваме, че матроид M (S, I) е претеглен, ако има свързана тегловна функция w, която присвоява строго положително тегло w (x) на всеки елемент x ∈ S. Тегловата функция w се разширява до подмножество на S чрез сумиране :

 w (A) = &#x2211;<sub>x&#x2208;A</sub> w(x) 

за всяко A ∈ S.