[Tự học lập trình Android] Bài 3: Các thành phần của ứng dụng Android

in , /

Thành phần ứng dụng là các khối cơ bản để xây dựng một ứng dụng Android. Các thành phần này được liên kết lỏng lẻo bởi các ứng dụng bởi tập tin AndroidManifest.xml, tập tin AndroidManifest.xml mô tả mỗi thành phần của ứng dụng và cách chúng tương tác với nhau.
Có bốn thành phần chính có thể được sử dụng trong một ứng dụng Android:


Thành phần
Đặc tả
Activities
Chúng gọi giao diện người dùng và xử lý các tương tác người dùng với màn hình điện thoại thông minh
Services
Chúng xử lý nền kết hợp với một ứng dụng.
Broadcast Receivers
Chúng xử lý thông tin liên lạc giữa hệ điều hành Android và các ứng dụng.
Content Providers
Chúng xử lý dữ liệu và các vấn đề quản lý cơ sở dữ liệu.

1. Activities (Hoạt động)
Một Activities đại diện cho một màn hình duy nhất với một giao diện người dùng. Ví dụ, một ứng dụng email có thể có một hoạt động cho thấy một danh sách các email mới, một hoạt động để soạn một email, và một hoạt động để đọc email. Nếu một ứng dụng có nhiều hơn một hoạt động, sau đó một trong số chúng được đánh dấu là hoạt động được hiển thị khi ứng dụng được khởi chạy.
Một Activities được thực hiện như một lớp con của lớp Activity như sau:
public class MainActivity extends Activity {
 ...
}

2. Services (Dịch vụ)
Một Services là một thành phần chạy trong nền để thực hiện các hoạt động lâu dài. Ví dụ, một dịch vụ có thể chơi nhạc ở chế độ nền trong khi người dùng đang ở một ứng dụng khác nhau, hoặc nó có thể lấy dữ liệu qua mạng mà không ngăn chặn người dùng tương tác với một hoạt động .
Một Service được thực hiện như một lớp con của lớp Service như sau:
public class MyService extends Service {
 ...
}

3. Broadcast Receivers
Broadcast Receivers chỉ đơn giản là phản ứng để phát các tín hiệu từ các ứng dụng khác hoặc từ hệ thống. Ví dụ, các ứng dụng cũng có thể bắt đầu chương trình phát tín hiệu để cho các ứng dụng khác biết rằng một số dữ liệu đã được tải về điện thoại và sẵn sàng cho họ sử dụng.
Một máy thu phát tín hiệu được thực hiện như một lớp con của BroadcastReceiver lớp và mỗi tín hiệu được phát đi như một đối tượng Intent.

public class MyReceiver extends BroadcastReceiver {
 ...
}

4. Content Providers
Content Providers cung cấp nội dung dữ liệu từ một ứng dụng khác theo yêu cầu. Yêu cầu đó được xử lý bằng các phương thức (methods) của lớp ContentResolver. Dữ liệu có thể được lưu trữ trong hệ thống tập tin, cơ sở dữ liệu (database) hoặc ở một nơi hoàn toàn khác.
Một Content Providers được thực hiện như một lớp con của ContentProvider lớp và phải thực hiện một bộ tiêu chuẩn API cho phép các ứng dụng khác để thực hiện các giao dịch.

public class MyContentProvider extends ContentProvider {
 ...
}

5. Additional Components (Các thành phần bổ sung)
Có thành phần bổ sung sẽ được sử dụng trong việc xây dựng của các đơn vị nêu trên. Các thành phần này là:

Thành phần
Đặc tả
Fragments
Đại diện cho một hành vi hoặc một phần của giao diện người dùng trong một hoạt động.
Views
Các yếu tố giao diện người dùng được vẽ trên màn hình bao gồm các nút, danh sách các hình thức, vv
Layouts
Xem phân cấp kiểm soát định dạng màn hình và xuất hiện của các quan điểm.
Intents
Tín hiệu hệ thống kết nối các thành phần với nhau.
Resources
Các yếu tố bên ngoài, các hằng số và drawables hình ảnh..
Manifest
Tập tin cấu hình cho ứng dụng.

*******

Một số tài liệu và khoá học bổ ích dành cho bạn: 

# Giáo trình: Lập Trình Android [Click để xem]

# Khoá học online:  Lập trình Android toàn tập [Click để xem]


-----------------------------------------
Xem thêm bài và ví dụ khác:

 

[Tự học lập trình Android] Bài 2: Kiến trúc Android

in , /

 Kiến trúc Android

Hệ điều hành Android có thể coi như một ngăn xếp chứa các thành phần phần mềm, tạm chia thành năm phần và bốn lớp chính như hình dưới đây trong sơ đồ kiến ​​trúc .


1. Nhân Linux 
Ở dưới cùng của các lớp là Linux - Linux 2.6. Nhân Linux cung cấp chức năng cơ bản như hệ thống quản lý tiến trình, quản lý bộ nhớ, quản lý thiết bị như máy ảnh, bàn phím , màn hình hiển thị , vv...

2. Thư viện (Libraries)
Phần đầu của nhân Linux có một tập hợp các thư viện bao gồm cả mã nguồn mở trình duyệt web WebKit, các thư viện phổ biến, cơ sở dữ liệu SQLite có thể được coi như một kho lưu trữ hữu ích cho việc lưu trữ và chia sẻ dữ liệu ứng dụng, thư viện để chạy các ứng dụng như ghi âm và video, SSL thư viện chịu trách nhiệm về an ninh Internet, vv...

3. Android Runtime
Đây là phần thứ ba của kiến ​​trúc và có sẵn trên lớp thứ hai từ dưới lên. Phần này cung cấp một thành phần quan trọng được gọi là Dalvik (có thể đã thay đổi theo phiên bản) máy ảo là một loại máy Java được thiết kế đặc biệt và tối ưu hóa cho Android.

Máy ảo Dalvik sử dụng các tính năng cốt lõi Linux như quản lý bộ nhớ và đa luồng, mà là nội tại trong ngôn ngữ Java . Máy ảo Dalvik cho phép tất cả các ứng dụng Android chạy trong tiến trình riêng của nó, với trường hợp riêng của các máy ảo Dalvik .

Android Runtime cũng cung cấp một tập hợp các thư viện lõi cho phép các nhà phát triển ứng dụng Android sử dụng ngôn ngữ lập trình Java để viết các ứng dụng của mình.

4. Khung ứng dụng (Application Framework)
Lớp Application Framework cung cấp nhiều dịch vụ cấp cao hơn cho các ứng dụng dưới dạng các lớp Java. Nhà phát triển ứng dụng được phép sử dụng các dịch vụ này trong các ứng dụng của họ.

5. Ứng dụng (Applications)
Bạn sẽ tìm thấy tất cả các ứng dụng Android ở lớp trên cùng . Bạn sẽ viết ứng dụng và các ứng dụng đó phải được cài đặt trên chỉ lớp này.


*******

Một số tài liệu và khoá học bổ ích dành cho bạn: 

# Giáo trình: Lập Trình Android [Click để xem]

# Khoá học online:  Lập trình Android toàn tập [Click để xem]


-----------------------------------------
Xem thêm bài và ví dụ khác:

 

[Giải thuật] Các phương pháp biểu diễn giải thuật

in , /

Như các bạn đã biết, trước khi bắt tay vào viết chương trình (coding) chúng ta cần phải xác định được các bước thực hiện hay giải thuật (Algorithms). Ngày nay, với sự phát triển nhanh chóng của phần cứng cũng như các công cụ lập trình làm cho việc học lập trình và lập trình ngày càng đơn giản. Thậm chí lập trình viên không cần xây dựng thuật toán trước. Cách lập trình không thiết kế thuật toán (lập trình chay) chỉ có thể áp dụng cho các chương trình đơn giản, cách lập trình này tiềm ẩn rất nhiều nguy cơ, ngây ra những phức tạp không đáng có trong quá trình tester và sửa lỗi.

Các bạn đang học lập trình hoặc mới bắt tay vào nghề lập trình không nên bỏ qua bước xây dựng giải thuật trước khi coding. Để xây dựng giải thuật chúng ta cũng cần có bộ quy tắc nhất quán để biểu diễn giải thuật. Trong thực tế, cũng như trong các tài liệu về giải thuật người ta hay sử dụng một trong ba phương pháp biểu diễn khác nhau, đó là: Sử dụng ngôn ngữ tự nhiên (xây dựng giải thuật theo từng bước), sử dụng lưu đồ, sử dụng mã giả.

Để hiểu rõ các phương pháp biểu diễn giải thuật, chúng ta cùng xét ví dụ: 
    Xây dựng giải thuật giải phương trình bậc nhất một ẩn ax+b=0, với a,b là số thực nhập từ bàn phím.

- Biều diễn giải thuật bằng các sử dụng ngôn ngữ tự nhiên (liệt kê từng bước) - List each step 

Input: a,b ;
Output: kết quả nghiệm ;

Begin
 Bước 1: Nhập a, b =>Bước 2;
 Bước 2: Xét a = 0
  - Nếu đúng (true) => Bước 3 ;
  - Nếu sai (false) => Bước 4 ;
 Bước 3: Xét b=0 
  - Nếu đúng => Bước 5;
  - Nếu sai => Bước 6;
 Bước 4: x = -b/a => Bước 7;
 Bước 5: In thông báo: Phương trình có vô số nghiệm => Bước 8;
 Bước 6: In thông báo: Phương trình có vô nghiệm => Bước 8;
 Bước 7: In thông báo: Phương trình có nghiệm: x => Bước 8;
 Bước 8: Kết thúc
End.

- Biểu diễn giải thuật sử dụng lưu đồ (flowchart)


- Biểu diễn giải thuật sử dụng mã giả (pseudo code)
Giả mã ngôn ngôn ngữ lập trình Pascal

{Khai báo biến}

BEGIN
 
{Nhập a, b; } 
 
if(a=0) then
  if(b=0) then
       { In ra thông báo: Phương trình có vô số nghiệm ;}
  else 
       { In ra thông báo: Phương trình có vô nghiệm ;}
else
  begin
      x:= -b/a;
      { In ra thông báo: Phương trình có nghiệm: x ;}
  end;

END.


TxT




[Java] Xử lý mảng đối tượng trong Java

in , /

Mảng đối tượng trong Java 

 Xây dựng chương trình Java gồm các lớp đối tượng sau:

1. Lớp NhanVien có các thuộc tính: họ và tên, ngày tháng năm sinh và địa chỉ. Để phục vụ cho bài toán quản lý lớp NhanVien, ngoài công việc tính lương (thu nhập) thì cần có các hàm thành phần sau: Nhập, hiển thị các thông tin về các nhân viên.

2. Lớp CanBo thừa kế lớp NhanVien, ngoài những thuộc tính nêu trên còn có các thuộc tính: Chức vụ và hệ số lương được che dấu. Lương của CanBo được tính bằng tích hệ số lương với mức lương tối thiểu.

3. Lớp CoQuan có danh sách cán bộ quản lý các hàm:

- Nhập vào một danh sách n cán bộ, n nhập từ bàn phím

- Hiển thị danh sách cán bộ của cơ quan theo bảng, thông tin về cán bộ được hiển thị từng cột trên một dòng

- Sắp xếp danh sách đó theo thứ tự tăng của thu nhập

- Tìm những cán bộ có thu nhập nhỏ hơn d, d nhập vào từ bàn phím

- Hàm main() thực hiện các hàm nêu trên





[Code Java]

/***************************/

/***** class NhanVen ********/

/**************************/

package coquan;
import java.util.Scanner;

public abstract class NhanVien {

    public String hoTen, diaChi, ngaySinh;

    public NhanVien(String hoTen, String diaChi, String ngaySinh){
      this.hoTen=hoTen;
      this.diaChi=diaChi;
      this.ngaySinh=ngaySinh;
}

// Nhap thong tin

public void NhapTT(){
   Scanner inp=new Scanner(System.in);
   System.out.print("- Ho va ten: ");
   hoTen=inp.nextLine();
   System.out.print("- Ngay sinh: ");
   ngaySinh=inp.nextLine();
   System.out.print("- Dia chi: ");
   diaChi=inp.nextLine();
}

// Tinh thu nhap

public abstract float TinhLuong();

// In thong tin nhan vien

  public void InTT(){
     System.out.print("|"+hoTen + "\t \t| " + ngaySinh + "\t\t | "+diaChi+"\t \t| " + TinhLuong() +" | \n");
   }
}





/***************************/

/***** class CanBo **********/

/**************************/

package coquan;

import java.util.Scanner;

public class CanBo extends NhanVien {
    private String chucVu;
    private float heSoLuong;
    final float LCB=1500000.0f;

    public CanBo(String hoTen, String diaChi, String ngaySinh, String chucVu, float heSoLuong){
      super(hoTen, diaChi, ngaySinh);
      this.chucVu=chucVu;
      this.heSoLuong=heSoLuong;
   }

// Nhap thong tin

public void NhapTT(){
   super.NhapTT();
   Scanner inp=new Scanner(System.in);
   System.out.print("- Chuc vu: ");
   chucVu=inp.nextLine();
   System.out.print("- He so luong: ");
   heSoLuong=inp.nextFloat();
}

// Tinh thu nhap

  public float TinhLuong(){
     return heSoLuong*LCB;
  }
}



/***************************/
/***** class CoQuan *****/
/**************************/

package coquan;
import java.util.Scanner;

public class CoQuan {
    public static int n;
    static CanBo[] ds = new CanBo[100];
   
    // Nhap danh sach
    public CoQuan(){
        // khoi tao danh sach CanBo
        for(int i=0;i<100;i++)
            ds[i]=new CanBo("","","","",0.0f);
       
        Scanner inp=new Scanner(System.in);
        System.out.print("- Nhap so luong can bo: \n");
        n=inp.nextInt();
    }
   
    // Nhap danh sach
   void NhapDS(){
      
        System.out.print("NHAP THONG TIN \n");
       
        for(int i=0;i<n;i++){
            System.out.print("+ Nhap thong tin cho can bo thu "+(i+1)+": \n");
            ds[i].NhapTT(); 
        }
    }
   
    // In danh sach CanBo
    void InDS(){
        System.out.print("* IN THONG TIN \n");
        System.out.print("| Ho va ten\t | Nam sinh \t | Dia chi \t | Thu nhap   |\n");
         for(int i=0;i<n;i++)
            ds[i].InTT();
    }
   
    // Sap xep danh sach sinh vien theo chieu tang dan cua thu nhap
    void SapXep(){
        System.out.print("* SAP XEP DANH SACH CAN BO: \n");
        CanBo cb= new CanBo("","","","",0.0f);
        for(int i=0;i<n-1;i++)
            for(int j=i+1;j<n;j++)
                if(ds[i].TinhLuong()>ds[j].TinhLuong())
                {                  
                    cb=ds[i];
                    ds[i]=ds[j];
                    ds[j]=cb;
                }
               
    }

    // Tim canBo co thu thap nho hon d
    void TimCanBo(){
        float d;
        System.out.print("\n + Nhap muc thu nhap can tim:");
        Scanner inp=new Scanner(System.in);
        d=inp.nextFloat();
        System.out.print("* TIM CAN BO CO THU NHAP < "+d+":\n");
        for(int i=0;i<n;i++)
            if(ds[i].TinhLuong()<d)
                ds[i].InTT();
    }
   
    // ham main
    public static void main(String[] args) {
        CoQuan cq=new CoQuan();
        cq.NhapDS();
        cq.InDS();
        // sap xep
        cq.SapXep();
        cq.InDS();
        // tim can bo
        cq.TimCanBo();       
    }   
}

Một số tài liệu và khoá học bổ ích dành cho bạn: 

# Tài liệu: Lập trình hướng đối tượng JAVA core dành cho người mới bắt đầu học lập trình [Click để xem]

# Khoá học online: Lập trình Java trong 4 tuần [Click để xem]

[Bài viết] Mẹo tìm kiếm thông tin trên Google

in , /

Một số mẹo tìm kiếm chuyên nghiệp trên Google, có thể bạn chưa biết!
Google là công cụ tìm kiếm phổ biến nhất hiện nay, là một phần gần như không thể thiếu trong cuộc sống công nghệ. Nhưng việc biết và tận dụng được thế mạnh của Google thì không phải ai cũng biết hoặc khai thác được. Trong bài viết dưới đây sẽ giới thiệu với các bạn một số mẹo, thủ thuật để tăng hiệu suất tìm kiếm để tận dụng hết thế mạnh của Google.

1. Tìm kiếm chính xác với từ hoặc cụm từ

Một công thức cơ bản và phổ biến nhất mà gần như ai cũng biết, đó là sử dụng dấu ngoặc kép để tìm chính xác thông tin cần thiết.
Ví dụ, nếu thực hiện yêu cầu tìm kiếm cụm từ "Lap trinh may tinh" thì bạn để cụm từ đó trong cắp " " : “lap trinh may tinh”

2. Loại trừ từ khóa

Bên cạnh đó, khi bạn thêm dấu trừ "-" vào phía trước 1 từ bất kỳ trong chuỗi thông tin tìm kiếm thì hệ thống sẽ loại bỏ tất cả các kết quả có chứa từ đó.
Ví dụ: nếu muốn tìm kiếm các trang cung cấp thông tin về Linux distribution mà không có liên quan gì đến Ubuntu thì các bạn nhập từ khóa như sau: linux distributions -ubuntu

3. Tìm kiếm trên một website nhất định

Toán tử site: cho phép người dùng tìm toàn bộ thông tin cần thiết trên 1 trang cố định nào đó.
Ví dụ: Bạn muốn tìm thông tin về C++ trên laptrinhmaytinh.net thì các bạn hãy gõ từ khóa như sau:

site:laptrinhmaytinh.net  C++

Bên cạnh đó, chúng ta cũng có thể áp dụng cách này trên 1 domain bất kỳ. Chẳng hạn khi cần tìm các bài viết, đường dẫn có chất lượng thì nên chú tâm vào những tên miền có đuôi edu, như site:.edu để “đẩy” các kết quả từ các trang edu đó lên đầu.

4. Các từ ngữ có liên quan

Ngược lại với ý kiến ở phần 2, các bạn hãy sử dụng dấu ~ để tìm tất cả các từ ngữ có liên quan đến từ khóa nhập vào, bên cạnh chính bản thân keyword đó. 
Ví dụ: khi gõ ~thanhdo thì chúng ta sẽ nhận được rất nhiều kết quả với nhiều từ có liên quan với từ thanhdo:

Theo như trên thì Đại học thành đô chính là từ “gần gũi” nhất với thanhdo, tiếp theo là Tư vấn, và sau đó là sieu thi.

5. Ký tự đặc biệt

Dấu hoa thị được sử dụng trong trường hợp người dùng muốn tìm kiếm nhiều thông tin trùng khớp với bất kỳ từ khóa nào.
Ví dụ: nếu muốn biết Google đã bỏ ra bao nhiêu tiền trong việc mua và bán trong thời gian qua, các bạn hãy gõ: “ lap trinh may tinh * for * Java”

6. Giới hạn trong khoảng thời gian
Một thủ thuật nữa rất hay mà lại ít người để ý tới, đó là tìm trong 1 khoảng thời gian có giới hạn. Ví dụ: nếu muốn tìm kiếm dữ liệu, thông tin về Lap trinh may tinh từ năm 2013 cho tới 2014 thì nhập nội dung từ khóa như sau:  lap trinh may tinh 2013 .. 2014

7. Tìm theo định dạng file

Thông số filetype: cho phép người dùng dễ dàng tìm kiếm bất kỳ định dạng tài liệu nào. Chẳng hạn, nếu muốn tìm tất cả các file PDF có tên Microsoft ASP.NET 4 Step by Step thì gõ:

filetype: pdf Microsoft ASP.NET 4 Step by Step

8. Sử dụng OR

Tham số OR có tác dụng tìm kiếm bất kỳ kết quả nào có liên quan tới 1 trong 2 thuật ngữ trước và sau OR. Ví dụ như sau: Laptrinhmaytinh OR Programming


9. Định nghĩa theo từ

Rất đơn giản và dễ dàng, nếu muốn tìm nghĩa của 1 từ nào đó thì các bạn chỉ cần gõ từ khóa theo cú pháp chung như sau: define:programming
10. Sử dụng AND

Tham số AND và + có tác dụng tìm kiếm bất kỳ kết quả nào có liên quan tới cả 2 thuật ngữ. Ví dụ như sau: "Laptrinhmaytinh" AND "Programming" hoặc
"Laptrinhmaytinh" + "Programming"


11. Tính toán

Thay vì việc phải dùng Google để tìm kiếm những tiện ích trực tuyến, ứng dụng hỗ trợ để thực hiện phép tính, thì chúng ta chỉ cần sử dụng những ký tự và công thức toán học thông thường ngay trên Google. Ví dụ như sau: (4 + 2) * (6 / 3)



Hoặc vẽ đồ thị với: (sqrt(cos(x))*cos(400*x)+sqrt(abs(x))-0.4)*(4-x*x) ^0.1

12. Chuyển đổi đơn vị

Tương tự như trên, đây là 1 trong nhiều chức năng thú vị nhất của Google tính cho tới thời điểm hiện tại, đó là chuyển đổi giữa nhiều đơn vị khác nhau. Chỉ cần nhập nội dung tương ứng dựa theo công thức: “X [units] in [units]” hoặc “X [units] to [units]” hoặc “X [units] –> [units]”

Ví dụ: 1 mile to km

Ngoài ra, Google còn rất nhiều tính năng tìm kiếm nâng cao nữa, như tìm kiềm với ngôn ngữ, với lãnh thổ, với định dạng,...

Chúc các bạn luôn tìm được những thứ mình muốn tìm !
 

Tham khảo Internet

[Algorithm] Thuật toán leo đồi (Hill Climbing Search)

