Strona główna » Algorytmy » Artykuły » Minimalizacja Łączenia Par
 

Minimalizacja Łączenia Par

Opis

Minimalizacja łączenia par polega na połączeniu wszystkich elementów tablicy przy jak najmniejszym koszcie. Zakładamy, że koszt połączenia pary to suma wartości łączonych liczb. Z kolei połączenie pary polega na zastąpieniu łączonych elementów ich sumą.

Przykład

Weźmy przykładowo tablicę liczb całkowitych L:={3, 2, 5, 7}.

ListaŁączone liczbyKoszt
{3, 2, 5, 7}2 i 35
{5, 5, 7}5 i 510
{10, 7}10 i 717

Sumując ostatnią kolumnę uzyskujemy całkowity koszt: 5 + 10 + 17 = 32. Jest to rozwiązanie optymalne, ponieważ uzyskaliśmy najmniejszy możliwy koszt.

Liczby możemy połączyć także nieoptymalnie. Oznacza to, że połączymy wszystkie pary, ale uzyskamy większy koszt:

ListaŁączone liczbyKoszt
{3, 2, 5, 7}5 i 712
{3, 2, 12}3 i 1215
{2, 15}2 i 1517

Ostateczny koszt to 44. To więcej niż w pierwszym przykładzie.

Spostrzeżenia

Jeśli w danym kroku chcemy uzyskać jak najmniejszy koszt to musimy połączyć dwie najmniejsze liczby na liście. Załóżmy, że zawsze łączymy najmniejszą z liczbą równą lub większą. Wtedy jeśli mamy więcej niż jedno wystąpienie liczby z pary to wystarczy, że wybierzemy dowolną z nich.

Zastanówmy się teraz nad złożonością takiego algorytmu. Operacją dominującą jest tu zdecydowanie porównanie. W i-tym kroku będziemy wykonywać n - i porównań, gdzie n to długość tablicy. Na podstawie tego możemy stwierdzić, że złożoność czasowa naszego algorytmu będzie kwadratowa rzędu Θ(n2). Z kolei złożoność pamięciowa będzie Θ(1). Potrzebujemy tylko zmiennej do przechowywania aktualnego kosztu.

Implementacja

Przed przystąpieniem do implementacji trzeba określić dwie strategie. Pierwsza strategia dotyczy znalezienia dwóch najmniejszych liczb w ciągu. Przyjęta przeze mnie w rozwiązaniu strategia polega na zadeklarowaniu dwóch zmiennych, które będą przechowywać pozycje najmniejszych liczb. Przed rozpoczęciem porównań zakładam, że najmniejszy liczby to pierwsza i druga na liście. Dla każdego elementu prócz dwóch pierwszych: porównuje z pierwszą zmienną. Jeśli jest mniejsza to zapamiętuje tę pozycję. Jeśli jednak nie to porównuje z drugą dotychczas najmniejszą liczbą. Jeśli jest mniejsza to zastępuje drugą liczbę aktualnie rozpatrywaną. W ten sposób zawsze uzyskamy dwie najmniejsze liczby.

Druga strategia dotyczy zmniejszania listy. Zakładamy, że podaną listę możemy modyfikować. (Jeśli jednak chcemy tego uniknąć to wystarczy dodać nową funkcję nadrzędną lub na początku tej funkcji dodać kopiowanie listy.) Deklarowanie za każdym razem może okazać się czasochłonne, dlatego po znalezieniu najmniejszych liczb: sumę liczb (koszt) wstawimy w miejsce liczby najmniejszej znajdującej się bliżej początku. Z kolei liczbę na pozycji drugiej najmniejszej liczby zamienimy z ostatnim elementem na liście, a potem zmniejszymy długość listy o 1.

  1. void swapInt(int &a, int &b){
  2.   int temp = a;
  3.   a = b;
  4.   b = temp;
  5. }

Podczas wykonywania algorytmu będziemy zamieniać wartości miejscami w pamięci. Funkcja swapInt() pozwoli nam zaoszczędzić kilka linijek kodu.

  1. int wyliczKoszt(int* lista, int n){
  2.   int koszt = 0;

(1.) Nasza funkcja przyjmuje listą liczb całkowitych lista oraz jej długość n. Zwracaną wartością będzie koszt. (2.) Na początek deklarujemy, że koszt całkowity wyniósł 0.

  1.   while (n > 1){
  2.     int min1 = 0, min2 = 1;
  3.     for(int i = 2; i < n; i++){
  4.       if(lista[i] < lista[min1]){
  5.         min1 = i;
  6.       } else if(lista[i] < lista[min2]){
  7.         min2 = i;
  8.       }
  9.     }

(3.) Funkcję wywołujemy dopóki długość listy jest większa niż 1. Dopóki n > 1 to (4.) Deklarujemy zmienne min1 i min2. Będziemy przechowywać w nich pozycję dwóch najmniejszych liczb do tej pory znalezionych. Początkowo wskazują na dwie pierwsze wartości listy. (5.) Dla każdego elementu począwszy od drugiego: (6.) porównujemy z element na pozycji min1. Jeśli element na pozycji i jest mniejszy to aktualizujemy min1. (8.) Porównanie elementu i-tego z min2 wykonujemy tylko kiedy nie aktualizowaliśmy min1. (9.) Jeśli i-ty jest mniejszy od elementu na pozycji min2 to go aktualizujemy.

  1.     koszt+=lista[min1]+lista[min2];
  2.     if(min2 < min1)
  3.       swapInt(min1, min2);
  4.     lista[min1] = lista[min1]+lista[min2];
  5.     swapInt(lista[min2], lista[n-1]);
  6.     n--;
  7.   }
  8.   return koszt;
  9. }

(12.) Zwiększamy koszt o sumę elementu na pozycji min1 i min2. Zgodnie ze strategią pozycja min1 musi być mniejsza od min2, dlatego (13.) jeśli jest odwrotnie to (14.) zamieniamy wartości miejscami. (15.) Na pozycji min1 wstawiamy sumę znalezionych liczb. (16.) Pozycję min2 zamieniamy z pozycją n - 1 (ostatnią). (17.) Na zakończenia pętli zmniejszamy długość listy n o 1. Na sam koniec funkcji (19.) zwracamy koszt.

Testowanie funkcji

Napisane funkcje można przetestować przy pomocy poniższej funkcji main(), która wczyta od użytkownika ile będzie liczb na liście n, a następnie n wartości. Po wczytaniu program wypisze minimalny koszt.

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   int* L = new int[n];
  5.     for(int i = 0; i < n; i++){
  6.     cin >> L[i];
  7.   }
  8.   cout << wyliczKoszt(L, n) << endl;
  9.   delete[] L;
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Napisz rekurencyjną wersję funkcji minimalizującą koszt łączenia par.