Chuyển đến nội dung chính

Bài đăng

Đang hiển thị bài đăng từ tháng mười, 2013

[ C\C++ ] Bài toán người đưa thư sử dụng giải thuật Heuristic [ Giải thuật - Trí tuệ nhân tạo ]

1. Phát biểu bài toán:

Bài toán: Để tiết kiệm thời gian đi đưa thư trong một địa phương. Người đưa thư phải đi qua tất cả các điểm cần phát thư rồi trở về vị trí ban đầu với đường đi ngắn nhất.

Bài toán có thể phát biểu lại như sau: Giả sử có một đồ thị có trọng số dương, tìm đường đi ngắn nhất qua tất cả các đỉnh của đồ thị rồi trở về đỉnh ban đầu.

2. Hạn chế khi sử dụng thuật toán tối ưu:

Đồ thị có n đỉnh, khi đó thuật toán tối ưu cho bài toán này sẽ là thuật toán tìm đường đi ngắn nhất cho chu trình Haminton. Do đó thuật toán tối ưu sẽ có độ phức tạp là O(n!).

ĐI TÌM một thuật giải Heuristic cho bài toán này.

3. Sử dụng thuật toán Heuristic cho bài toán người đưa thư:

- Theo kinh nghiệm của con người trong thực tế thì khi ta đi trên những đoạn đường ngắn nhất thì cuối cùng ta sẽ có một hành trình ngắn nhất à sử dụng nguyên lý tham lam.

- Thuật giải bài toán sử dụng nguyên lý tham lam:

- Ví dụ về thuật giải trên:

Với một đồ thị trọng số dương như hình bên. Nếu ta xuất phát từ đỉnh sổ 1, thì…

[ Lập trình Android ] Ví dụ: Xây dựng ứng dụng MÁY TÍNH ĐIỆN TỬ [ ứng dụng Android cơ bản ]

Xây dựng ứng dụng mô phỏng máy tính điện tử đơn giản trên Android:


Để xây dựng ứng dụng trên, chúng ta tiến hành như sau (Cài đặt trên môi trường Eclipse đã plugin SDK, xem thêm tại đây):

Bước 1: Tạo Project Vidu1 với các thành phần như hình vẽ


 Bước 2: Viết nội dung các file:  PhepTinh.java (chứa các xử lý tính toán); Vidu1.Activity.java (file chạy Android); main.xml (thiết kế giao diện); color.xml (thiết lập màu sắc); string.xml (thiết lập các giá trị cho string). Nội dung cụ thể:

+ color.xml

<?xml version="1.0" encoding="utf-8"?>
<resources>
<color name="title_color">#0000FF</color>
<color name="text_color">#DC143C</color>
<color name="resul_color">#FFD700</color>
<color name="backg_color">#F0F8FF</color>
<color name="btn_color">#FF0000</color>

</resources>

+ string.xml

<?xml version="1.0" encoding="utf-8"?>
<resources>…

