Проблемите с пътуващия търговец се съобразяват с търговец и набор от градове. Продавачът трябва да посети всеки един от градовете, като започне от определен (напр. родния град) и да се върне в същия град. Предизвикателството на проблема е, че пътуващият търговец трябва да минимизира общата дължина на пътуването.
Да предположим, че градовете са x1х2..... хнкъдето цена cijобозначава разходите за пътуване от град xiдо хй. Проблемът на пътуващия продавач е да намери маршрут, който започва и завършва на x1който ще приеме всички градове с минимални разходи.
Пример: Един вестникарски агент ежедневно пуска вестника в определения район по такъв начин, че трябва да покрие всички къщи в съответния район с минимални разходи за пътуване. Изчислете минималните разходи за пътуване.
Областта, определена за агента, където той трябва да пусне вестника, е показана на фиг.
Решение: Матрицата на съседство на разходите на графика G е както следва:
ценаij=
Обиколката започва от местност Х1и след това изберете зоната с минимални разходи, достъпна от H1.
Маркирайте зона H6защото това е зоната с минимални разходи, достъпна от H1и след това изберете зона с минимални разходи, достъпна от H6.
Маркирайте зона H7защото това е зоната с минимални разходи, достъпна от H6и след това изберете зона с минимални разходи, достъпна от H7.
Маркирайте зона H8защото това е зоната с минимални разходи, достъпна от H8.
Маркирайте зона H5защото това е зоната с минимални разходи, достъпна от H5.
Маркирайте зона H2защото това е зоната с минимални разходи, достъпна от H2.
Маркирайте зона H3защото това е зоната с минимални разходи, достъпна от H3.
Маркирайте зона H4и след това изберете зоната с минимални разходи, достъпна от H4това е Х1.И така, използвайки алчната стратегия, получаваме следното.
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>.
Така минималните разходи за пътуване = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
document.queryselector
Matroids:
Матроидът е подредена двойка M(S, I), която отговаря на следните условия:
- S е крайно множество.
- I е непразно семейство от подмножества на S, наречени независими подмножества на S, така че ако B ∈ I и A ∈ I. Казваме, че I е наследствено, ако удовлетворява това свойство. Забележете, че празното множество ∅ е задължително член на I.
- Ако 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) = ∑<sub>x∈A</sub> w(x)
за всяко A ∈ S.