Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    1 Thuật toán nhánh cận on Mon Jun 20, 2011 9:41 pm

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Gửi các anh chị một số đề luyện thi của HV KTQS vài năm lại đây liên quan đến Thuật toán nhánh cận để tìm 1 hoặc 2 (nếu có) hành trình du lịch tối ưu cho bài toán người du lịch với ma trận kinh phí cho sẵn.
    Đề 2009:
    [You must be registered and logged in to see this image.]
    Đề 2008:
    [You must be registered and logged in to see this image.]


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    Admin


    Quản trị viên
    Quản trị viên
    Thuật toán nhánh cận
    Những bài toán áp dụng thuật toán nhánh cận không phải là bài toán khó. Vì đã xây dựng thành thuật toán thì cứ thế mà áp dụng. Những bài toán này, chẳng đòi hỏi Khách viếng thăm là người phải thông minh xuất chúng gì cả, mà là những bài toán yêu cầu sinh viên phải tỉ mỉ, cẩn thận và thực tế rất chua chát là những bài này khi cho vào các bài thi lại là bài giết thí sinh nhiều nhất. Bản thân nó không khó, nhưng vì khi giải nó rất dài dòng và tốn kém (tốn giấy đã đành vì mỗi bài phải viết tới vài trang) nó còn dã man ở chỗ là khiến thí sinh phải dành rất nhiều thời gian làm các phép tính cộng cộng, trừ trừ đơn giản. Các đề thi đưa thuật toán nhánh cận để tuyển thạc sĩ hay tiến sĩ thì có nghĩa là người ra đề cũng muốn biến các "thạc sĩ, tiến sĩ tương lai" thành một chút công nhân lao động khổ sai. Nó âm thầm tiêu diệt nguồn tài sản quý nhất của người đi thi đó là thời gian, cho dù thế nào đi nữa, Khách viếng thăm cố làm bài này cũng được trả công rất bạc bẽo. Nếu đề thi có câu này, thì đó là câu bạc bẽo nhất để Khách viếng thăm luôn hiểu rằng cuộc đời nhiều khi thời gian, công sức của mình bỏ ra nhiều nhưng thu được chẳng được bao nhiêu.

    Tôi với Admin đều là người đi thi, chẳng có lời khuyên gì. Nếu chẳng biết làm bài nào thì lấy tạm câu này ra làm để giết thời gian lấy phần chăm chỉ, cẩn thận bù vào sự thiếu thông minh, kém cỏi thôi thì cũng là điều vạn bất đắc dĩ. Lẽ ra câu hỏi dạng này thì chỉ nên để ở phần nghiên cứu thôi, cho vào đề thi thì nhiều khi tiêu tốn hai thứ đã nói ở trên đó là thời gian và công sức của cả người đi thi và người chấm thi. Người ra đề dạng này chắc Khách viếng thăm hiểu được sẽ là người như thế nào rồi đấy.

    Tôi copy cái ý đoạn văn trên từ một blogger google trên mạng để làm mào đầu cho câu chuyện của chúng ta về cái thuật toán này. Mỗi người nói một kiểu về nó, nhưng có hỏi 100% thí sinh đi thi thì chẳng ai thích làm câu hỏi dạng này cả, chỉ cần để biết thôi. Mấy năm rồi đề thi vào Học viện KTQS không có, nhưng những năm trước có, những đề luyện tập luôn có. Năm nay câu hỏi dạng này có hay không thật khó trả lời, nhưng có một điều chắc chắn rằng, nếu có cho dù biết cách làm mười mươi, nhưng sẽ có nhiều thí sinh bỏ qua, nếu các câu khác hòm hòm. Chẳng ai đâm đầu vào làm bằng tay cái công việc vô bổ này, vì có thể dùng thuật toán hoặc viết giải thuật chỉ mất vài dòng, nhưng cứ làm ra thì tiêu hao thời gian và tàn lực của chúng ta không hề ít.

    Tôi cũng chẳng tài ba gì, thôi thì mình lấy tí cần cù gõ vào đây làm căn cứ cho thiên hạ copy vậy, vì có google chẳng có thằng điên nào gõ một bài nhánh cận trên mạng nên hồn. Và cũng để cho những bạn nào vì một lý do bận việc đi đâu đó không đi học được có chỗ để mà tham khảo.

    Trong bài toán người du lịch, khi tiến hành tìm kiếm lời giải chúng ta sẽ phân tập các hành trình ra thành 2 tập con:

    - Một tập chứa hành trình một cung (i, j) nào đó.
    - Tập kia gồm những hành trình không chứa cung này.

    Ta gọi việc làm đó là phân nhánh và mỗi tập con nói trên sẽ được gọi là một nhánh hay một nút của cây tìm kiếm.
    [You must be registered and logged in to see this image.]
    Việc phân nhánh sẽ được thực hiện dựa trên một quy tắc Hơristic nào đó cho phép ta rút ngắn quá trình tìm kiếm phương án tối ưu. Sau khi phân nhánh ta sẽ tính cận dưới của giá trị hàm mục tiêu của mỗi một tập con (trên 2 tập trên).Việc tìm kiếm sẽ được tiếp tục trên tập con có giá trị cận dưới nhỏ hơn.
    Thủ tục này sẽ tiếp tục cho đến khi thu được một hành trình đầy đủ tức là một phương án của bài toán người du lịch. Khi đó ta chỉ việc xét những tập con các phương án nào có cận dưới nhỏ hơn giá trị hàm mục tiêu tại phương án đã tìm được.
    Quá trình phân nhánh và tính cận dưới trên tập các phương án của bài toán thông thường cho phép rút ngắn một cách đáng kể quá trình tìm kiếm do ta loại được khá nhiều tập con chắc chắn không chứa phương án tối ưu.

    1. Thủ tục rút gọn (tính chi phí cận dưới)
    Rõ ràng tổng chi phí của một hành trình của người du lịch sẽ chứa:
    + đúng một phần tử của mỗi dòng
    + đúng một phần tử của mỗi cột
    trong ma trận chi phí C. Do đó, nếu ta trừ đi vào mỗi phần tử của một hàng (một cột) một số α thì chi phí của tất cả hành trình sẽ giảm đi α , vì thế hành trình tối ưu sẽ không thay đổi.
    Nên trừ để mỗi dòng, mỗi cột đều chứa ít nhất một số 0 thì tổng các hằng số trừ đó sẽ cho ta cận dưới của mọi hành trình. Thủ tục này gọi là thủ tục rút gọn.

    2. Thủ tục cung phân nhánh
    Sau khi rút gọn, mỗi hàng, mỗi cột có ít nhất 1 phần tử 0.
    Đối với mỗi phần tử 0 này, ta tính chỉ số của nó là tổng các phần tử khác không đang xét và nhỏ nhất tương ứng với hàng và cột đó. Chọn phần tử 0 có chỉ số lớn nhất, tương ứng với cung cần chọn để phân nhánh và đặt phần tử đối xứng với nó qua đường chéo là ∞.

    Sau khi đã tiến hành tính cận dưới và phân nhánh, chia các hành trình làm 2 tập con.
    - Tập T1 gồm các hành trình chứa cung (p, q)
    - Tập T2 gồm các hành trình không chứa cung (p, q)
    Đối với tập T1, ma trận chi phí tương ứng C1 nhận được từ ma trận C bằng cách loại bỏ hàng p cột q, kích thước giảm xuống 1 bậc.
    Đối với tập T2 ma trận chi phí tương ứng C2 nhận được từ ma trận C bằng cách đặt Cpq = ∞ , tức là trong bước tiếp theo không chọn cung (p, q) nữa.



    Được sửa bởi Admin ngày Sun Jul 03, 2011 1:23 pm; sửa lần 2.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    3 Re: Thuật toán nhánh cận on Sat Jul 02, 2011 11:33 pm

    Admin


    Quản trị viên
    Quản trị viên
    Bây giờ ta giải một bài toán áp dụng thuật toán nhánh cận để biết cuộc đời nó phũ phàng đến thế nào nhé:
    Ma trận chi phí sẽ cho như sau:







    3

    93

    13

    33

    9



    4



    77

    42

    21

    16

    C =

    45

    17



    36

    16

    28



    39

    90

    80



    56

    7



    28

    46

    88

    33



    25



    3

    88

    18

    46

    92


    Để rút gọn ma trận theo hàng thực hiện như sau:
    Viết những con số nhỏ nhất của hàng ra một cột bên ngoài tay phải. Số được chọn là số đã tô đỏ. Gọi là αi. Cộng tổng bọn chúng lại là số M.
    Ta có:

















    αi





    3

    93

    13

    33

    9

    3



    4



    77

    42

    21

    16

    4

    C =

    45

    17



    36

    16

    28

    16



    39

    90

    80



    56

    7

    7



    28

    46

    88

    33



    25

    25



    3

    88

    18

    46

    92



    3











    M

    =

    58


    Thực hiện trừ các số trong hàng cho con số nhỏ nhất của hàng này (Trừ hết giá trị cho số màu đỏ) ta được:








    0

    90

    10

    30

    6



    0



    73

    38

    17

    12

    C =

    29

    1



    20

    0

    12



    32

    83

    73



    49

    0



    3

    21

    63

    8



    0



    0

    85

    15

    43

    89









    15

    8





    Tương tự, làm theo cột ta thấy chỉ có 2 cột có giá trị nhỏ nhất khác 0 là 15 và 8, thực hiện trừ các số trong cột chứa 2 giá trị đó, cho chính giá trị màu đỏ. Ta được ma trận rút gọn:








    0

    75

    2

    30

    6





    0



    58

    30

    17

    12



    C =

    29

    1



    12

    0

    12





    32

    83

    58



    49

    0





    3

    21

    48

    0



    0





    0

    85

    0

    35

    89















    M

    =

    81

    M lúc này được tính bằng cách cộng các giá trị đã trừ gồm: 58 + 15 + 8 = 81. Lưu ý, sách in đúng, nhưng trong mấy cái quyển phô tô, học sinh khóa trước họ sửa sai vào đó đấy nha, đừng có mà theo số của họ.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    4 Re: Thuật toán nhánh cận on Sun Jul 03, 2011 12:16 am

    Admin


    Quản trị viên
    Quản trị viên
    Bây giờ ta sang bước chọn cung phân nhánh để tính B(i, j). Làm như thế nào? Đầu tiên đánh dấu các phần tử có giá trị 0. Rồi, khoanh nó lại. Ở hình vẽ chính là số màu đỏ đó nha. Làm từng số phần tử mang giá trị 0 một nha. Tìm trong hàng chứa phần tử 0 này xem giá trị nào nhỏ nhất gọi là ri tạm tô màu đỏ, tìm trong cột chứa phần tử 0 này xem giá trị nào nhỏ nhất gọi là si tạm tô màu đỏ,cộng các số màu đỏ lại, ghi ra một số be bé bên cạnh màu hồng làm chỉ số. Ví dụ số 3 được tạo thành bằng cách cộng số 1 và số 2. Tương tự ở các vị trí khác. Ở đây được phóng to lên cho dễ nhìn. Sau đó chọn trong số các số màu hồng giá trị nào lớn nhất để làm căn cứ phân tập. Do hàng 6, cột 3 (Phần tử 6, 3) có giá trị chỉ số lớn nhất là 48.
    [You must be registered and logged in to see this image.]

    Vậy chọn cung (6, 3) để phân tập thành 2 nhánh:
    Nhánh T1 gồm các hành trình chứa cung (6, 3) có ma trận chi phí C1 tương ứng, bằng cách bỏ hàng 6 và cột 3. Đặt C(3, 6) = ∞ ta có:
    [You must be registered and logged in to see this image.]
    Nhánh T2, gồm các hành trình không chứa cung (6, 3) có ma trận chi phí C2 bằng cách thay C (6, 3) = ∞ ta có:
    [You must be registered and logged in to see this image.]
    Ta thấy C2 có thể rút gọn theo phương pháp trên vì cột 3 có thể trừ tất cả đi 48, như vậy chi phí cận dưới của nhánh này sẽ tăng lên là M = 81 + 48 = 129


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    5 Re: Thuật toán nhánh cận on Sun Jul 03, 2011 10:39 am

    Admin


    Quản trị viên
    Quản trị viên
    Xét tiếp nhánh T1 có chi phí cận dưới M = 81 nhỏ hơn, Khách viếng thăm hãy tiếp tục tính chỉ số các phần tử 0 để chọn cung phân nhánh. Cách làm như phần trên nha. Ta có, ở đây ta đánh lại số hàng và cột vì đã bỏ đi hàng 6  và cột 3 ở bước trên, nên nếu không đánh lại số sẽ nhầm lẫn, và công của Khách viếng thăm và tôi sẽ thành công cốc:
    [You must be registered and logged in to see this image.]
    M = 81
    Như vậy phần tử 0 tương ứng với hàng 4 cột 6 (hay cung 4, 6) có chỉ số lớn nhất là 32, ta tiếp tục chọn cung này để phân nhánh cho tập T1 gồm:
    - Nhánh T11 gồm cách hành trình chứa (6, 3) và (4, 6) rõ ràng 2 cung này không tạo thành chu trình con kín. Ma trận chi phí C11 tương ứng (sau khi bỏ hàng 4, cột 6  và đặt C6,4 = ∞ như cách làm ở các bước trên) sẽ như sau:
    [You must be registered and logged in to see this image.]
    - Nhánh T12 gồm các hành trình chứa cung (6, 3) nhưng không chứa cung (4, 6) có ma trận chi phí C12 tương ứng. Thay C4,6 = ∞ ta có:
    [You must be registered and logged in to see this image.]
    Ta thấy có thể rút gọn bằng cách trừ hàng 4 cho 32, nên chi phí cận dưới của C12 sẽ là 81 + 32 = 113.
    Như vậy ta sẽ phải chọn tiếp nhánh T11.
    Làm tiếp thế nào?
    Lại tính chỉ số các phần tử 0, chọn chỉ số to nhất phân nhánh. Ta lại có:
    [You must be registered and logged in to see this image.]
    Tiếp tục chọn cung này để phân nhánh cho tập T11, phân làm 2
    Nhánh T111 gồm các hành trình chứa (6, 3), (4, 6) và (2, 1) rõ ràng cung này không tạo thành chu trình con khép kín Ma trận chi phí tương ứng C111 được tạo → Bỏ hàng và cột của chỉ số to nhất này là bỏ hàng 2, cột 1. Đặt c12 = ∞ ta có:
    [You must be registered and logged in to see this image.]
    Rút gọn bằng cách trừ các phần tử cột 4 cho 2, và trừ các phần tử hàng 3 cho 1.
    Chi phí cận dưới bằng M = 81 + 2 + 1 = 84.
    [You must be registered and logged in to see this image.]


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    6 Re: Thuật toán nhánh cận on Sun Jul 03, 2011 12:44 pm

    Admin


    Quản trị viên
    Quản trị viên
    Nhánh T112 gồm các hành trình chứa cung (6, 3), (4, 6) và không chứa cung (2, 1). Ta thay C21 = ∞ sẽ nhận được ma trận chi phí C112 tương ứng như sau:
    [You must be registered and logged in to see this image.]
    Có thể trừ hàng 1 cho 2, hàng 2 cho 17, cột 1 cho 3, cột 2 cho 1 để rút gọn, ta sẽ nhận được:
    Chi phí cận dưới sẽ là M = 81 + 3 + 1 + 2 + 17 = 104. Để đây đã, tý nữa xét.
    Tiếp tục xét nhánh T111, tính các chỉ số:
    [You must be registered and logged in to see this image.]
    Có thể lấy cung (3, 5) hoặc (2, 4) vì cùng có chỉ số là 28. Thôi ta chọn 1 nhé, chọn cung (3, 5) để phân nhánh là 2 tập:
    - Tập T1111 gòm các hành trình chứa (6, 3), (4, 6), (2, 1) và (3, 5) các cung này không tạo thành các chu trình con kín. thì bớt bỏ hàng 3, cột 5 ta có:
    [You must be registered and logged in to see this image.]
    Rút gọn bằng cách trừ các phàn tử cột 2 cho 20:
    [You must be registered and logged in to see this image.]
    Khi ma trận chi phí còn lại là cấp 2, ta chọn 2 cung còn lại theo đường chéo ao cho không tạo thành chu trình con kín và có tổng bé hơn. Trường hợp này là (5, 2) và (1, 4).
    Như vậy có được một hành trình hoàn chỉnh là:
    T = {(6, 3), (4, 6), (2, 1), (3, 5), (5, 2), (1, 4)} với chi phí G = 84 + 20 = 104.
    Viết lại cho đúng thứ tự:
    T = {(1, 4), (4, 6), (6, 3), (3, 5), (5, 2), (2, 1)} với chi phí G = 104.
    Đường đi: 1 → 4 → 6 → 3 → 5 → 2 → 1


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    7 Re: Thuật toán nhánh cận on Sun Jul 03, 2011 1:15 pm

    Admin


    Quản trị viên
    Quản trị viên
    Nhánh T1112 gồm các hành trình chứa các cung (6, 3), (4, 6), (2, 1) và không chứa cung (3, 5) có ma trận chi phí bằng cách thay c35 = ∞ ta có:
    [You must be registered and logged in to see this image.]
    Có thể rút gọn bằng trừ các phần tử cột 5 cho 28.
    Ta thấy chi phí cận dưới này M = 81 + 28 = 109 mặc dù chưa hết chu hành trình mà đã lớn hơn chi phí G = 104 nên bỏ qua.
    Xét tất cả các chi phí cận dưới của các nhánh đã bỏ qua thấy có nhánh T112 gồm các hành trình chứa cung (6, 3) và (4, 6) và không chứa cung (2, 1) có M = 103 nhỏ hơn G = 104 nên có thể xét tiếp. Rút gọn ta có:
    [You must be registered and logged in to see this image.]
    Tương tự, Khách viếng thăm tự xét tiếp để lấy hành trình nha. Nếu hành trình < 104 thì lấy, lớn hơn thì thôi nha.
    Nếu xét ra còn dài nữa. mà ngay cả sách giáo khoa còn sai lung tung nữa là ta.
    Mệt thế đấy.
    Cuối cùng phải kết luận hành trình tối ưu sẽ là hành trình: ?
    Có tổng chi phí là: ?
    Đường đi là: ?


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Tuan Diep


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    về phần bài tập:
    bắt đầu từ bước tính C112, trong bước này anh Admin lại đặt C12=0 chứ không phải C12=Vô cùng, nên M=101 chứ không phải M=104 => dẫn đến cuối cùng chúng ta còn phải xét tiếp nhánh T112 này.
    Mong sao thi không có dạng này nhỉ các anh nhỉ. ~) ~)


    ================

    9 Re: Thuật toán nhánh cận on Wed Jul 13, 2011 10:19 am

    Admin


    Quản trị viên
    Quản trị viên
    Theo lý thuyết của thầy P giảng trên lớp, thì ngay cả các sách chúng ta hiện có trong tay vẫn còn thiếu điều kiện. Nghĩa là, chúng ta còn phải đặt tất cả các cạnh mà có thể khiến hình thành chu trình con đều phải bằng ∞. Mặc dù ngầm định là tính nhánh và cận theo cạnh, chúng ta cũng cần biết cách làm theo đỉnh thì nó như thế nào?

    Đề bài thầy trên lớp như vầy:
    [You must be registered and logged in to see this image.]
    Ở đây, cột trái và hàng đỉnh là hàng ghi chỉ số cho dễ quan sát nha.
    Giải:
    Không mất tính tổng quát, chọn xuất phát là đỉnh 1. Ta có Cmin = 2.
    1) Nếu sang 2:
    w = 3
    h = 11
    f* = ∞
    Lý giải cách tính:
    w: Vì ta xuất phát từ 1 nên phải tra ở hàng 1. Ta đi đến đỉnh 2, chọn cột 2. Tra bảng hàng 1 cột 2 được giá trị 3.
    h: Được tính bằng cách lấy w + số cạnh cần qua * Cmin. Ở đây w = 3 như cách tính trên, cần phải qua 4 cạnh nữa, Cmin = 2, nên
    h = 3 + 4*2 = 11
    Vì chưa có hành trình nên f* = ∞
    2) Nếu sang 3:
    w = 14
    h = 22
    f* = ∞
    3) Nếu sang 4:
    w = 18
    h = 26
    f* = ∞
    4) Nếu sang 5:
    w = 15
    h = 13
    f* = ∞
    Vậy chọn sang 2, đường đi 1 → 2, f* = ∞
    5) Nếu sang 3
    w = 7
    h = 13
    f* = ∞
    Lý giải cách tính:
    w: Vì ta xuất phát từ 1, đi đến 2, đang ở 2 để đi tiếp nên phải tra ở hàng 2. Ta đi đến đỉnh 3, chọn cột 3. Tra bảng hàng 2 cột 3 được giá trị 4. Giá trị này phải cộng với đoạn 1 2 có độ dài 3, nên ta có w = 3 + 4 = 7.
    h: Được tính bằng cách lấy w + số cạnh cần qua * Cmin. Ở đây w = 7 như cách tính trên, cần phải qua 3 cạnh nữa, Cmin = 2, nên
    h = 7 + 3*2 = 13
    Vì chưa có hành trình nên f* = ∞
    6) Nếu sang 4
    w = 25
    h = 31
    f* = ∞
    7) Nếu sang 5
    w = 23
    h = 29
    f* = ∞
    Vậy chọn sang 3, đường đi 1 → 2 → 3, f* = ∞
    8) Nếu sang 4
    w = 23
    h = 27
    f* = ∞
    9) Nếu sang 5
    w = 11
    h = 15
    f* = ∞
    Vậy chọn sang 5, đường đi 1 → 2 → 3 → 5, f* = ∞
    10) Không còn lựa chọn, sang 4
    w = 16
    h = 18
    f* = ∞
    11) Không còn lựa chọn, về 1
    w = 22
    h = 22
    f* = 22
    Lý giải kết quả:
    Do kết thúc một hành trình nên h = w = f*
    Đường đi tạm thời là:
    1 → 2 → 3 → 5 → 4 → 1
    f* tạm thời = 22
    12) Quay về 8:
    h = 27 > f* loại.
    13) Quay về 7:
    h = 29 > f* loại.
    14) Quay về 6:
    h = 31 > f* loại.
    15) Quay về 4:
    h = 23 > f* loại.
    16) Quay về 3:
    h = 26 > f* loại.
    17) Quay về 2:
    h = 22 = f*
    18) Nếu sang 2
    w = 23
    h = 29 > f* loại
    19) Nếu sang 4
    w = ...
    h = ... > f* loại
    20) Nếu sang 5
    w = ...
    h = ... > f* loại
    Vậy đường đi tối ưu của bài toán là: 1 → 2 → 3 → 5 → 4 → 1 với f* = 22


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    10 Re: Thuật toán nhánh cận on Sun Aug 07, 2011 4:12 pm

    vinhct


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    thi gặp dạng này (nhánh và cận) làm chắc chết mất, dài dòng lê thê, dễ nhầm lẫn, tốn thời gian

    http://ictprovn.net

    11 Re: Thuật toán nhánh cận on Sun Jun 24, 2012 3:45 pm

    tuyen_i7u


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    cảm ơn bạn admin 1 lần nữa nhé

    12 Re: Thuật toán nhánh cận on Mon Aug 06, 2012 4:02 pm

    huutaisc


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    vinhct đã viết:thi gặp dạng này (nhánh và cận) làm chắc chết mất, dài dòng lê thê, dễ nhầm lẫn, tốn thời gian
    Mình thấy các bạn nên vẽ dạng cây ,giống như ví dụ trong slide thầy đưa .Nó sẽ trực quan và ít bị rối hơn.

    13 Re: Thuật toán nhánh cận on Sat Oct 27, 2012 9:08 pm

    Khờ Tâm


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    mọi người ơi??? gửi slide của thầy lên em xem với càng nhanh càng tốt ạ. em cảm ơn.

    14 Re: Thuật toán nhánh cận on Sat Oct 27, 2012 9:12 pm

    Khờ Tâm


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    mà em hỏi với có hai loại tuần tự nhánh cận và song song nhánh cận đúng không ạ. Mà có thể chỉ rõ cho em về hai cái này được không ạ

    15 Re: Thuật toán nhánh cận on Wed Nov 28, 2012 5:32 am

    nguyenphucanh.soict


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Cảm ơn admin về những chia sẻ rất bổ ích đó!!! ~) :D

    16 Re: Thuật toán nhánh cận on Mon Mar 04, 2013 6:12 pm

    anhhoc123


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Ai co CODE thuat toan tren ko? gui cho minh voi? :(

    17 Re: Thuật toán nhánh cận on Tue Mar 12, 2013 9:53 pm

    xuantd93


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    thanks

    18 Re: Thuật toán nhánh cận on Sat May 03, 2014 12:31 pm

    mstmgz


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    cho mình hỏi chút, trường hợp mà bắt đc những 2 số 0 có cùng một chỉ số lớn nhất trong ma trận rút gọn thì xử lý sao nhỉ, bỏ cả 2 cung đó hay chia thành 2 trường hợp để tách

    chaucp88


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Có anh chị nào có source code của dạng nhánh cận này không> cho mình xin với :)

    20 Re: Thuật toán nhánh cận Today at 9:37 pm

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Have a free blog with Sosblogs