in , , , , , , /

Giơi thiệu Thuật toán leo đồi (Hill Climbing Search)



Trước hết, ta nghiên cứu bài toán sau: Trò chơi n2-1 số (n thuộc N, n > 1).

Bài toán:


 Có n2-1 số mang các giá trị từ 1 tới n2-1 được sắp xếp vào một lưới các ô vuông kích thước n x n. Mỗi số đó được gọi là một quân cờ và lưới ô đó được gọi là bàn cờ. Có một vị trí của bàn cờ bỏ trống. Mỗi lần di chuyển quân, người chơi được phép chuyển một quân ở vị trí ô tiếp giáp cạnh với ô trống vào ô trống.

Yêu cầu: 


Từ một trạng thái ban đầu (sự sắp xếp ban đầu của các quân trên bàn cờ), hãy thực hiện các nước đi hợp lệ để thu được trạng thái kết thúc (trạng thái đích cần đạt được).

Vídụ: với trò chơi 8 số ta minh họa trạng thái ban đầu và trạng thái kết thúc qua các hình vẽ dưới đây:

Hình 1


Để giải bài toán này, chúng ta sẽ nghĩ ngay tới việc xây dựng một cây tìm kiếm mà gốc của cây tương ứng với trạng thái xuất phát của bàn cờ. Các đỉnh khác của cây tương ứng với các trạng thái thu được do việc thực hiện các nước đi hợp lệ (các nước đi được phép thực hiện là: lên trên, xuống dưới, sang trái và sang phải). Với ví dụ trên, ta có cây tìm kiếm sau:
Hình 2

 Tiếp đó, ta chỉ việc áp dụng các thuật toán thông dụng như: thuật toán tìm kiếm theo chiều rộng hoặc thuật toán tìm kiếm theo chiều sâu để tìm ra lời giải.

Ý tưởng thuật toán:

Việc suy nghĩ như trên xem ra có tính khả thi (đơn giản, dễ cài đặt), tuy nhiên, dễ nhận thấy rằng nếu số n lớn hơn, ta sẽ phải phát triển một số quá lớn các trạng thái trước khi phát hiện ra trạng thái đích. Những hạn chế về mặt thời gian và dung lượng bộ nhớ không cho phépthực hiện điều đó.

Trong thực tế, có nhiều bài toán mà số các trạng thái của nó là rất lớn (như cờ vua, cờ tướng...), thì việc giải bài toán chỉ có thể thực hiện nếu bằng một cách nào đó ta lược bỏ những trạng thái thừa, không cần thiết nhằm giảm số lượng trạng thái cần phát triển. Để làm được điều đó, phải sử dụng khéo léo các thông tin phản hồi nảy sinh trong quá trình tìm kiếm (các thông tin này còn gọi là thông tin cảm tính: HeuristicInformation). Cách làm này được đưa ra nhằm mục đích lựa chọn được hướng tìm kiếm tốt nhất tại mỗi bước theo nghĩa: hướng đi đó nhanh dẫn tới trạng thái đích nhất và nhằm giảm công sức tìm kiếm.


Thuật toán leo đồi:

Thuật toán tìm kiếm leo đồi đã đáp ứng được yêu cầu trên. Nội dung thuật toán được mô tả như sau:

Bước 1: Nếu trạng thái đầu trùngvới trạng thái đích thì dừng ngay, ngược lại thì chuyển sang bước 2.

Bước 2: Sử dụng các quy tắc biến đổi để tạo ra 1 tập hợp các trạng thái từ trạng thái hiện thời (trong bài toán trên ta có 4 quy tắc biến đổi tương ứngvới 4 phép di chuyển quân).

Bước 3: Với mỗi trạng thái trong tập hợp vừa tạo ra kiểm tra xem đó có phải là trạng thái đích hay không? Nếu phải thì ngừng việc tìm kiếm, nếu không phải thì ta kiểm tra xem trạng thái mới này có tốt hơn (gần trạng thái đích hơn) so với trạng thái đã có hay không? Nếu quả thật như vậy thì ghi nhận trạng thái này, ngược lại thì bỏ qua.

Bước 4: Trong các trạng thái được tạo ra (sau khi thực hiện các thao tác ở bước 3), ta ưu tiên phát triển trạngthái tốt nhất (trạng thái tốt nhất là trạng thái có tiềm năng dẫn tới đích nhanh nhất).
Bước này nhằm mục đích chuyển hướng tìm kiếm lời giải nhanh đến đích nhất.

