Проблем са продавцем на путовању
Проблеми са трговачким путницима се придржавају продавца и низа градова. Продавац мора да посети сваки од градова почевши од одређеног (нпр. родног града) и да се врати у исти град. Изазов проблема је у томе што путујући продавац треба да минимизира укупну дужину путовања.
Претпоставимо да су градови к 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)
за било које А ∈ С.
