Проблеми са трговачким путницима се придржавају продавца и низа градова. Продавац мора да посети сваки од градова почевши од одређеног (нпр. родног града) и да се врати у исти град. Изазов проблема је у томе што путујући продавац треба да минимизира укупну дужину путовања.
Претпоставимо да су градови к1Икс2..... Икснгде кошта цијозначава трошкове путовања из града хидо кј. Проблем трговачког путника је пронаћи руту која почиње и завршава на к1који ће узети у све градове са минималним трошковима.
Пример: Новински агент свакодневно испушта новине у додељено подручје тако да мора да покрије све куће у том подручју уз минималне трошкове путовања. Израчунајте минималне трошкове путовања.
Подручје додељено агенту где мора да испусти новине приказано је на сл.
Решење: Матрица суседности трошкова графа Г је следећа:
трошакиј=
Обилазак почиње из области Х1а затим изаберите област минималне цене која је доступна од Х1.
јава динамички низ
Означите област Х6јер је то подручје минималне цене до које се може доћи од Х1а затим изаберите област минималне цене која је доступна од Х6.
Означите област Х7јер је то подручје минималне цене до које се може доћи од Х6а затим изаберите област минималне цене која је доступна од Х7.
Означите област Х8јер је то подручје минималне цене до које се може доћи од Х8.
Означите област Х5јер је то подручје минималне цене до које се може доћи од Х5.
Означите област Х2јер је то подручје минималне цене до које се може доћи од Х2.
мб вс гб
Означите област Х3јер је то подручје минималне цене до које се може доћи од Х3.
Означите област Х4а затим изаберите област минималне цене која је доступна од Х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
матроиди:
Матроид је уређени пар М(С, И) који задовољава следеће услове:
- С је коначан скуп.
- И је непразна породица подскупова од С, која се називају независни подскупови од С, таква да ако је Б ∈ И и А ∈ И. Кажемо да је И наследно ако задовољава ово својство. Приметимо да је празан скуп ∅ нужно члан И.
- Ако је А ∈ И, Б ∈ И и |А|<|b|, then there is some element x ∈ b ? a such that a∪{x}∈i. we say m satisfies the exchange property.< li>
Кажемо да је матроид М (С, И) пондерисан ако постоји придружена тежинска функција в која сваком елементу к ∈ С додељује стриктно позитивну тежину в (к). Функција тежине в се проширује на подскуп од С сумирањем :
w (A) = ∑<sub>x∈A</sub> w(x)
за било које А ∈ С.