[ C# ] Làm việc với File và Directory trong C#

.NET Framework của Microsoft cung cấp cho chúng ta namespace System.IO để làm việc với thư mục và tập tin trên máy tính. Bài viết sau đây sẽ hướng dẫn các bạn một số phương thức và lớp rất hữu dụng khi thao tác với tập tin/thư mục.
Trong tất cả các đoạn code sau này, chúng ta lưu ý đều phải có chỉ dẫn tham chiếu đến System.IO như sau ở đầu:

using System.IO;
Lấy thông tin về File, Directory hoặc Drive

Thông qua các lớp FileInfo, DirectoryInfo và DriveInfo, chúng ta có thể lấy được thông tin về đối tượng như: ngày khởi tạo, kích thước, phần mở rộng, thuộc tính… Ví dụ sau đây cho phép chúng ta nhập vào đường dẫn đến một tập tin và sẽ hiển thị thông tin về tập tin, thư mục cha và ổ đĩa chứa tập tin đó.

using System;  using System.Collections.Generic;  using System.IO;  namespace Example  {    class Test     {       public static void Main()        {          Console.Write("Enter file path:");          string filePath = Console.ReadLine();          Console.WriteLine("File Information"…

[ C\C++ ] Chuyển đổi từ số thực sang chuỗi kí tự trong C/C++

make money Như ta đã biết, trong C/C++ có tích hợp một số các hàm chuyển đổi cho phép ta chuyển đổi qua lại giữa các loại dữ liệu. 
Một số hàm thường dùng:  - atoi (chuyển chuỗi sang số nguyên),   - atof (chuyển sang float),   - atol (chuyển sang số longint), ... các hàm này có trong thư viện stdlib.h
Và ngược lại, từ số nguyên ta có thể chuyển đổi về chuỗi một cách dễ dàng dùng hàm itoa(). 


Ví dụ [code C]: #include <stdlib.h> // for itoa() call
#include <stdio.h> // for printf() call
int main()
{
  int num = 123;
  char buf[5];
// convert 123 to string [buf]
  itoa(num, buf, 10);
// print our string
  printf("%sn", buf);
  return 0;
}

Lưu ý cần đảm bảo buf đủ chỗ chứa số cần chuyển để tránh trường hợp tràn bộ đệm, kích thước cỡ (sizeof(int)*8 + 1).

Chuyển đổi đối với số nguyên là như vậy nhưng đôi khi ta lại gặp trường hợp khó hơn là chuyển đổi float sang chuỗi vì trong thư viện của C/C++ không có hàm nào cho phép ta làm việc này. Thật may mắn, như các bạ…

[Thuật toán đồ thị / code C++] Thuật toán Dijkstra - tìm đường đi ngắn nhất từ đỉnh D đến đỉnh C trên đồ thị G.

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định đường đi ngắn nhất từ đỉnh D tới đỉnh C của đồ thị G.

Ý tưởng thuật toán: sử dụng thuật toán Dijkstra (tìm hiểu thêm về thuật toán Dijkstra tại đây).

Mô tả dữ liệu đầu vào và đầu ra của bài toán:

+ Dữ liệu vào: đồ thị đã liên thông và cho trong tập tin Dijkstra.inp.
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
- Dòng thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 (1 <= i <= n ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.

+ Dữ liệu ra: xuất ra màn hình đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.




[Cài đặt thuật toán với Turbo C++]
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define max 100 #define FileIn "Dijkstra.inp"

// doc file chua do thi G
void Doc_File(int A[max][max], int &n, int &D, int &C) {
  FILE*f = fopen(FileIn,"rb");
  fscanf(f,"%d%d%d",&n,&am…

[Thuật toán đồ thị / code C++] Thuật toán Euler - tìm đường đi Euler trên đồ thị G (với đồ thị nửa Euler)

Mô tả bài toán: cho đồ thị vô hướng G=(V,E) hãy xác định mọi đường đi qua tất cả các cạnh mỗi cạnh chỉ qua duy nhất 1 lần.

Ý tưởng thuật toán: sử dụng kỹ thuật tìm kiếm theo chiều sâu bằng cách xóa cạnh đã đi qua trong quá trình tìm kiếm đường đi.

Mô tả dữ liệu đầu vào và đầu ra của bài toán:
+ Dữ liệu vào: cho trong tập tin Euler.inp
   - Dòng đầu ghi số n là số đỉnh của một đồ thị (0<n<100)
   - Dòng i+1 (1 <= i <= n ) chứa n số A[i,1],A[i,2]…A[i,n] mỗi số cách nhau bởi một khoảng trắng.
+ Dữ liệu ra: in ra màn hình đường đi qua tất cả các cạnh (nếu có).

[Cài đặt thuật toán với Turbo C++]

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#define Filename "Euler.inp"
int Dem = 0, SoCanh=0; //dem so duong di va luu so canh cua do thi
int *L; //luu dinh da di qua
int **A,n;
int XuatPhat=0; //dinh xuat phat la dinh bac le neu do thi co dinh bac le

// Doc file chua do thi G (dang ma tran ke)
void Doc_File() {
   int BacDinh; // Bac cua dinh

[Algorithms] Cây quyết định với bài toán phân loại dữ liệu

Cây quyết định với bài toán phân loại dữ liệu

Khái niệm cây quyết định

Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo (predictive model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong (internal node) tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trước các giá trị của các biến được biểu diễn bởi đường đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định. [Xem thêm...]

[Algorithms] Thuật toán K-Mean trong bài toán Phân cụm dữ liệu [VB]

Thuật toán K-Mean trong bài toán Phân cụm dữ liệu


I. GIỚI THIỆU
Thuật toán K-means clustering do MacQueen giới thiệu trong tài liệu “J. Some Methods for Classification and Analysis of Multivariate Observations” năm 1967.
K-means Clustering là một thuật toán dùng trong các bài toán phân loại/nhóm n đối tượng thành k nhóm dựa trên đặc tính/thuộc tính của đối tượng (k £n nguyên, dương).
Về nguyên lý, có n đối tượng, mỗi đối tượng có m thuộc tính, ta phân chia được các đối tượng thành k nhóm dựa trên các thuộc tính của đối tượng bằng việc áp dụng thuật toán này.
Coi mỗi thuộc tính của đối tượng (đối tượng có m thuộc tính) như một toạ độ của không gian m chiều và biểu diễn đối tượng như một điểm của không gian m chiều. [Xem thêm...]

[ Java ] Lớp trừu tượng và phương thức trừu tượng (abstract) trong Java - Ví dụ 1: Tính điểm cho sinh viên [abstract class-method]

Lớp trừu tượng và phương thức trừu tượng (abstract) trong Java
Xây dựng Project theo mô hình sau:



Yêu cầu:
 - Khởi tạo mỗi lớp 1 đối tượng  - In kết quả 
[Cài đặt với NetBean] - Xây dựng Project như hình sau:


- Code Java:
/*abstract class SV*/ package abstract1;
public abstract class SV {     // thuoc tinh     int ns;// nam sinh     String ht;// ho ten     String dc;// dia chi     // phuong thuc khoi tao     public SV(String ht, int ns, String dc){      this.ht=ht; this.dc=dc; this.ns=ns;        }         // Phuong thuc TinhDiem() - abstract     abstract float TinhDiem();     // phuong thuc XepLoai()-abstract     abstract String XepLoai();     // phuong thuc InKQ()     void InKQ(){         System.err.print("\n - Ho ten sinh vien: "+ht);         System.err.print("\n - Dia chi: "+dc);         System.err.print("\n - Nam sinh: "+ns);         System.err.print("\n - Diem tong ket: "+TinhDiem());         System.err.println("\n - Xep loai: "+XepLo…