Perkara yang mereka tanya semasa temu bual: semakan algoritma, bahagian 2

Artikel ini adalah kesinambungan ulasan ringkas saya tentang algoritma. Berikut adalah pautan ke bahagian pertama . Sebelum ini, kami melihat pelbagai algoritma pengisihan tatasusunan dan apa yang dipanggil algoritma tamak . Hari ini kita akan bercakap tentang graf dan algoritma yang berkaitan dengannya. Graf ialah salah satu struktur yang paling fleksibel dan serba boleh dalam pengaturcaraan. Graf G biasanya dinyatakan menggunakan sepasang set G = (V, R) , di mana:

• V - set bucu;
• R ialah set garis yang menghubungkan pasangan bucu.

Garis penghubung biasa dipanggil tepi : Garisan dengan anak panah - lengkok : Lazimnya, graf diwakili menggunakan gambar rajah di mana beberapa bucu disambungkan oleh tepi (arka). Graf yang disambungkan antara satu sama lain dengan lengkok yang menunjukkan arah secara langsung dipanggil terarah . Jika graf disambungkan dengan tepi, iaitu, tanpa menunjukkan arah pergerakan yang mungkin, ia menjadi tidak terarah . Ini bermakna pergerakan sepanjang mereka boleh dilakukan dalam kedua-dua arah: kedua-dua dari bucu A ke B, dan dari B ke A. Graf bersambung ialah graf di mana sekurang-kurangnya satu laluan menuju dari setiap bucu ke mana-mana bucu lain (seperti dalam contoh atas ). Jika ini tidak berlaku, graf akan terputus sambungan : Selain itu, tepi (arka) boleh diberikan pemberat - nombor yang mewakili jarak fizikal antara dua bucu (atau masa relatif peralihan antara dua bucu). Graf sedemikian dipanggil berwajaran :

3. Algoritma carian laluan (kedalaman, lebar)

Salah satu operasi asas yang dilakukan pada graf adalah untuk menentukan semua bucu yang boleh dicapai dari bucu tertentu. Bayangkan anda cuba menentukan cara untuk pergi dari satu bandar ke bandar lain dengan kemungkinan pemindahan. Sesetengah bandar boleh dikunjungi secara terus, manakala yang lain memerlukan lencongan melalui bandar lain. Terdapat banyak situasi lain di mana ia mungkin perlu untuk mencari semua bucu yang laluan boleh ditemui dari bucu tertentu. Jadi, terdapat dua cara utama untuk melintasi graf: lintasan pertama dalam dan lintasan pertama lebar , yang akan kami pertimbangkan. Kedua-dua kaedah akan memastikan lelaran ke atas semua bucu yang disambungkan. Untuk pertimbangan lanjut tentang algoritma depth-first dan breadth-first , ambil graf berikut:

Depth First Traversal

Ini adalah salah satu kaedah traversal graf yang paling biasa. Strategi carian kedalaman -pertama ini terdiri daripada pergi "mendalam" ke dalam graf sejauh mungkin, dan apabila mencapai jalan buntu, kembali ke bucu terdekat yang mempunyai bucu bersebelahan yang belum pernah dilawati sebelum ini. Algoritma ini menyimpan maklumat pada timbunan tentang tempat untuk kembali apabila kebuntuan dicapai. Peraturan untuk laluan pertama yang mendalam:

1. Lawati puncak bersebelahan, yang sebelum ini tidak dilawati, tandai dan letakkan pada timbunan.
2. Pergi ke puncak ini.
3. Ulang langkah 1.
4. Jika mustahil untuk melengkapkan langkah 1, kembali ke bucu sebelumnya dan cuba ulangi peraturan 1. Jika ini mustahil, kembali ke bucu sebelumnya, dan seterusnya, sehingga kita menemui bucu dari mana kita boleh meneruskan traversal.
5. Teruskan sehingga semua bucu berada pada timbunan.

