Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 11 kết quả

Đề tài: Thảo luận về thuật toán tìm đường đi ngắn nhất (có chi phí ít nhất) trên ma trận

  1. #1
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Mặc định Thảo luận về thuật toán tìm đường đi ngắn nhất (có chi phí ít nhất) trên ma trận

    Đây là bài gửi đầu tiên của mình kể từ khi tham gia diễn đàn, có gì sai sót mong các bạn thông cảm

    Bài 1 :
    Cho mê cung được biểu diễn trên ma trận cấp n*n. Nếu đang ở tọa độ (x,y) ta có thể di chuyển tới 4 điểm xung quanh theo chiều ngang và dọc giả sử có tọa độ là (p,q), và chi phí cho lần di chuyển đó bằng a[p][q]. Cho tọa độ điểm bắt đầu (S) và kết thúc (F), tìm đường đi có chi phí nhỏ nhất từ S->F.
    Input
    -Dòng đầu chứa n, tọa độ điểm bắt đầu và kết thúc.
    -n dòng tiếp theo chứa ma trận trọng số.
    Output
    -1 dòng duy nhất chứa chi phí ít nhất cho hành trình.

    Ví dụ:
    Input:
    3 1 1 3 1
    1 1 1
    9 9 1
    1 1 1
    Output:
    6

    Giải thích : tọa độ điểm bắt đầu và kết thúc có màu xanh. Từ ô (1,1) khi di chuyển đến ô(1,2) ta mất chi phí là 1. Từ (1,1) -> (2,1) chi phí là 9.

    Bài 2:
    Xét bàn cờ vuông kích thước n×n. Các dòng được đánh số từ 1 đến n, từ dưới lên trên. Các cột được đánh số từ 1 đến n từ trái qua phải.

    Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên bàn cờ có m (0 ≤ m ≤ n) quân cờ. Với m > 0, quân cờ thứ i ở ô (ri, ci), i = 1,2,..., m. Không có hai quân cờ nào ở trên cùng một ô. Trong số các ô còn lại của bàn cờ, tại ô (p, q) có một quân tượng. Mỗi một nước đi, từ vị trí đang đứng quân tượng chỉ có thể di chuyển đến được những ô trên cùng đường chéo với nó mà trên đường đi không phải qua các ô đã có quân

    Cần phải đưa quân tượng từ ô xuất phát (p, q) về ô đích (s,t). Giả thiết là ở ô đích không có quân cờ. Nếu ngoài quân tượng không có quân nào khác trên bàn cờ thì chỉ có 2 trường hợp: hoặc là không thể tới được ô đích, hoặc là tới được sau không quá 2 nước đi (hình trái). Khi trên bàn cờ còn có các quân cờ khác, vấn đề sẽ không còn đơn giản như vậy.

    Yêu cầu: Cho kích thước bàn cờ n, số quân cờ hiện có trên bàn cờ m và vị trí của chúng, ô xuất phát và ô đích của quân tượng. Hãy xác định số nước đi ít nhất cần thực hiện để đưa quân tượng về ô đích hoặc đưa ra số -1 nếu điều này không thể thực hiện được.

    Input
    Dòng đầu tiên chứa 6 số nguyên n, m, p, q, s, t.

    Nếu m > 0 thì mỗi dòng thứ i trong m dòng tiếp theo chứa một cặp số nguyên ri , ci xác định vị trí quân thứ i.

    Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

    Output
    Gồm 1 dòng duy nhất là số nước đi tìm được

    Example
    Input:
    8 3 7 2 1 4
    5 4
    3 4
    4 7

    Output:
    3
    Hạn chế:
    Trong tất cả các test: 1 ≤ n ≤ 200. Có 60% số lượng test với n ≤ 20
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  2. #2
    Ngày gia nhập
    07 2009
    Bài viết
    43

    Chào a hunter em xin làm bài 1 theo 2 cách thế này:
    C1)
    áp dụng thuật toán dijkstra()
    giả sử điểm đầu là x,y
    điểm cuối là x1,y1
    gọi l[i][j] là chi phí ít nhất từ x,y tới điểm i,j bất kì trên mt
    khởi tạo l[i][j]=100;
    l[x][y]=0(điểm bắt đầu chi phí tới nó là 0)
    trx[i][j]={0};
    try[i][j]={0};
    dùng để lưu vết
    2 mảng ax[]={0,-1,0,1}
    ay[]={-1,0,1,0};
    dùng để dịch chuyển bước đi
    áp dụng Dij như bt
    1) tìm l[i][j] tm
    -l[i][j] tự do(dùng mảng d[i][j] để làm điều này (!d[i][j]) thì i,j tự do
    -l[i][j] nhỏ nhất
    2) sửa nhãn những đỉnh kề với i,j thỏa mãn 1)
    sau đây xin viết code sửa nhãn
    PHP Code:
    void relax(int p,int q)
    {
        
    int i,u,v;
        for(
    i=0;i<4;i++)
        {
            
    u=p+ax[i];
            
    v=q+ay[i];
            if(
    ok(u,v) && (l[u][v]!=100) && (l[p][q]>l[u][v]+a[p][q]))
            {
                
    l[p][q]=l[u][v]+a[p][q];
                
    trx[p][q]=u;
                try[
    p][q]=v;
            }
        }

    Cách 2: Đệ quy quay lui(nhánh cận)
    cái này thì phổ biến
    chỉ viêc dùng hàm duyêt(int p,int q)
    mảng
    int a[10][10]={0},n,m;
    int Min_tr[10][10]={0},dem=0,min=0;
    PHP Code:
    void toi_uu()
    {
          
    int i,j;
          if(
    min>dem)
          {
                
    min=dem;
                for(
    i=1;i<=n;i++)
                for(
    j=1;j<=n;j++)
                
    Min_tr[i][j]=tr[i][j];
          }

    hàm này viêy như sau
    PHP Code:
    void duyet(int p,int q)
    {
        
    int i,u,v,so;
        for(
    i=0;i<4;i++)
        {
            
    u=p+ax[i];
            
    v=q+ay[i];
            if(
    d[u][v]==0)
            {
                
    so=dem;
                
    d[u][v]=1;
                
    tr[p][q]=i;//ghi lai huong
                
    dem+=a[u][v];
                if(
    u==x1 && v==x1)
                
    toi_uu();
                else
                
    duyet(u,v);
                
    d[u][v]=0;
                
    tr[p][q]=0;
                
    dem=so;
            }
        }

    Cách 3:
    dynamic programing
    gọi l[i][j] là khoảng cách nhỏ nhất từ i,j tới x,y;
    thì l[i][j] se bằng min l[ii][jj] của 4 điểm nằm cạnh nó + a[i][j];
    ---Hãy mạnh mẽ hơn chính chúng ta của ngày hôm qua---

  3. #3
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Thanks bạn đã góp ý.
    Bài 1 mình cũng dùng dijk, quay lui không chạy được những test lớn, còn dynamic program thì sẽ sai trong trường hợp đường đi xoắn ốc.
    Bài 2 mình tìm min(dijk k lần), với k là số nước đi đầu tiên có thể đi của con tượng. Mong các bạn góp ý.

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  4. #4
    Ngày gia nhập
    05 2009
    Nơi ở
    VietNam - HCM
    Bài viết
    32

    bài 1 mình tìm kiếm theo chiều rộng.
    dùng hàng đợi ưu tiên để lưu mảng các chi phí của các ô. cuối cùng khi nào ô đích được lấy ra khỏi hàng đợi ưu tiên thì dừng.
    hi vọng bạn hiểu

  5. #5
    Ngày gia nhập
    05 2009
    Nơi ở
    VietNam - HCM
    Bài viết
    32

    bài 2
    mình sẽ chia bàn cờ làm 2. nếu ô xuất phát và ô đích cùng một phía của bàn cờ. thì quân tượng sẽ ưu tiên đi vào các ô nằm trên đường chéo của bàn cờ(đường chéo có chứ ô đích). nếu ko được sẽ đi vào các đường chéo còn lại.
    nếu 2 ô nằm ở 2 bên của bàn cờ. mình sẽ ưu tiên đi vào các ôn có cùng chỉ số cột hoặc dòng của ô đích.
    các ô đã đi sẽ ko đi lại. vì vậy cuối cùng sẽ tìm được đường đến đích.
    tuy nhiên không đảm bảo là ngắn nhất.
    muốn đảm bảo là ngắn nhất thì sẽ phải kiểm tra các trường hợp đi được khác.
    cái này mình cũng dùng hàng đợi.

  6. #6
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Mặc định Thảo luận về thuật toán tìm đường đi ngắn nhất (có chi phí ít nhất) trên ma trận

    - Hàng đợi ưu tiên bạn dùng ở bài 1 là heap chăng, cứ lần lượt tìm nhãn và tối ưu thì là DIJK rồi còn gì
    - Bài 2 mình đảm bảo rằng cách của bạn sẽ bị quá thời gian trong trường hợp không tồn tại đường đi

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  7. #7
    Ngày gia nhập
    05 2009
    Nơi ở
    VietNam - HCM
    Bài viết
    32

    uh, dijktra cũng là một dạng của tìm kiếm theo chiều rộng mà.

  8. #8
    Ngày gia nhập
    05 2009
    Nơi ở
    VietNam - HCM
    Bài viết
    32

    thiển ý của mình thật là bưởi. xin mời các cao nhân vào trợ giúp.

  9. #9
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    bài 2 mình làm như sau:
    Vị trí bắt đầu là (i,j) con tượng (có thể) đi đến 4 điểm xung quanh.
    -Chọn lấy 1 điểm làm nước đi đầu tiên giả sử là (i+1,j+1), sau đó dijk tìm vị trí (p,q) nếu ba điểm (i,j) (i+1,j+1) và (p,q) thẳng hàng thì d[p][q]=0, ngược lại d[p][q]=1. Trong trường hợp này trace[i+1][j+1]=(i,j). Rồi tìm đến vị trí kết thúc (nếu có)
    -Kết quả sẽ làm min của 4 lần dijk

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  10. #10
    Ngày gia nhập
    05 2009
    Nơi ở
    VietNam - HCM
    Bài viết
    32

    Trích dẫn Nguyên bản được gửi bởi hunterphu Xem bài viết
    sau đó dijk tìm vị trí (p,q)
    mình không hiểu bước này bạn tìm thế nào
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

Các đề tài tương tự

  1. Lý thuyết giải thuật Thuật giải tìm đường đi ngắn nhất tửng đỉnh xuất phát qua tất cả các đỉnh và quay về chính nó như thế nào?
    Gửi bởi kitti trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 13-11-2012, 07:52 PM
  2. Trả lời: 0
    Bài viết cuối: 20-06-2012, 02:50 PM
  3. [Thảo Luận]UCWEB – Trình duyệt pro nhất nhì trên mobile
    Gửi bởi Mr.Duy trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 06-06-2012, 11:25 AM
  4. Trả lời: 1
    Bài viết cuối: 08-11-2011, 11:05 PM
  5. Thuật toán tìm đường đi ngắn nhất trong ma trận?
    Gửi bởi toraihand trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 4
    Bài viết cuối: 18-03-2011, 07:27 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn