Soal Jawab daripada temu duga kerja: algoritma di Jawa, bahagian 1

Projek pembangunan menggunakan pelbagai algoritma lebih kerap daripada yang anda fikirkan. Sebagai contoh, katakan kita perlu mengisih beberapa data mengikut parameter tertentu (lajur) supaya kita boleh menavigasi data tanpa banyak usaha. Oleh itu, tidak pelik sama sekali untuk penemuduga kerja bertanya kepada anda tentang algoritma asas tertentu dan mungkin memberi tugas untuk melaksanakannya menggunakan kod. Dan kerana anda berada di laman web ini, saya akan sangat berani untuk menganggap bahawa anda menulis dalam Java. Itulah sebabnya hari ini saya mencadangkan agar anda membiasakan diri dengan beberapa algoritma asas dan dengan contoh khusus tentang cara melaksanakannya di Java. Dengan "beberapa", maksud saya:

1. Gambaran keseluruhan algoritma pengisihan tatasusunan:
   • jenis gelembung,
   • jenis pemilihan,
   • jenis sisipan,
   • Jenis cangkang,
   • quicksort,
   • gabungan jenis,
2. Algoritma tamak
3. Algoritma pencarian laluan
   • carian mendalam-pertama
   • carian luas-pertama
4. Algoritma Laluan Terpendek Pertama Dijkstra

Nah, tanpa berlengah lagi, mari kita mula berniaga.

1. Gambaran keseluruhan algoritma pengisihan

Isih gelembung

Algoritma pengisihan ini dikenali terutamanya kerana kesederhanaannya, tetapi ia juga merupakan salah satu yang paling perlahan. Sebagai contoh, mari kita pertimbangkan jenis gelembung untuk nombor dalam tertib menaik. Mari kita bayangkan urutan nombor rawak. Kami akan melakukan langkah berikut pada nombor ini, bermula dari permulaan urutan:

• bandingkan dua nombor;
• jika nombor di sebelah kiri lebih besar, maka tukarkannya;
• gerakkan satu kedudukan ke kanan.

Selepas melakukan langkah-langkah ini pada keseluruhan jujukan, kami akan mendapati bahawa nombor terbesar adalah pada penghujung siri nombor kami. Kemudian kami membuat satu lagi laluan ke atas jujukan, melaksanakan langkah yang sama seperti di atas. Tetapi kali ini kami tidak akan memasukkan elemen terakhir senarai, kerana ia adalah nombor terbesar dan sudah pun tepat di tempat yang sepatutnya apabila nombor diisih. Sekali lagi, kami akan mengalihkan nombor terbesar seterusnya ke penghujung jujukan kami. Sudah tentu, ini bermakna dua nombor terbesar berada di tempat yang sepatutnya. Sekali lagi, kami membuat hantaran ke atas jujukan, tidak termasuk elemen yang sudah berada di tempatnya, sehingga semua elemen berada dalam susunan yang diperlukan. Mari kita lihat cara isihan gelembung dilaksanakan dalam kod Java:

