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 1

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.

Przykład 2

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 porównanie. W i-tym kroku będziemy wykonywać n - i porównań, gdzie n to długość tablicy. Na podstawie tego można stwierdzić, że złożoność czasowa algorytmu będzie kwadratowa rzędu O(n2). Z kolei złożoność pamięciowa będzie O(1).

Implementacja

Wybór strategii

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.

Kod

Przedstawiona poniżej funkcja wyliczKoszt() dla podanej tablicy zwraca minimalny koszt łączenia elementów.

C#
C++
  1. static int wyliczKoszt(int[] lista) {
  2.   int koszt = 0, n = lista.Length;
  3.   while (n > 1) {
  4.     int min1 = 0, min2 = 1;
  5.     for (int i = 2; i < n; i++) {
  6.       if (lista[i] < lista[min1]) {
  7.         min1 = i;
  8.         if (lista[min1] < lista[min2])
  9.           Zamień(ref min1, ref min2);
  10.       }
  11.     }
  12.     koszt += lista[min1] + lista[min2];
  13.     lista[min1] = lista[min1] + lista[min2];
  14.     Zamień(ref lista[min2], ref lista[n - 1]);
  15.     n--;
  16.   }
  17.   return koszt;
  18. }

(2.) Początkowo należy ustalić koszt na 0 i (3.) sprawdzić czy są pary do łączenia. Jeśli tak to (4.) przyjmujemy dwa pierwsze elementy za najmniejsze, a następnie (5. - 11.) weryfikujemy to przeglądając pozostałe elementy i aktualizując, które elementy są najmniejsze. Dla znalezionej pary: (12.) powiększ koszt, (13.) nową sumę umieść na liście zamiast pierwszej minimalnej wartości, a następnie (14.) przesuń drugą wartość na koniec tablicy i (15.) zmniejsz informację ile pozostało elementów do złączenia.

Testowanie funkcji

Napisane funkcje można przetestować przy pomocy poniższego kodu, który wczyta od użytkownika ile będzie liczb na liście n, a następnie n wartości. Po wczytaniu program wypisze minimalny koszt łączenia wczytanych liczb.

C#
C++
  1. static void Main(string[] args) {
  2.   Console.Write("Ile elementow ma tablica?\n n = ");
  3.   int n = Convert.ToInt32(Console.ReadLine());
  4.   int[] L = new int[n];
  5.   Console.WriteLine("Podaj elementy:");
  6.   for (int i = 0; i < n; i++)
  7.     L[i] = Convert.ToInt32(Console.ReadLine());
  8.   Console.WriteLine(wyliczKoszt(L));
  9.   Console.ReadKey();
  10. }

Zadania

Zadanie 1

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