Problemy komiwojażera dotyczą sprzedawcy i zbioru miast. Sprzedawca musi odwiedzić każde z miast, zaczynając od określonego (np. rodzinnego) i wrócić do tego samego miasta. Problem polega na tym, że podróżujący sprzedawca musi zminimalizować całkowitą długość podróży.
Załóżmy, że miasta to x1X2..... XNgdzie koszt cjaoznacza koszt podróży z miasta xIdo xJ. Problem podróżującego sprzedawcy polega na znalezieniu trasy rozpoczynającej się i kończącej w punkcie x1który obejmie wszystkie miasta przy minimalnych kosztach.
Przykład: Agent prasowy codziennie zrzuca gazetę na przydzielony obszar w taki sposób, że musi objąć wszystkie domy na danym obszarze przy minimalnych kosztach podróży. Oblicz minimalny koszt podróży.
Obszar przydzielony agentowi, w którym musi on wrzucić gazetę, pokazano na rys.:
Rozwiązanie: Macierz sąsiedztwa kosztów grafu G wygląda następująco:
kosztja=
Wycieczka rozpoczyna się od obszaru H1a następnie wybierz obszar minimalnego kosztu osiągalny z H1.
Liczba całkowita Java na ciąg
Oznacz obszar H6ponieważ jest to obszar minimalnych kosztów osiągalny z H1a następnie wybierz obszar minimalnego kosztu osiągalny z H6.
Zaznacz obszar H7ponieważ jest to obszar minimalnych kosztów osiągalny z H6a następnie wybierz obszar minimalnego kosztu osiągalny z H7.
Zaznacz obszar H8ponieważ jest to obszar minimalnych kosztów osiągalny z H8.
Oznacz obszar H5ponieważ jest to obszar minimalnych kosztów osiągalny z H5.
Oznacz obszar H2ponieważ jest to obszar minimalnych kosztów osiągalny z H2.
Zaznacz obszar H3ponieważ jest to obszar minimalnych kosztów osiągalny z H3.
Oznacz obszar H4a następnie wybierz obszar minimalnego kosztu osiągalny z H4to jest H1Zatem stosując strategię zachłanną otrzymujemy co następuje.
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>.
Zatem minimalny koszt podróży = 4 + 3 + 2 + 4 + 3 + 2 + 1 + 6 = 25
Matroidy:
Matroida to uporządkowana para M(S, I) spełniająca następujące warunki:
rj12 kontra rj11
- S jest zbiorem skończonym.
- I jest niepustą rodziną podzbiorów S, zwanych niezależnymi podzbiorami S, takimi, że jeśli B ∈ I i A ∈ I. Mówimy, że I jest dziedziczny, jeśli spełnia tę własność. Zauważ, że zbiór pusty ∅ jest koniecznie członkiem I.
- Jeśli A ∈ I, B ∈ I 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ówimy, że matroida M (S, I) jest ważona, jeśli istnieje powiązana funkcja wagi w, która przypisuje ściśle dodatnią wagę w (x) każdemu elementowi x ∈ S. Funkcja wagi w rozciąga się na podzbiór S przez sumowanie :
w (A) = ∑<sub>x∈A</sub> w(x)
dla dowolnego A ∈ S.