public class Solution {
   public static void main(String[] args) {
    int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
    bubbleSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void  bubbleSort(int[] array) {
       for(int i = array.length -1; i > 1; i--) {
         for (int j = 0; j < i; j++) { //
             if (array[j] > array[j+1]) {
                 int temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
             }
         }
       }
   }
}

Seperti yang anda lihat, tidak ada yang rumit di sini. Segala-galanya kelihatan hebat dan ia akan menjadi jika bukan kerana satu kekurangan — jenis gelembung adalah sangat, sangat perlahan. Kerumitan masa ialah O(N²), kerana kita mempunyai gelung bersarang. Gelung luar ke atas elemen dilakukan N kali. Gelung dalam juga dilaksanakan N kali. Hasilnya, kita mendapat N*N, atau N², lelaran.

Isihan pilihan

Algoritma ini serupa dengan jenis gelembung, tetapi ia berfungsi lebih pantas sedikit. Sekali lagi, sebagai contoh, mari kita ambil urutan nombor yang ingin kita susun dalam tertib menaik. Intipati algoritma ini adalah untuk mengulangi semua nombor secara berurutan dan memilih elemen terkecil, yang kami ambil dan tukar dengan elemen paling kiri (elemen ke-0). Di sini kita mempunyai situasi yang serupa dengan isihan gelembung, tetapi dalam kes ini elemen yang diisih kita akan menjadi yang terkecil. Oleh itu, laluan seterusnya melalui elemen akan bermula dari elemen dengan indeks 1. Kami akan mengulangi pas ini sehingga semua elemen telah diisih. Pelaksanaan di Jawa:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {

       for (int i = 0; i < array.length-1; i++) { // An ordinary outer loop
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // Put the sorted number in the proper cell
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

Algoritma ini lebih baik daripada jenis gelembung, kerana di sini bilangan anjakan yang diperlukan dikurangkan daripada O(N²) kepada O(N). Kami tidak memacu satu elemen melalui keseluruhan senarai, tetapi bilangan perbandingan masih O(N²).

Isihan sisipan

Kami mempertimbangkan satu lagi urutan nombor yang ingin kami susun dalam tertib menaik. Algoritma ini terdiri daripada meletakkan penanda, di mana semua elemen di sebelah kiri penanda sudah sebahagiannya disusun antara mereka. Pada setiap langkah algoritma, salah satu elemen akan dipilih dan diletakkan pada kedudukan yang dikehendaki dalam urutan yang disusun separa. Oleh itu, bahagian yang disusun akan berkembang sehingga semua elemen telah diperiksa. Adakah anda tertanya-tanya bagaimana anda mendapatkan subset elemen yang telah diisih dan bagaimana kami menentukan tempat untuk meletakkan penanda? Tetapi tatasusunan yang terdiri daripada elemen pertama sudah disusun, bukan? Mari kita lihat pelaksanaan di Jawa:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       insertionSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void insertionSort(int[] array) {

       for (int i = 1; i < array.length; i++) { // i is the dividing marker
           int temp = array[i]; // Make a temporary copy of the marked element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // Until a smaller element is found
               array[j] = array[j - 1]; // We shift the element to the right
               --j;
           }
           array[j] = temp;   // Insert the marked element in its proper place
       }
   }
}

Jenis jenis ini lebih baik daripada yang diterangkan di atas, kerana walaupun pada hakikatnya ia mempunyai masa berjalan O(N²) yang sama, algoritma ini adalah dua kali lebih pantas daripada isihan gelembung dan lebih pantas sedikit daripada isihan pemilihan.

Isih cangkerang

Jenis ini pada asasnya ialah jenis sisipan yang diubah suai. Apa yang saya cakapkan? Mari kita dahulukan perkara pertama. Kita mesti terlebih dahulu memilih selang. Terdapat banyak pendekatan untuk membuat pilihan ini. Kami tidak akan menjelaskan perkara ini secara terperinci. Mari bahagikan tatasusunan kita kepada separuh dan dapatkan beberapa nombor — ini akan menjadi selang kita. Jadi, jika kita mempunyai 9 elemen dalam tatasusunan kita, maka selang kita akan menjadi 9/2 = 4.5. Kami membuang bahagian pecahan dan mendapat 4, kerana indeks tatasusunan hanya boleh menjadi integer. Kami akan menggunakan selang ini untuk membentuk kumpulan kami. Jika unsur mempunyai indeks 0, maka indeks unsur seterusnya dalam kumpulannya ialah 0+4, iaitu 4. Unsur ketiga akan mempunyai indeks 4+4, yang keempat — 8+4, dan seterusnya. Dalam kumpulan kedua, elemen pertama akan menjadi 1,5,9... Dalam kumpulan ketiga dan keempat, keadaan akan sama. Akibatnya, daripada tatasusunan nombor {6,3,8,8,6,9,4,11,1} kita mendapat empat kumpulan: I — {6,6,1} II — {3,9} III — {8,4 } IV — {8,11} Mereka mengekalkan tempat mereka dalam tatasusunan umum, tetapi kami telah menandakan sebagai ahli kumpulan yang sama: {6,3,8,8,6,9,4,11,1} Seterusnya, sisipan isihan digunakan pada kumpulan ini, dan kemudian ia kelihatan seperti ini: I — {1,6,6} II — {3,9} III — {4,8} IV — {8,11} Dalam tatasusunan umum, sel yang diduduki oleh kumpulan akan kekal sama, tetapi susunan dalaman mereka akan berubah, mengikut susunan kumpulan di atas: {1,3,4,8,6,9,8,11,6} Tatasusunan telah menjadi sedikit lagi yang dipesan, bukan? Selang seterusnya akan dibahagikan dengan 2: 4/2 = 2 Kami mempunyai dua kumpulan: I — {1,4,6,8,6} II — {3,8,9,11} Dalam tatasusunan umum, kami mempunyai : {1,3,4,8,6,9,8,11,6} Kami menjalankan algoritma isihan sisipan pada kedua-dua kumpulan dan mendapatkan tatasusunan ini: {1,3,4,8,6,9,6, 11, 8} Kini tatasusunan kami hampir diisih. Kami perlu melakukan lelaran akhir algoritma: kami membahagikan selang dengan 2: 2/2 = 1. Kami mendapat kumpulan yang terdiri daripada keseluruhan tatasusunan: {1,3,4,8,6,9,6,11 ,8} Menjalankan algoritma isihan sisipan pada itu, kita mendapat: {1,3,4,6,6,8,8,9,11} Mari kita lihat bagaimana kita boleh menghidupkan jenis ini dalam kod Java:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {
       int length = array.length;
       int step = length / 2;
       while (step > 0) {
           for (int numberOfGroup = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // Shrink the interval
       }
   }
}

Pada masa ini, prestasi Shellsort tidak mudah untuk dicirikan, kerana hasilnya berbeza dalam situasi yang berbeza. Anggaran eksperimen berjulat daripada O(N ^3/2 ) hingga O(N ^7/6 ).

Quicksort

Ini adalah salah satu algoritma yang paling popular, jadi ia patut diberi perhatian khusus. Intipati algoritma ini ialah elemen pangsi dipilih dalam senarai elemen. Kami mengisih semua elemen lain berbanding dengan elemen pangsi. Nilai kurang daripada elemen pangsi berada di sebelah kiri. Nilai yang lebih besar daripada yang ada di sebelah kanan. Seterusnya, elemen pangsi juga dipilih di bahagian kanan dan kiri, dan perkara yang sama berlaku: nilai diisih relatif kepada elemen ini. Kemudian elemen pangsi dipilih dalam bahagian yang baru dibentuk, dan seterusnya sehingga kita mendapat urutan yang disusun. Pelaksanaan Java berikut bagi algoritma ini menggunakan rekursi:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       fastSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void fastSort(int[] array) {
       recursionFastSort(array, 0, array.length - 1);
   }


