Giải bài toán tam giác sử dụng mạng ngữ nghĩa – Solution for triangle using semantic network

  Bài viết này mô tả bài toán giải tam giác bằng mạng ngữ nghĩa (chương trình nhỏ) kèm theo chương trình demo viết trên Visual studio 2010 (C#). Tài liệu tham khảo hơi nhiều chỗ nên hiện giờ chưa nhớ hết. Bài này chỉ demo 5 công thức trong tam giác được lấy từ ví dụ của giáo trình trường Đại học công nghệ thông tin – xuất bản năm 2007.

1. Sơ lược về bài toán tam giác bằng mạng ngữ nghĩa.

Có 22 yếu tố liên quan đến cạnh và góc của tam giác. Để xác định một tam giác thì ta phải có 3 yếu tố. Trong đó phải có yếu tố cạnh. Như vậy có khoảng vài ngàn cách để xây dựng hay xác định một tam giác. Theo thống kê thì có khoảng trên 200 công thức liên quan đến cạnh và góc của tam giác.

Để giải bài toán này bằng mạng ngữ nghĩa, ta phải sử dụng khoảng 200 đỉnh để chứa công thức và khoảng 22 đỉnh để chứa các yếu tố của tam giác. Mạng ngữ nghĩa cho bài toán này có cấu trúc như sau:

Đỉnh của đồ thị bao gồm 2 loại:

– Đỉnh chứ công thức (ký hiệu bằng hình chữ nhật).

– Đỉnh chứa các yếu tố tam giác (ký hiệu bằng hình tròn).

Cung: chỉ nối từ đỉnh hình tròn đến đỉnh hình chữ nhật cho biết yếu tố tam giác xuất hiện trong công thức nào(không có trường hợp cung nối giữa hai đỉnh hình tròn hay nối giữa 2 đỉnh hình chữ nhật).

* Lưu ý : trong một công thức liên hệ giữa n yếu tố của tam giác, ta giả định rằng nếu đã biết giá trị của n-1 yếu tố thì sẽ tính được giá trị của yếu tố còn lại. Chẳng hạn như trong công thức tổng 3 góc của tam giác bằng 1800thì khi biết được hai góc, ta sẽ tính được góc còn lại.

2. Cơ chế thực hiện và giải thuật:

Cơ chế suy diễn thực hiện theo thuật toán “loang” đơn giản sau :

B1 : Kích hoạt những đỉnh hình tròn đã cho ban đầu (những yếu tố đã có giá trị)B2 : Lặp lại bước sau cho đến khi kích hoạt được tất cả những đỉnh ứng với những yếu tố cần tính hoặc không thể kích hoạt được bất kỳ đỉnh nào nữa.Nếu một đỉnh hình chữ nhật có cung nối với n đỉnh hình tròn mà n-1 đỉnh hình tròn đãđược kích hoạt thì kích hoạt đỉnh hình tròn còn lại (và tính giá trị đỉnh còn lại này thông qua công thức ở đỉnh hình chữ nhật).

Giả sử ta có mạng ngữ nghĩa để giải bài toán tam giác như hình sau: (Ví dụ này cũng sẽ được sử dụng trong source code demo chương trình kèm theo).

Ví dụ : “Cho hai góc a, b và chiều dài cạnh a của tam giác. Tính chiều dài đường cao hC”. Với mạng ngữ nghĩa đã cho trong hình trên. Các bước thi hành của thuật toán như sau :

clip_image002[5]

Bắt đầu : đỉnh a, b, acủa đồ thị được kích hoạt.

– Công thức (1) được kích hoạt (vìa, b,a được kích hoạt). Từ công thức (1) tính được cạnh b. Đỉnh b được kích hoạt.

– Công thức (4) được kích hoạt (vì a, b). Từ công thức (4) tính được góc d

– Công thức (2) được kích hoạt (vì 3 đỉnh b,d,b được kích hoạt). Từ công thức (2) tính được cạnh c. Đỉnh cđược kích hoạt.

– Công thức (3) được kích hoạt (vì 3 đỉnh a, b, c được kích hoạt) . Từ công thức (3) tính được diện tích S. Đỉnh S được kích hoạt.

– Công thức (5) được kích hoạt (vì 2 đỉnh S, c được kích hoạt). Từ công thức (5) tính được hC. Đỉnh hC được kích hoạt.

– Giá trị hC đã được tính.

Thuật toán kết thúc.

3. Xây dựng chương trình giải bài toán tam giác bằng mạng ngữ nghĩa theo ví dụ trên.

Chương trình được xây dựng trên môi trường visual studio 2010, ngôn ngữ C#

clip_image006

Giao diện chương trình demo ví dụ trên.

Về mặt chương trình, ta có thể cài đặt mạng ngữ nghĩa giải bài toán tam giác bằng một mảng hai chiều A trong đó:

Cột : ứng với công thức. Mỗi cột ứng với một công thức tam giác khác nhau (đỉnh hình chữ nhật).

Dòng: ứng với yếu tố tam giác. Mỗi dòng ứng với một yếu tố tam giác khác nhau (đỉnh hình tròn).

Phần tử A[i, j] = -1 nghĩa là trong công thức ứng với cột j có yếu tố tam giác ứng với cột i. Ngược lại A[i,j] = 0.

// Khai báo biến.
    private float[,] a = new float[8, 5];

// Khởi tạo các yếu tố trong tam giác theo ma trận lúc đầu.
pivate void init()
{
  float temp = -1;     // Bien tam
  for (int i = 0; i < 8; i++ )
  {
      for (int j = 0; j < 5; j++ )
      {
          a[i, j] = 0;
      }
  }

  a[0, 0] = a[1, 0] = a[3, 0] = a[4, 0] = temp;
  a[1, 1] = a[2, 1] = a[4, 1] = a[5, 1] = temp;
  a[3, 2] = a[4, 2] = a[5, 2] = a[6, 2] = temp;
  a[0, 3] = a[1, 3] = a[2, 3] = temp;
  a[5, 4] = a[6, 4] = a[7, 4] = temp;
}

Để thực hiện thao tác “kích hoạt” một đỉnh hình tròn, ta đặt giá trị của toàn dòng ứng với yếu tố tam giác bằng 1.

Để kiểm tra xem một công thức đã có đủ n-1 yếu tố hay chưa (nghĩa là kiểm tra điều kiện “đỉnh hình chữ nhật có cung nối với n đỉnh hình tròn mà n-1 đỉnh hình tròn đã được kích hoạt“), ta chỉ việc lấy hiệu giữa tổng số ô có giá trị bằng 1 và tổng số ô có giá trị -1 trên cột ứng với công thức cần kiểm tra. Nếu kết quả bằng n, thì công thức đã có đủ n-1 yếu tố.

Trở lại mạng ngữ nghĩa đã cho. Quá trình thi hành kích hoạt được diễn ra như sau :

Mảng biểu diễn mạng ngữ nghĩa ban đầu

(1) (2) (3) (4) (5)
a -1 0 0 -1 0
b -1 -1 0 -1 0
d 0 -1 0 -1 0
a -1 0 -1 0 0
b -1 -1 -1 0 0
c 0 -1 -1 0 -1
S 0 0 -1 0 -1
hC 0 0 0 0 -1

Khởi đầu : đỉnh a, b, a của đồ thị được kích hoạt.

(1) (2) (3) (4) (5)
a 1 0 0 1 0
b 1 1 0 1 0
d 0 -1 0 -1 0
a 1 0 1 1 0
b -1 -1 -1 0 0
c 0 -1 -1 0 -1
S 0 0 -1 0 -1
hC 0 0 0 0 -1

Trên cột (1), hiệu (1+1+1 – (-1)) = 4 nên dòng b sẽ được kích hoạt.

(1) (2) (3) (4) (5)
a 1 0 0 1 0
b 1 1 0 1 0
d 0 -1 0 -1 0
a 1 0 1 1 0
b 1 1 1 0 0
c 0 -1 -1 0 -1
S 0 0 -1 0 -1
hC 0 0 0 0 -1

Trên cột (4), hiệu (1+1+1 – (-1)) = 4 nên dòng d sẽ được kích hoạt.

(1) (2) (3) (4) (5)
a 1 0 0 1 0
b 1 1 0 1 0
d 0 1 0 1 0
a 1 0 1 1 0
b 1 1 1 0 0
c 0 -1 -1 0 -1
S 0 0 -1 0 -1
hC 0 0 0 0 -1

Trên cột (2), hiệu (1+1+1 + (1)) = 4 nên dòng c được kích hoạt.

(1) (2) (3) (4) (5)
a 1 0 0 1 0
b 1 1 0 1 0
d 0 1 0 1 0
A 1 0 1 1 0
B 1 1 1 0 0
C 0 1 1 0 1
S 0 0 -1 0 -1
hC 0 0 0 0 -1

Trên cột (3), hiệu (1+1+1 – (-1)) = 4 nên dòng S được kích hoạt.

(1) (2) (3) (4) (5)
a 1 0 0 1 0
b 1 1 0 1 0
d 0 1 0 1 0
a 1 0 1 1 0
b 1 1 1 0 0
c 0 1 1 0 1
S 0 0 1 0 1
hC 0 0 0 0 -1

Trên cột (5), hiệu (1+1 + (1)) = 3 nên dòng hC được kích hoạt.

Các hàm xử lý các ma trận ngữ nghĩa:

// Lấy vị trí yếu tố chưa biết.

private int GetElementNotKnow(int k)

// Kích hoạt yếu tố chưa biết.

private void activationElementKnow()

// Kích hoạt theo cơ chế lan truyền.

private void spreadingActivation(int j, int ElementNotKnow)

// Xử lý

private void Solution()

4. Cách sử dụng chương trình demo:

– Nhập vào các giá trị lúc đầu của tam giác vào các textbox màu vàng trên chương trình.

– Chọn giá trị cần tính trong combobox phía bên phải.

– Nhấn bắt đầu tính để thực hiện tính tam giác theo mạng ngữ nghĩa đã được cài đặt.

– Để bắt đầu với bài toán mới, nhấn vào button Làm bài khác.

5. Tài liệu tham khảo:

Giáo trình Trí Tuệ Nhân Tạo – Đại học công nghệ thông tin – GS.TSKH. Hoàng Kiếm, Ths. Đinh Nguyễn Anh Dũng – Xuất bản năm 2007

Model Driven Architecture and Ontology Development – Tác giả:  Dragan Gasevic, Dragan Djuric, Vladan Devedzic

http://en.wikipedia.org/wiki/Semantic_network

http://en.wikipedia.org/wiki/Spreading_activation

6. Source code chương trình

Advertisements

About thanhcuong1990

Handsome and talent!! ^^
This entry was posted in Artificial Intelligence. Bookmark the permalink.

18 Responses to Giải bài toán tam giác sử dụng mạng ngữ nghĩa – Solution for triangle using semantic network

  1. Hi hi says:

    Trong công thức Herong khi nhập a,b,S tìm c chẳng hạn thì giả sử mình cho a=3,b=4,S=6 -> c=5; nhưng khi cho b=4, c=5, S=6 => a thì a lại bằng cái gì đó đó. Bạn xem lại thử ^^

  2. lu khach says:

    bài này bạn lấy lại hình ảnh mạng ngữ nghĩa trong bài giảng của thầy kiếm.
    vẽ lại đẹp hơn làm lại ma trận thi chuẩn hơn đấy nha!

  3. Phamhai99 says:

    Bạn ơi, up giùm source code chương trình lại giùm mình với. up lên mediafire cho lâu hỏng nha bạn

  4. crisper says:

    bạn ơi! Bạn lukhach nói: “bài này bạn lấy lại hình ảnh mạng ngữ nghĩa trong bài giảng của thầy kiếm. vẽ lại đẹp hơn làm lại ma trận thi chuẩn hơn đấy nha!”
    share cho mình bài giảng thầy kiếm nói về phần mạng ngữ nghĩa đi bạn, mình kiếm hoài khong có cám ơn bạn.

  5. Linh says:

    Giúp mình với !
    Đoạn kích hoạt giải tam giác ở cuối ấy , bước đầu tiên là kích hoạt alpha beta và a
    Yếu tố a chỉ có trong công thức 1 và 3 , trên hình vẽ cũng biểu diễn là (-1) ở công thức 1 và 3 rồi
    Sau khi kích hoạt thì yếu tố a lại nhận thêm giá trị 1 ở công thức 4 . Đoạn này mình không hiểu lắm ai giúp mình với

  6. Harry_HV says:

    Em ở lớp CNTN04, em nghĩ bài này cần xây dựng cơ sở tri thức trước. Sử dụng cơ sở tri thức để xây dựng mạng ngữ nghĩa, và thực hiện suy diễn trên mạng ngữ nghĩa này. Hình như, mọi tri thức về tam giác (như công thức tính toán chẳng hạn) anh để luôn trong code ! Trường hợp lớn hơn, ví dụ như khoảng 200 công thức, mỗi công thức với nhiều yếu tố khác nhau nữa thì công việc sẽ trở nên cực kì khó khăn ! E cũng đang đụng tới bày này, đang đụng tới xử lí mấy công thức này…

  7. nguyễn duy hảo says:

    chào bạn!mình test thử code thấy một số lỗi và mình nghĩ rằng code này thiếu một công việc. khi xảy ra tính toán, giá trị biến mới phát sinh chưa được cập nhật mà bị cứng nhắc bởi các chỉ số mảng a bạn quy định cho từng biến .chỉ số mảng a này lưu giá trị biến nhập từ textbox.chỉ số này đại diện cho giá trị biến và không thay đổi trong suốt chương trình.chính điều này có kết quả sai!
    ví dụ anpha=30,beta=60 tính toán denta=90 rồi nhập a=8 tính toán b 13,8 đúng nhưng c sai c không bằng 16
    đây là ý kiến của mình có gì sai sót mong bạn góp ý

  8. Dark says:

    anh ơi cái bảng
    (1) (2) (3) (4) (5)
    a -1 0 0 -1 0
    b -1 -1 0 -1 0
    d 0 -1 0 -1 0
    a -1 0 -1 0 0
    b -1 -1 -1 0 0
    c 0 -1 -1 0 -1
    S 0 0 -1 0 -1
    hC 0 0 0 0 -1
    Khởi đầu : đỉnh a, b, a của đồ thị được kích hoạt.

    (1) (2) (3) (4) (5)
    a 1 0 0 1 0
    b 1 1 0 1 0
    d 0 -1 0 -1 0
    a 1 0 1 1 0
    b -1 -1 -1 0 0
    c 0 -1 -1 0 -1
    S 0 0 -1 0 -1
    hC 0 0 0 0 -1
    Trên cột (1), hiệu (1+1+1 – (-1)) = 4 nên dòng b sẽ được kích hoạt.

    (1) (2) (3) (4) (5)
    a 1 0 0 1 0
    b 1 1 0 1 0
    d 0 -1 0 -1 0
    a 1 0 1 1 0
    b 1 1 1 0 0
    c 0 -1 -1 0 -1
    S 0 0 -1 0 -1
    hC 0 0 0 0 -1
    Trên cột (4), hiệu (1+1+1 – (-1)) = 4 nên dòng d sẽ được kích hoạt.

    (1) (2) (3) (4) (5)
    a 1 0 0 1 0
    b 1 1 0 1 0
    d 0 1 0 1 0
    a 1 0 1 1 0
    b 1 1 1 0 0
    c 0 -1 -1 0 -1
    S 0 0 -1 0 -1
    hC 0 0 0 0 -1
    Trên cột (2), hiệu (1+1+1 + (1)) = 4 nên dòng c được kích hoạt.

    (1) (2) (3) (4) (5)
    a 1 0 0 1 0
    b 1 1 0 1 0
    d 0 1 0 1 0
    A 1 0 1 1 0
    B 1 1 1 0 0
    C 0 1 1 0 1
    S 0 0 -1 0 -1
    hC 0 0 0 0 -1
    Trên cột (3), hiệu (1+1+1 – (-1)) = 4 nên dòng S được kích hoạt.

    (1) (2) (3) (4) (5)
    a 1 0 0 1 0
    b 1 1 0 1 0
    d 0 1 0 1 0
    a 1 0 1 1 0
    b 1 1 1 0 0
    c 0 1 1 0 1
    S 0 0 1 0 1
    hC 0 0 0 0 -1
    có thể giải thick kỹ đc ko a em không hiểu cảm ơn a.

  9. Dung says:

    Bạn ơi có thể giải thích cho mình tại sao từ công thức Herong nếu biết cạnh a,b, S thì tính được cạnh c theo công thức như của bạn là:
    sqrt(a2+b2) + sqrt(a2*b2 – 4*S2)

  10. Pingback: [Representation] Semantic Network – Biểu diễn qua mạng ngữ nghĩa P2 | SEPTENI TECHNOLOGY Developer's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s