Проблем с пътуващия търговец
Проблемите с пътуващия търговец се съобразяват с търговец и набор от градове. Продавачът трябва да посети всеки един от градовете, като започне от определен (напр. родния град) и да се върне в същия град. Предизвикателството на проблема е, че пътуващият търговец трябва да минимизира общата дължина на пътуването.
Да предположим, че градовете са x 1 х 2 ..... х н където цена c ij обозначава разходите за пътуване от град x i до х й . Проблемът на пътуващия продавач е да намери маршрут, който започва и завършва на x 1 който ще приеме всички градове с минимални разходи.
Пример: Един вестникарски агент ежедневно пуска вестника в определения район по такъв начин, че трябва да покрие всички къщи в съответния район с минимални разходи за пътуване. Изчислете минималните разходи за пътуване.
Областта, определена за агента, където той трябва да пусне вестника, е показана на фиг.
Решение: Матрицата на съседство на разходите на графика G е както следва:
цена ij =
Обиколката започва от местност Х 1 и след това изберете зоната с минимални разходи, достъпна от H 1 .
Маркирайте зона H 6 защото това е зоната с минимални разходи, достъпна от H 1 и след това изберете зона с минимални разходи, достъпна от H 6 .
Маркирайте зона H 7 защото това е зоната с минимални разходи, достъпна от H 6 и след това изберете зона с минимални разходи, достъпна от H 7 .
Маркирайте зона H 8 защото това е зоната с минимални разходи, достъпна от H 8 .
Маркирайте зона H 5 защото това е зоната с минимални разходи, достъпна от H 5 .
Маркирайте зона H 2 защото това е зоната с минимални разходи, достъпна от H 2 .
Маркирайте зона H 3 защото това е зоната с минимални разходи, достъпна от H 3 .
Маркирайте зона H 4 и след това изберете зоната с минимални разходи, достъпна от H 4 това е Х 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
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.