   public static void recursionFastSort(int[] array, int min, int max) {
       if (array.length == 0) // Condition for exiting recursion if the array length is 0
           return;

       if (min> = max) // Terminate the recursion, since there is nothing to divide
           return;


       int middle = min + (max - min) / 2; // Select the middle
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) { // Swap places
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // Make a recursive call on the elements that are less than middle
           recursionFastSort(array, min, j);

       if (max > i) // Make a recursive call on the elements larger than middle
           recursionFastSort(array, i, max);
   }
}

Tidak syak lagi, algoritma quicksort adalah yang paling popular, kerana dalam kebanyakan situasi ia berjalan lebih pantas daripada yang lain. Kerumitan masanya ialah O(N*logN).

Gabungkan jenis

Jenis ini juga popular. Ia adalah salah satu daripada banyak algoritma yang bergantung pada prinsip "bahagi dan takluk". Algoritma sedemikian mula-mula membahagikan masalah kepada bahagian yang boleh diurus (quicksort ialah satu lagi contoh algoritma sedemikian). Jadi apakah intipati algoritma ini?

Bahagikan:

Tatasusunan dibahagikan kepada dua bahagian dengan saiz yang lebih kurang sama. Setiap satu daripada dua bahagian ini dibahagikan kepada dua lagi, dan seterusnya sehingga bahagian terkecil yang tidak boleh dibahagikan kekal. Kami mempunyai bahagian terkecil yang tidak boleh dibahagikan apabila setiap tatasusunan mempunyai satu elemen, iaitu tatasusunan yang telah diisih.

