Problem podróżującego sprzedawcy
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 x 1 X 2 ..... X N gdzie koszt c ja oznacza koszt podróży z miasta x I do x J . Problem podróżującego sprzedawcy polega na znalezieniu trasy rozpoczynającej się i kończącej w punkcie x 1 któ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:
koszt ja =
Wycieczka rozpoczyna się od obszaru H 1 a następnie wybierz obszar minimalnego kosztu osiągalny z H 1 .
Oznacz obszar H 6 ponieważ jest to obszar minimalnych kosztów osiągalny z H 1 a następnie wybierz obszar minimalnego kosztu osiągalny z H 6 .
Zaznacz obszar H 7 ponieważ jest to obszar minimalnych kosztów osiągalny z H 6 a następnie wybierz obszar minimalnego kosztu osiągalny z H 7 .
Zaznacz obszar H 8 ponieważ jest to obszar minimalnych kosztów osiągalny z H 8 .
Oznacz obszar H 5 ponieważ jest to obszar minimalnych kosztów osiągalny z H 5 .
Oznacz obszar H 2 ponieważ jest to obszar minimalnych kosztów osiągalny z H 2 .
Zaznacz obszar H 3 ponieważ jest to obszar minimalnych kosztów osiągalny z H 3 .
Oznacz obszar H 4 a następnie wybierz obszar minimalnego kosztu osiągalny z H 4 to jest H 1 Zatem 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:
- 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.