Mari kita lihat rupa kod untuk algoritma ini dalam Java:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Stack<integer> stack;

  public Graph() { // инициализация внутрених полей
     vertexArray = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {
           adjMat[j][k] = 0;
        }
     }
     stack = new Stack<>();
  }

  public void addVertex(char lab) {
     vertexArray[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexArray[v].getLabel());
  }

  public void dfs() { // обход в глубину
     vertexArray[0].setWasVisited(true); // берётся первая вершина
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // вынуть индекс смежной веришины, еckи есть 1, нету -1
        if (v == -1) { // если непройденных смежных вершин нету
           stack.pop(); // элемент извлекается из стека
        }
        else {
           vertexArray[v].setWasVisited(true);
           displayVertex(v);
           stack.push(v); // элемент попадает на вершину стека
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexArray[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

Bahagian atas kelihatan seperti:

public class Vertex {
  private char label;  // метка А например
  public boolean wasVisited;

  public Vertex(final char label) {
     this.label = label;
     wasVisited = false;
  }

  public char getLabel() {
     return this.label;
  }

  public boolean isWasVisited() {
     return this.wasVisited;
  }

  public void setWasVisited(final boolean wasVisited) {
     this.wasVisited = wasVisited;
  }
}

Mari jalankan algoritma ini dengan bucu tertentu dan lihat sama ada ia berfungsi dengan betul:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.dfs();
  }
}

Output konsol: Oleh kerana kita mempunyai matriks bersebelahan dan dalam kaedah berjalan kita menggunakan gelung bersarang dalam gelung, kerumitan masa ialah O(N²) .

Berjalan dengan lebar

Algoritma ini, seperti depth-first traversal, adalah salah satu kaedah paling mudah dan paling asas untuk melintasi graf. Intipatinya ialah kita mempunyai bucu semasa tertentu, dari mana kita meletakkan semua bucu yang bersebelahan dan tidak dilalui ke dalam baris gilir dan pilih elemen seterusnya (yang disimpan dahulu dalam baris gilir) untuk menjadikannya semasa... Jika kita memecahkan algoritma ini menjadi peringkat, kita boleh menyerlahkan peraturan berikut:

1. Lawati puncak seterusnya yang sebelum ini tidak dilawati bersebelahan dengan puncak semasa, tandainya terlebih dahulu dan tambahkannya pada baris gilir.
2. Jika peraturan #1 tidak dapat dipenuhi, alih keluar bucu daripada baris gilir dan jadikannya bucu semasa.
3. Jika peraturan #1 dan #2 adalah mustahil, traversal selesai dan semua bucu telah dilalui (jika graf kami disambungkan).

Kelas graf hampir sama dengan kelas yang serupa daripada algoritma carian mendalam-pertama, kecuali kaedah yang memproses algoritma dan menggantikan tindanan dalaman dengan baris gilir:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Queue<integer> queue;

  public Graph() {
     vertexList = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {  // заполнение матрицы смежности нулями
           adjMat[j][k] = 0;
        }
     }
     queue = new PriorityQueue<>();
  }

  public void addVertex(char lab) {
     vertexList[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexList[v].getLabel());
  }

  public void bfc() { // обход в глубину
     vertexList[0].setWasVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

     while (!queue.isEmpty()) {
        int v = queue.remove();

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// цикл будет работать, пока все смежные вершины не будут найденны, и не будут добавлены в очередь
           vertexList[v2].wasVisited =true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexList[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

Kelas Vertex adalah sama dengan kelas daripada algoritma carian depth-first . Mari kita lakukan algoritma ini:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.bfc();
  }
}

Output konsol: Sekali lagi: kami mempunyai matriks bersebelahan dan menggunakan gelung bersarang dalam gelung, jadi O(N²) ialah kerumitan masa bagi algoritma di atas.

4. Algoritma Dijkstra

Seperti yang dinyatakan sebelum ini, graf boleh diarahkan atau tidak diarahkan . Dan seperti yang anda ingat, mereka masih boleh ditimbang . Graf berwajaran dan terarah sering ditemui dalam kehidupan sebenar: contohnya, peta bandar, di mana bandar adalah bucu, laluan di antaranya adalah jalan raya, jalan raya boleh mempunyai lalu lintas sehala - arah graf. Katakan anda terlibat dalam pengangkutan kargo dan anda perlu membuat laluan terpendek antara dua bandar yang jauh. Bagaimana anda akan melakukan ini? Salah satu masalah paling biasa yang melibatkan graf berwajaran ialah masalah memilih laluan terpendek antara dua bucu. Untuk menyelesaikan masalah ini kami menggunakan algoritma Dijkstra . Saya ingin segera ambil perhatian bahawa dengan melaksanakan algoritma Dijkstra kita akan mengetahui laluan terpendek ke semua bucu dari satu permulaan yang diberikan. Apakah peringkat algoritma ini? Saya akan cuba menjawab soalan ini. Peringkat algoritma Dijkstra:

• Peringkat 1 : cari nod, peralihan ke mana kos paling rendah. Anda berdiri di awal-awal lagi dan tertanya-tanya ke mana hendak pergi: ke nod A atau ke nod B. Berapa lama masa yang diperlukan untuk sampai ke setiap nod ini?
• Peringkat 2 : mengira berapa banyak masa yang diperlukan untuk sampai ke semua jiran B yang masih belum terjejas oleh algoritma apabila bergerak di sepanjang tepi dari B. Jika masa baharu ini ternyata kurang daripada masa lama, laluan melalui tepi B akan menjadi laluan terpendek baharu untuk bucu ini.
• Peringkat 3 : tandakan bucu B sebagai lulus.
• Langkah 4 : Pergi ke Langkah 1.

Kami akan mengulangi kitaran peringkat ini sehingga semua puncak telah dilalui. Mari kita pertimbangkan graf berwajaran berikut: Jadi, menggunakan algoritma di atas, kita akan menentukan laluan terpendek dari A ke G:

1. Untuk bucu A terdapat tiga laluan yang mungkin: ke B dengan berat 3, ke C dengan berat 5 dan ke D dengan berat 7. Menurut titik pertama algoritma, kami memilih nod dengan peralihan paling rendah kos - iaitu, kepada B.
2. Memandangkan satu-satunya bucu jiran yang tidak dilalui untuk B ialah bucu E , kami menyemak apakah laluan apabila melalui bucu ini. 3( AB ) + 6( BE ) = 9.

   Oleh itu, kami perhatikan bahawa laluan terpendek semasa ke AE = 9.

3. Memandangkan kerja kami dengan bucu B sudah selesai, kami terus memilih bucu seterusnya dengan berat minimum tepi sebelum itu.

   Daripada bucu A dan B ini boleh menjadi bucu D (7), C (5), E (6).

   C mempunyai berat tepi terkecil , jadi kita beralih ke bucu ini.

4. Seterusnya, seperti sebelum ini, kita mengetahui laluan terpendek ke bucu jiran apabila melalui C:
   • AD = 5( AC ) + 3( CD ) = 8, tetapi sejak laluan terpendek sebelumnya AC = 7, iaitu kurang daripada yang ini melalui C , kita biarkan laluan terpendek AD = 7 tidak berubah.
   • CE = 5( AC ) + 4( CE ) = 9, laluan terpendek baharu ini adalah sama dengan laluan sebelumnya jadi kami biarkan ia tidak berubah juga.
5. Daripada bucu yang tersedia terdekat, E dan D , kami memilih bucu dengan berat tepi terkecil, iaitu, D (3).
6. Kami mengetahui jalan terpendek ke jirannya - F.

   AF = 7( AD ) + 3( DF ) = 10

7. Daripada bucu E dan F yang tersedia terdekat , kami memilih bucu dengan berat tepi yang paling sedikit kepadanya, iaitu, F (3).
8. Kami mengetahui jalan terpendek ke jirannya - G.

   AG = 7( AD ) + 3( DF ) + 4( FG ) = 14

   Sebenarnya, di sini kami telah menemui laluan dari A ke G.

   Tetapi untuk memastikan bahawa ia adalah yang terpendek, kita mesti menjalankan langkah kita untuk bucu E juga .

9. Memandangkan bucu G tidak mempunyai bucu jiran yang akan membawa laluan terarah, kita hanya mempunyai bucu E yang tinggal : kita pilihnya.
10. Kami mengetahui jalan terpendek ke jiran - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, laluan ini lebih panjang daripada AG(14) terpendek sebelumnya, jadi kita biarkan laluan ini tidak berubah.

    Memandangkan tiada bucu menuju dari G , tidak masuk akal untuk menjalankan peringkat untuk bucu tertentu. Oleh itu, kerja algoritma boleh dianggap lengkap.

Seperti yang saya katakan sebelum ini, selain daripada mencari laluan terpendek untuk AG , kami mendapat laluan terpendek ke semua bucu dari bucu A (AB, AC, AD, AE, AF) . Nah, sudah tiba masanya untuk melihat bagaimana ini boleh dilaksanakan di Jawa. Pertama, mari kita lihat kelas puncak:

public class Vertex {
   private char label;
   private boolean isInTree;

   public Vertex(char label) {
       this.label = label;
       this.isInTree = false;
   }

   public char getLabel() {
       return label;
   }

   public void setLabel(char label) {
       this.label = label;
   }

   public boolean isInTree() {
       return isInTree;
   }

   public void setInTree(boolean inTree) {
       isInTree = inTree;
   }
}

Kelas bucu sebenarnya adalah sama dengan kelas bucu daripada carian mendalam-dahulu dan luas-dahulu. Untuk memaparkan laluan terpendek, kami memerlukan kelas baharu yang akan mengandungi data yang kami perlukan:

public class Path { // an object данного класса содержащий расстояние и предыдущие и пройденные вершины
   private int distance; // текущая дистанция от начальной вершины
   private List<integer> parentVertices; // текущий родитель вершины

   public Path(int distance) {
       this.distance = distance;
       this.parentVertices = new ArrayList<>();
   }

   public int getDistance() {
       return distance;
   }

   public void setDistance(int distance) {
       this.distance = distance;
   }

   public List<integer> getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List<integer> parentVertices) {
       this.parentVertices = parentVertices;
   }
}
</integer></integer></integer>