Menakluk:

Di sinilah kita memulakan proses yang memberikan algoritma namanya: merge. Untuk melakukan ini, kami mengambil dua tatasusunan disusun yang terhasil dan menggabungkannya menjadi satu. Dalam kes ini, elemen pertama yang terkecil daripada dua tatasusunan ditulis ke dalam tatasusunan yang terhasil. Operasi ini diulang sehingga semua elemen dalam dua tatasusunan ini telah disalin. Iaitu, jika kami mempunyai dua tatasusunan minimum {6} dan {4}, kami membandingkan nilainya dan menjana hasil gabungan ini: {4,6}. Jika kami telah mengisih tatasusunan {4,6} dan {2,8}, kami mula-mula membandingkan nilai 4 dan 2, dan kemudian kami menulis 2 ke dalam tatasusunan yang terhasil. Selepas itu, 4 dan 8 akan dibandingkan, dan kami akan menulis 4. Akhirnya, 6 dan 8 akan dibandingkan. Sehubungan itu, kami akan menulis 6, dan hanya selepas itu kami akan menulis 8. Hasilnya, kami mendapat tatasusunan gabungan berikut: {2,4,6,8}. Bagaimanakah ini akan kelihatan dalam kod Java? Untuk menjalankan algoritma ini, adalah mudah bagi kami untuk menggunakan rekursi:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       testArr = mergeSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static int[] mergeSort(int[] array1) {
       int[] sortArr = Arrays.copyOf(array1, array1.length); // Array for sorting
       int[] bufferArr = new int[array1.length];// Buffer array
       return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
           return sortArr;
       }

       // Make a recursive call to get two sorted arrays:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Merge the sorted arrays:
       int firstIndex = startIndex;
       int secondIndex = middle;
       int destIndex = startIndex;
       int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
       while (firstIndex < middle && secondIndex < endIndex) {
           result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
                   ? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
       }
       while (firstIndex < middle) {
           result[destIndex++] = firstSortArr[firstIndex++];
       }
       while (secondIndex < endIndex) {
           result[destIndex++] = secondSortArr[secondIndex++];
       }
       return result;
   }
}

Seperti dalam isihan pantas, kami mengalihkan kaedah rekursif ke kaedah perantaraan supaya pengguna hanya perlu membekalkan tatasusunan untuk diisih dan tidak perlu risau tentang menyediakan sebarang hujah lalai tambahan. Algoritma ini mempunyai persamaan dengan quicksort, dan tidak menghairankan kelajuan pelaksanaannya adalah sama: O(N*logN).

2. Algoritma tamak

Algoritma tamak ialah pendekatan di mana keputusan optimum tempatan dibuat pada setiap peringkat, dengan andaian bahawa penyelesaian akhir juga akan optimum. Penyelesaian "optimum" akan menjadi penyelesaian yang menawarkan faedah yang paling jelas dan segera pada mana-mana langkah/peringkat tertentu. Untuk meneroka algoritma ini, mari kita ambil masalah yang agak biasa — masalah ransel. Berpura-puralah seketika bahawa anda seorang pencuri. Anda telah memecah masuk kedai pada waktu malam dengan ransel (beg galas). Di hadapan anda terdapat beberapa barangan yang anda boleh curi. Tetapi pada masa yang sama, beg beg anda mempunyai kapasiti terhad. Ia boleh membawa tidak lebih daripada 30 unit berat. Anda juga ingin membawa pergi set barang paling berharga yang akan dimuatkan ke dalam beg galas. Bagaimana anda menentukan apa yang perlu dimasukkan ke dalam beg anda? Jadi,

1. Pilih barang yang paling mahal yang belum diambil.
2. Jika ia muat dalam beg beg, masukkannya. Jika tidak, biarkan ia.
3. Adakah kita sudah mencuri segala-galanya? Jika tidak, kita kembali ke langkah 1. Jika ya, maka kita pergi cepat dari kedai, kerana kita telah mencapai apa yang kita datang untuk lakukan.

