|
| Tác giả | Thông điệp |
|---|
builan20689
Tổng số bài gửi : 98
Experience : 153
Đã được cảm ơn : 4
Join date : 09/12/2010
Age : 34
Đến từ : Hưng Yên city
 |  Tiêu đề: Toan roi rac  Fri Jan 07, 2011 9:45 am | |
| |
|
| | |
nguyenducanh
Tổng số bài gửi : 187
Experience : 306
Đã được cảm ơn : 14
Join date : 17/12/2010
Age : 34
Đến từ : Gia Lâm - Hà Nội
| | Tiêu đề: Re: Toan roi rac Mon Jan 10, 2011 8:20 pm | |
| |
|
| | |
builan20689
Tổng số bài gửi : 98
Experience : 153
Đã được cảm ơn : 4
Join date : 09/12/2010
Age : 34
Đến từ : Hưng Yên city
| | Tiêu đề: Re: Toan roi rac Tue Jan 11, 2011 6:24 am | |
| |
|
| | |
[K14A]ADMIN
![[K14A]ADMIN](https://2img.net/u/3414/13/44/87/avatars/1-61.gif)
Tổng số bài gửi : 408
Experience : 681
Đã được cảm ơn : 19
Join date : 07/12/2010
Age : 35
Đến từ : Hà Nội
| | Tiêu đề: Re: Toan roi rac Fri Mar 25, 2011 8:42 pm | |
| |
|
| | |
Nguyenhang88
Tổng số bài gửi : 3
Experience : 3
Đã được cảm ơn : 0
Join date : 31/03/2011
Age : 35
Đến từ : Nam Định
| | Tiêu đề: Re: Toan roi rac Sun May 01, 2011 2:37 pm | |
| |
|
| | |
big_big_girl
Tổng số bài gửi : 67
Experience : 94
Đã được cảm ơn : 7
Join date : 11/01/2011
| | Tiêu đề: Re: Toan roi rac Wed May 04, 2011 9:09 am | |
| |
|
| | |
ong.gia88
Tổng số bài gửi : 242
Experience : 292
Đã được cảm ơn : 13
Join date : 09/12/2010
Age : 36
Đến từ : Hòa Bình
| | Tiêu đề: Re: Toan roi rac Wed May 04, 2011 9:16 am | |
|  | |  | | HamilTon
Đường đi qua tất cả các đỉnh của đồ thị, mỗi đình đúng 1 lần được gọi là đường đi Hamilton.
Chu trình bắt đầu tại một đỉnh v nào đấy qua tất cả các đỉnh còn lại mỗi đỉnh đúng 1 lần sau đó quay trở lại v được gọi là chu trình Hamilton.
Đồ thị được gọi là đồ thị H nếu nó chứa chu trình H
Đồ thị được gọi là đồ thị nửa H nếu nó chứa đường đi H
Định lý:
Giả sử G là một đơn đồ thị liên thông có n đỉnh(n>=3). Khi đó có chu trình H nếu bậc của mỗi đỉnh ít nhất =n/2.
Thuật toán Prim
Cho G=(V,E) |V|=n
1. T=rỗng;
2. While T a. Chọn (u,v) thuộc E: + Có trọng số nhỏ nhất.
+ Có đỉnh liên thuộc trong T.
+ Khi thêm vào T ko tạo ra chu trình.
b. Thêm (u,v) vào T.
Thuật toán Dijktra.
Tìm đường đi ngắn nhất từ đỉnh u tới đỉnh v nào đó
Chọn đồ thị G liên thông có trọng số G=( V,E)
1 khởi tạo
a, Gán nhãn +L(u):=0.
+L(x)=oo(vô cùng) với mọi x thuộc V\u
B, V* = rỗng (V* là tập đỉnh được duyệt).
2. Xác định độ dài đường đi ngắn nhất từ u đến v;
While v không thuộc V* do
a. tìm đỉnh a sao cho L(a)=min( L(x),x thuộc V\ V*)
b. V* := V* U (a).
c. For all x thuộc ( V\ V*) n ( danh sách kề của a)
If L(x) + f(a,x) < L(x) then L(x)= L(a) + f(a,x)
{ L(V) là độ dài đường đi ngắn nhất từ u -> v }
{ Thứ tự các đỉnh thêm vào V* là đường đi u -> v}
Thuật toán KRUSKAL
Cho G=(V,E) |V|=n
1. T=rỗng;
2. While T a. Chọn (u,v) thuộc E: + Có trọng số nhỏ nhất
+ Khi thêm vào T ko tạo ra chu trình.
b. Thêm (u,v) vào T.
Tim kiem theo chieu rong
Procedure BFS (S đỉnh)
1 Đưa S vào hàng đợi
2. Đánh dấu đỉnh S đã duyệt
3 While hàng đợi khác rỗng do
+ Lấy 1 đỉnh u từ đầu hàng đợi
+ For mỗi đỉnh v thuộc danh sách kề của u
+if v chưa đánh dấu thì
-- Thêm v vào sau hàng đợi
-- Đánh dấu v đã duyệt
-- Thực hiện phép toán với v
Tim kiem theo chieu sau
Procedure DFS(S dinh).
1. Danh dau dinh S da duyet.
2. For moi dinh v thuoc danh sach ke cua S
+ if v chua danh dau then xu ly v
+ Goi lai de quy DFS(v)
|  | |  |
|
|
| | |
Tesulakata
Tổng số bài gửi : 141
Experience : 240
Đã được cảm ơn : 1
Join date : 18/05/2011
Age : 48
Đến từ : Heaven
| | Tiêu đề: Re: Toan roi rac Wed May 18, 2011 10:55 pm | |
| | | | | - ong.gia88 đã viết:
- HamilTon
Đường đi qua tất cả các đỉnh của đồ thị, mỗi đình đúng 1 lần được gọi là đường đi Hamilton.
Chu trình bắt đầu tại một đỉnh v nào đấy qua tất cả các đỉnh còn lại mỗi đỉnh đúng 1 lần sau đó quay trở lại v được gọi là chu trình Hamilton.
Đồ thị được gọi là đồ thị H nếu nó chứa chu trình H
Đồ thị được gọi là đồ thị nửa H nếu nó chứa đường đi H
Định lý:
Giả sử G là một đơn đồ thị liên thông có n đỉnh(n>=3). Khi đó có chu trình H nếu bậc của mỗi đỉnh ít nhất =n/2.
Thuật toán Prim
Cho G=(V,E) |V|=n
1. T=rỗng;
2. While T a. Chọn (u,v) thuộc E: + Có trọng số nhỏ nhất.
+ Có đỉnh liên thuộc trong T.
+ Khi thêm vào T ko tạo ra chu trình.
b. Thêm (u,v) vào T.
Thuật toán Dijktra.
Tìm đường đi ngắn nhất từ đỉnh u tới đỉnh v nào đó
Chọn đồ thị G liên thông có trọng số G=( V,E)
1 khởi tạo
a, Gán nhãn +L(u):=0.
+L(x)=oo(vô cùng) với mọi x thuộc V\u
B, V* = rỗng (V* là tập đỉnh được duyệt).
2. Xác định độ dài đường đi ngắn nhất từ u đến v;
While v không thuộc V* do
a. tìm đỉnh a sao cho L(a)=min( L(x),x thuộc V\ V*)
b. V* := V* U (a).
c. For all x thuộc ( V\ V*) n ( danh sách kề của a)
If L(x) + f(a,x) < L(x) then L(x)= L(a) + f(a,x)
{ L(V) là độ dài đường đi ngắn nhất từ u -> v }
{ Thứ tự các đỉnh thêm vào V* là đường đi u -> v}
Thuật toán KRUSKAL
Cho G=(V,E) |V|=n
1. T=rỗng;
2. While T a. Chọn (u,v) thuộc E: + Có trọng số nhỏ nhất
+ Khi thêm vào T ko tạo ra chu trình.
b. Thêm (u,v) vào T.
Tim kiem theo chieu rong
Procedure BFS (S đỉnh)
1 Đưa S vào hàng đợi
2. Đánh dấu đỉnh S đã duyệt
3 While hàng đợi khác rỗng do
+ Lấy 1 đỉnh u từ đầu hàng đợi
+ For mỗi đỉnh v thuộc danh sách kề của u
+if v chưa đánh dấu thì
-- Thêm v vào sau hàng đợi
-- Đánh dấu v đã duyệt
-- Thực hiện phép toán với v
Tim kiem theo chieu sau
Procedure DFS(S dinh).
1. Danh dau dinh S da duyet.
2. For moi dinh v thuoc danh sach ke cua S
+ if v chua danh dau then xu ly v
+ Goi lai de quy DFS(v)
Lớp B đang hoàn thiện seris code c# - giải quyết các vấn đề duyệt cây, tìm kiếm
Hiện tại đã giải quyết được Tìm kiếm theo chiều sâu, skurkal và Dijktra
Các bạn tham khảo và đóng góp để phát triển tiếp các giải thuât khác nhé
Tất cả các code đều mô phỏng = đồ họa. do đó có thể dùng làm bài tập lớn môn kĩ thuật đồ họa .... 1 công đôi việc
Link tại đây
http://k14ktqs.cntt.in/ | | | |
|
|
| | |
builan20689
Tổng số bài gửi : 98
Experience : 153
Đã được cảm ơn : 4
Join date : 09/12/2010
Age : 34
Đến từ : Hưng Yên city
| | Tiêu đề: Re: Toan roi rac Mon May 23, 2011 9:57 pm | |
| |
|
| | |
Sponsored content
| | Tiêu đề: Re: Toan roi rac | |
| |
|
| | |
|
Tìm kiếm 
Đăng ký 