Bước 5: Lặp lại từ bước 2.

Đến đây bạn có thể nhận thấy thuật toán tìm kiếm leo đồi thực chất là thuật toán tìm kiếm theo chiều sâu, song tại mỗi bước ta sẽ ưu tiên chọn một trạng thái có hứa hẹn nhanh tới đích nhất để phát triển trước. Vấn đề quan trọng là ở chỗ biết khai thác khéo léo thông tin phản hồi để xác định hướng đi tiếp và đẩy nhanh quá trình tìm kiếm.Thông thường ta gắn mỗi trạng thái của bài toán với một số đo (1 hàm đánh giá) nào đó nhằm đánh giá mức độ gần đích của nó.

Như vậy: Nếu trạng thái hiện thời là u, theo bước 4 của thuật toán trên thì trạng thái v sẽ được phát triển tiếp theo nếu vẻ kề(u) và hàm đánh giá của v đạt giá trị max (hoặc min).


Phần tiếp theo sẽ trình bày cụ thể thuật toán để giải bài toán trên. Trong bài toán này, ta sẽ sử dụng hàm đánh giá ký hiệu là h với ý nghĩa: h(u) cho biết số cácchữ số trong trạng thái u không trùng với vị trí của nó trong trạng thái đích.Trạng thái có tiềm năng dẫn tới đích nhanh nhất (được ưu tiên phát triển trước)là trạng thái có hàm đánh giá h đạt giá trị min.
Thuật toán cho trò chơi n2-1 số được mô tả như sau :
 
Hình 3


Algorithm:


 Input: Trạng thái ban đầu u0và trạng thái đích ut

BEGIN

1. P:={u0} ; { P để lưu các trạng thái chờ phát triển được tổ chức dưới dạng Stack }

   Q:=Φ ;  { để lưu các trạng thái đãphát triển được tổ chức dưới dạng hàng đợi Queue }

   P:= Φ ; { P để lưu tạm thời các trạngthái kề với trạng thái đang xét }

   found:=false;