Dalam kelas ini kita boleh melihat jumlah jarak laluan dan bucu yang akan diliputi apabila melalui laluan terpendek. Dan sekarang saya ingin mempertimbangkan kelas di mana, sebenarnya, traversal terpendek graf berlaku. Jadi, kelas graf:

public class Graph {
   private final int MAX_VERTS = 10;// максимальное количество вершин
   private final int INFINITY = 100000000; // это число у нас будет служить в качестве "бесконечности"
   private Vertex vertexList[]; // список вершин
   private int relationMatrix[][]; // матрица связей вершин
   private int countOfVertices; // текущее количество вершин
   private int countOfVertexInTree; // количество рассмотренных вершин в дереве
   private List<path> shortestPaths; // список данных кратчайших путей
   private int currentVertex; // текущая вершина
   private int startToCurrent; //расстояние до currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // матрица смежности
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       countOfVertices = 0;
       countOfVertexInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) {// матрица смежности заполняется
           for (int k = 0; k < MAX_VERTS; k++) { // бесконечными расстояниями
               relationMatrix[i][k] = INFINITY; // задания значений по умолчанию
               shortestPaths = new ArrayList<>();// задается пустым
           }
       }
   }

   public void addVertex(char lab) {// задание новых вершин
       vertexList[countOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // задание ребер между вершинами, с весом между ними
   }

   public void path() { // выбор кратчайшего пути
       //  задание данных для стартовой вершины
       int startTree = 0; // стартуем с вершины 0
       vertexList[startTree].setInTree(true); // включение в состав дерева первого element
       countOfVertexInTree = 1;

       // заполнение коротких путей для вершин смежных с стартовой
       for (int i = 0; i < countOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// первым родительским элементом, будет всегда стартовая вершина
           shortestPaths.add(path);
       }
       // пока все вершины не окажутся в дереве
       while (countOfVertexInTree < countOfVertices) { // выполняем, пока количество вершин в дереве не сравняется с общим количеством вершин
           int indexMin = getMin();//получаем индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
           int minDist = shortestPaths.get(indexMin).getDistance();// минимальная дистанция вершины, из тек которые ещё не в дереве

           if (minDist == INFINITY) {
               System.out.println("В графе пристувствуют недостижимые вершины");
               break;// в случае если остались непройденными только недостижимые вершины, мы выходим из цикла
           } else {
               currentVertex = indexMin; // переводим указатель currentVert к текущей вершине
               startToCurrent = shortestPaths.get(indexMin).getDistance();// задаем дистанцию к текущей вершине
           }

           vertexList[currentVertex].setInTree(true);  //включение текущей вершины в дерево
           countOfVertexInTree++; // увеличиваем счетчик вершин в дереве
           updateShortestPaths(); // обновление списка кратчайших путей
       }

       displayPaths(); // выводим в консоль результаты
   }

   public void clean() { // очиска дерева
       countOfVertexInTree = 0;
       for (int i = 0; i < countOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // за точку старта взята "бесконечная" длина
       int indexMin = 0;
       for (int i = 1; i < countOfVertices; i++) {// для каждой вершины
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // если вершина ещё не ве дереве и её растояние меньше старого минимума
               minDist = shortestPaths.get(i).getDistance(); // задаётся новый минимум
               indexMin = i; // обновление индекса вершины содержащую минимаьную дистанцию
           }
       }
       return indexMin; //возвращает индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // стартовая вершина пропускается
       while (vertexIndex < countOfVertices) { // перебор столбцов

           if (vertexList[vertexIndex].isInTree()) { // если вершина column уже включена в дерево, она пропускается
               vertexIndex++;
               continue;
           }
           // вычисление расстояния для одного element sPath
           // получение ребра от currentVert к column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // суммирование всех расстояний
           int startToFringe = startToCurrent + currentToFringe;
           // определение расстояния текущего element vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // сравнение расстояния через currentVertex с текущим расстоянием в вершине с индексом vertexIndex
           if (startToFringe < shortPathDistance) {// если меньше, то у вершины под индексом vertexIndex будет задан новый кратчайший путь
               List<integer> newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices());//создаём копию списка родителей вершины currentVert
               newParents.add(currentVertex);// задаём в него и currentVertex How предыдущий
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // соохраняем новый маршут
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // соохраняем новую дистанцию
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // метод для вывода кратчайших путей на экран
       for (int i = 0; i < countOfVertices; i++) {
           System.out.print(vertexList[i].getLabel() + " = ");
           if (shortestPaths.get(i).getDistance() == INFINITY) {
               System.out.println("0");
           } else {
               String result = shortestPaths.get(i).getDistance() + " (";
               List<integer> parents = shortestPaths.get(i).getParentVertices();
               for (int j = 0; j < parents.size(); j++) {
                   result += vertexList[parents.get(j)].getLabel() + " -> ";
               }
               System.out.println(result + vertexList[i].getLabel() + ")");
           }
       }
   }
}
</integer></integer></path>

Sebenarnya, itu semua keajaiban =) Nah, sekarang, mari kita lihat algoritma ini dalam tindakan:

public class Solution {

   public static void main(String[] args) {
       Graph graph = new Graph();
       graph.addVertex('A');
       graph.addVertex('B');
       graph.addVertex('C');
       graph.addVertex('D');
       graph.addVertex('E');
       graph.addVertex('F');
       graph.addVertex('G');

       graph.addEdge(0, 1, 3);
       graph.addEdge(0, 2, 5);
       graph.addEdge(0, 3, 7);
       graph.addEdge(1, 4, 6);
       graph.addEdge(2, 4, 4);
       graph.addEdge(2, 3, 3);
       graph.addEdge(3, 5, 3);
       graph.addEdge(4, 6, 6);
       graph.addEdge(5, 6, 4);

       System.out.println("Элементы имеют кратчайшие пути из точки A: ");
       graph.path();
       graph.clean();
   }
}

Dan output dalam konsol: Kerumitan masa algoritma ini tidak lebih daripada O(N²) kerana kita mempunyai gelung bersarang dalam gelung. Baiklah, itu sahaja untuk saya hari ini, terima kasih atas perhatian anda!