Mari kita lihat ini, tetapi di Jawa. Beginilah rupa kelas Item:

public class Item implements Comparable {
   private String name;
   private int weight;
   private int value;

   public Item(String name, int weight, int value) {
       this.name = name;
       this.weight = weight;
       this.value = value;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getValue() {
       return value;
   }

   @Override
   public int compareTo(Item o) {
       return this.value > o.value ? -1 : 1;
   }
}

Tiada apa-apa yang istimewa di sini: tiga medan (nama, berat, nilai) yang mentakrifkan ciri item. Selain itu, seperti yang anda lihat, antara muka Sebanding dilaksanakan untuk membolehkan kami mengisih Item kami mengikut harga. Seterusnya, kami akan melihat kelas Beg, yang mewakili ransel kami:

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentValue;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentValue = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentValue() {
       return currentValue;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentValue += item.getValue();
   }
}

• maxWeight ialah kapasiti beg galas kami, yang ditetapkan apabila kami mencipta objek;
• item mewakili objek dalam beg galas kami;
• currentWeight , currentValue — medan ini menyimpan berat semasa dan nilai semua item dalam beg galas, yang kami tambah apabila kami menambah item baharu dalam kaedah addItem.

Bagaimanapun, mari kita pergi ke kelas di mana semua tindakan berlaku:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("Guitar", 7, 800));
       items.add(new Item("Iron", 6, 500));
       items.add(new Item("Tea pot", 3, 300));
       items.add(new Item("Lamp", 4, 500));
       items.add(new Item("Television", 15, 2000));
       items.add(new Item("Vase", 2, 450));
       items.add(new Item("Mixer", 2, 400));
       items.add(new Item("Blender", 3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
               ". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
} 

Pertama, kami membuat senarai item dan menyusunnya. Kami mencipta objek beg dengan kapasiti 30 unit. Seterusnya, kami menghantar item dan objek beg ke kaedah fillBackpack, yang mengisi ransel mengikut algoritma tamak kami:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

Ia agak mudah: kami mula menyemak senarai item yang diisih mengikut kos dan memasukkannya ke dalam beg jika kapasitinya membenarkan. Jika tidak ada ruang yang mencukupi, maka item tersebut akan dilangkau dan kami akan terus melintasi item yang lain sehingga kami sampai ke penghujung senarai. Sebaik sahaja kami menjalankan utama, berikut ialah output konsol yang kami akan dapat: Ini ialah contoh algoritma tamak: pada setiap langkah, penyelesaian optimum tempatan dipilih, dan pada akhirnya, anda mendapat penyelesaian optimum global. Dalam kes kami, pilihan terbaik adalah item yang paling mahal. Tetapi adakah ini penyelesaian terbaik? Tidakkah anda fikir adalah mungkin untuk menambah baik sedikit penyelesaian kami untuk mengisi beg galas kami dengan item yang mempunyai jumlah nilai yang lebih besar? Mari kita lihat bagaimana ini boleh dilakukan.

public static void effectiveFillBackpack(Bag bag, List items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getValue() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

Di sini kita mula-mula mengira nisbah nilai kepada berat untuk setiap item. Ini memberitahu kami nilai setiap unit item tertentu. Dan kemudian kami menggunakan nisbah ini untuk mengisih item kami dan menambahkannya pada beg kami. Mari jalankan perkara berikut:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("The weight of the knapsack is " + secondBag.getCurrentWeight() +
       ". The total cost of items in the knapsack is " + secondBag.getCurrentValue());

Kami mendapat output konsol ini: Sedikit lebih baik, bukan? Algoritma tamak membuat pilihan optimum tempatan pada setiap langkah, dengan harapan bahawa penyelesaian akhir juga akan optimum. Andaian ini tidak selalunya sah, tetapi untuk banyak tugas, algoritma tamak memang menghasilkan penyelesaian akhir yang optimum. Kerumitan masa algoritma ini ialah O(N). Agak bagus, ya?