2. While (P # y) and (not found) do

   2.1. Loại bỏ trạng thái u ở đỉnh stack P và đặt nó vào hàng đợi Q:
          Pop(P, u);
          Add(u, Q);

2.2. if u=ut then found:= true
       else
           For v kề (u) do
              if (v thuộc P U Q) and (h(v) <= max { h(w)| w thuộc P U Q } then
               Begin
                  father (v):=u;
                  Add (v, P);
              End;

        if P <> f then
         Begin
           - Sắp xếp các trạng thái trong P theotrật tự tăng của hàm h;
           - Chuyển các trạng thái trong P vàođỉnh của stack P sao cho trạng thái có giá trị hàm h nhỏ nhất ở đỉnh của P;

         End;

END.

Output:  

- Nếu found = false thì bài toán không có lời giải.

- Nếu found = true thì lời giải là đường đi từ u0 tới ut được xác định bằng cách sử dụng hàm father.


Chú ý: Sau khi chuyển các trạng thái từ P vào P thì P= f



 Hình 4

h(v1)  ≤  h(v2)  ≤ .... ≤  h(vk)

Với ví dụ trên, cây tìm kiếm được hình thành bởi tìm kiếm leo đồi có các trạng thái được phát triển như hình vẽ dưới (nét đậm thể hiện hướng tìm kiếm), các số ghi cạnh mỗi đỉnh là giá trị của hàm h tại đỉnh đó.

Thuật toán này có tên gọi là thuật toán tìm kiếm leo đồi, vì tư tưởng của nó tương tự như trường hợp: Một người ở vị trí chân đồi u0 và muốn leo lên đỉnh đồi tại vị trí ut. Anh ta chọn một đỉnh cao nhất trong số các đỉnh mà anh ta có thể đến được (từ vị trí đang đứng) để leo lên, tại vị trí này anh ta lại chọn một đỉnh cao nhất như bước trước để leo lên. Quá trình cứ lặp lại như vậy cho đến khi tới được đích ut.

Nhận xét: Thuật toán này đơn giản, dễ cài đặt và tỏ ra có nhiều hiệu quả. Bạn đọc có thể tự lập trình để giải bài toán trên, kết quả khá tuyệt vời! Tuy nhiên, thuật toán này không phù hợp với các bài toán có giá trị hàm đánh giá đột nhiên thay đổi khi đến ngưỡng nào đó. Một số hiện tượng sẽ nảy sinh trong quá trình tìm kiếm được ghi nhận như sau:

*Có cực đại địa phương, là nơi đạt được lời giải tốt hơn các lời giải lân cận, nhưng chưa phải là lời giải tốt trên tổng thể. Như vậy phải có biện pháp ghi nhớ lại nhiều đường đi đề phòng khi cần đi lại đường cũ.

*Có vùng lời giải như cao nguyên bằng phẳng, không thể xác định được ngay hướng nào tốt hơn nếu chỉ so sánh vùng lân cận (các trạng thái của bài toán có hàm đánh giá xấp xỉ bằng nhau). Khi đó cần có bước nhảy xa để thoát khỏi vùng bằng phẳng.

Có đỉnh hình chóp, đó là trạng thái được lựa chọn tốt hơn vùng lân cận nhưng không vượt qua được theo bất kỳ hướng nào. Để xử lý hiện tượng này, nên chuyển theo đồng thời vài hướng.

Cực đại địa phương Cao nguyên Chóp

Minh họa cực trị địa phương khi giải bài toán bằng thuật toán leo đồi.

Như vậy: Thuật toán này chỉ làphương pháp giải quyết cục bộ, để tăng tính tối ưu, có thể sử dụng phối hợp nóvới các thuật toán tìm kiếm khác.

 Hình 5


Tham khảo 123doc



Subscribe to: Posts (Atom)

Categories

AI (14) AI programming (1) ASP (1) Android (32) App Honeygain (5) Assembly (17) Biểu diễn thuật toán (1) Bubble-Sort (1) Bài giảng (2) Bài giảng lập trình C và Cpp (21) Bài viết hay (112) Bản đồ tư duy (1) C Plus Plus (103) C/C++ (16) CDSL phân tán (1) CSS (2) Cơ sở dữ liệu (11) Danh ngôn lập trình (1) Datamining (4) Genetic Algorithm (1) Giáo trình (3) Giải thuật tiến hóa - thuật toán di truyền (2) Google App Engine (2) Góc học tập (34) HTML (1) Hướng dẫn kiếm tiền online tại nhà (7) Hướng dẫn sử dụng Emu8086 (1) Học lập trình (132) Học lập trình C và CPP qua ví dụ (17) Java (54) Java Căn bản (6) JavaScript (5) Kỹ năng đọc hiệu quả (1) Kỹ thuật lập trình (16) Kỹ thuật đồ họa máy tính (10) Lý thuyết Cơ sở dữ liệu (2) Lý thuyết đồ thị (11) Lập trình Cơ sở dữ liệu (2) Lập trình Python (2) Lập trình căn bản (8) Lập trình hướng đối tượng với Java (7) Lập trình mobile (9) Lập trình mạng (6) Lập trình nhúng (1) Lập trình trí tuệ nhân tạo (2) ML (1) MMO (7) MS Access (1) Machine learning (2) Mạng máy tính (1) Mẹo tìm kiếm trên Google (1) Nghiên cứu khoa học (3) Ngôn ngữ lập trình (2) Những cuốn sách hay mà bạn nên đọc khi còn trẻ (1) Pascal (3) Phương pháp tính toán tối ưu (2) Phương pháp tối ưu (2) Quản lý dự án CNTT (1) SEO (1) SQL (5) Swift (9) Sách hay (4) Thiết kế Web (2) Thuật toán (51) Thuật toán Sắp Xếp -Sort (9) Thuật toán Tìm kiếm - Search (5) Thuật toán di truyền (4) Thực hành Android (2) Tin học văn phòng (5) Tiện ích máy tính (3) Toán rời rạc (13) Treo máy kiếm tiền (5) Trí tuệ nhân tạo (20) Tài liệu tham khảo (5) Tìm hiểu Blockchain (2) Tự học Android (3) Tự học Android qua ví dụ (1) Tự học JavaScript (1) Tự học lập trình (9) Tự học lập trình Android (17) Tự học lập trình C và CPP (14) Tự học lập trình java qua các ví dụ (8) XML (1) blockchain (2) bài giảng quản lý dự án CNTT (1) bài tập java (3) bài tập lập trình (4) cấu trúc dữ liệu giải thuật (15) hướng dẫn viết báo (1) học lập trình Java (11) học máy (5) hợp ngữ (8) lập trình viên (4) phưng pháp đơn hình (2) thuật toán AI (2) tài liệu CNTT miễn phí (4) tính toán tối ưu (1) tự học lập trình iOS (8) tự học lập trình python (1) ví dụ Assembly (1) Đại số gia tử và ứng dụng (1) Đồ họa (4)