Từ 1 tới 10 trên tổng số 10 kết quả

Đề tài: C++ :: SourceCode thuật toán A* (A sao) tìm đường đi ngắn nhất.

  1. #1
    Ngày gia nhập
    12 2009
    Bài viết
    74

    Mặc định C++ :: SourceCode thuật toán A* (A sao) tìm đường đi ngắn nhất.

    Thuật toán A sao (A star) là thuật toán được dùng phổ biến nhất để tìm đường trong game.

    Mình viết bằng C++, gồm 4 class:



    Test:

    Tìm đường đi ngắn nhất từ A tới J trong hình sau:



    Kết quả:



    Code Test:

    PHP Code:
    #include <stdio.h>
    #include <conio.h>
    #include "AStar.h"

    Node *= new Node('A'00);
    Node *= new Node('B'20);
    Node *= new Node('C'70);
    Node *= new Node('D'41);
    Node *= new Node('E'22);
    Node *= new Node('F'53);
    Node *= new Node('G'03);
    Node *= new Node('H'45);
    Node *= new Node('I'16);
    Node *= new Node('J'75);

    void MyTest()
    {
        
    A->BiConnectTo(B);
        
    A->BiConnectTo(E);
        
    A->BiConnectTo(G);

        
    B->BiConnectTo(C);
        
    B->BiConnectTo(D);
        
    B->BiConnectTo(E);

        
    C->BiConnectTo(D);
        
    C->BiConnectTo(F);
        
    C->BiConnectTo(J);

        
    D->BiConnectTo(E);
        
    D->BiConnectTo(F);
        
    D->BiConnectTo(H);

        
    E->BiConnectTo(G);
        
    E->BiConnectTo(H);

        
    F->BiConnectTo(J);

        
    G->BiConnectTo(H);

        
    H->BiConnectTo(I);

        
    I->BiConnectTo(J);
    }

    int main()
    {
        
    MyTest();
        
    Node *start A;
        
    Node *target J;

        
    AStar astar;

        
    bool success astar.Calculate(starttarget);
        if (
    success)
        {
            
    printf("Find Path: ");
            for (
    int i 0astar.GetLengthPath(); i++)
                
    printf("%c "astar.Path[i]->name);
        }
        else
            
    printf("Can't find path");

        
    getch();
        return 
    0;

    Cách sử dụng lớp Node và Astar:

    1. Tạo node mới:
    PHP Code:
    Node *node = new Node(char nameint xint y); 
    trong đó name là tên của node (kiểu char), x, y là tọa độ node.

    2. Liên kết các node:
    PHP Code:
    ConnectTo để kết nối 1 chiềuBiConnectTo để kết nối 2 chiềutương tự với DisconnectTo và BiDisconnectTo để hủy kết nối
    3. Tạo đối tượng A sao:
    PHP Code:
    AStar astar
    4. Tính toán tìm đường:
    PHP Code:
    bool success astar.Calculate(starttarget); 
    5. Nếu success trả về true tức là tìm ra đường, để lấy độ dài đường đi ngắn nhất tìm được
    PHP Code:
    astar.GetLengthPath(); 
    Các node trên đường đi ngắn nhất đó lưu trong mảng astar.Path[] từ astar.Path[0] đến astar.Path[astar.GetLengthPath() - 1]

    Source code mình đính kèm bên dưới:
    Attached Files Attached Files

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

    bạn nào muốn giải thích rõ về thuật toán này mail cho mình qua : anhpt.csit@gmail.com

  3. #3
    Ngày gia nhập
    08 2009
    Bài viết
    6

    Mặc định Thừa CLASS

    Trong C++ có hỗ trợ PriorityQueue rồi bạn, đâu cần phải tự viết 1 class riêng.
    Để sử dụng Priority Queue trong C++ chỉ cần include queue là xong
    Demo:

    #include <iostream>
    #include <queue>

    using namespace std;

    int main(){
    priority_queue<int> q;

    q.push(5);
    q.push(4);
    q.push(2);

    while(!q.empty()){
    cout << q.top() << endl;
    q.pop();
    }

    puts("Ket thuc!");
    return 0;
    }


    Tham khảo thêm: http://www.java2s.com/Code/Cpp/Data-...rity-Queue.htm

  4. #4
    Ngày gia nhập
    12 2009
    Bài viết
    74

    uh chỉ khi học thuật toán mình mới xài C++. Mình chỉ dùng mỗi stdlib.h thôi, để print() và getch() buộc phải dùng thêm stdio.h và conio.h

    không thì mình vẫn code dot net, tha hồ thư viện mà chọn ^^

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

    hay lắm bạn. sao không viết một bài giải thích rõ thuật toán A* đi. mọi người cùng học hỏi.

  6. #6
    Ngày gia nhập
    10 2010
    Nơi ở
    tp hồ chí minh
    Bài viết
    1

    Smile C++ :: SourceCode thuật toán A* (A sao) tìm đường đi ngắn nhất.

    Bạn có thể trình bày kỹ hơn một chút cho mọi người học hỏi không.
    chạy tay thì mình làm rất tốt nhưng khi viết code thì nó mắc rất nhiều lỗi.Bạn giúp mình khắc phục với
    "Đừng bao giờ nói không thể khi mình không thử "

  7. #7
    Ngày gia nhập
    05 2012
    Bài viết
    3

    Mặc định các anh giúp em bài này cái

    em đọc mãi mà chẳng hiểu mong anh chị giúp em đk không ạ
    Công thức toán học Latex
    Attached Files Attached Files

  8. #8
    Ngày gia nhập
    02 2012
    Bài viết
    8

    Mình thì không rành lập trình cho mình hỏi là code này bạn viết trên Dev C++ hay Visual C++ hay C# sao.

  9. #9
    Ngày gia nhập
    11 2010
    Bài viết
    574

    Trích dẫn Nguyên bản được gửi bởi chipchipknight Xem bài viết
    Trong C++ có hỗ trợ PriorityQueue rồi bạn, đâu cần phải tự viết 1 class riêng.
    Để sử dụng Priority Queue trong C++ chỉ cần include queue là xong

    Tham khảo thêm: http://www.java2s.com/Code/Cpp/Data-...rity-Queue.htm
    Priority Queue trong STL không hỗ trợ Decrease Key => Không dùng được trong cài đặt A*.

  10. #10
    Ngày gia nhập
    02 2012
    Bài viết
    8

    Có anh chị nào giải thích về code giải thuật này không. Đang cần cho học tập.

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

  1. Làm sao để thực thi sourcecode sinh bằng codedom cùng với các sourcecode khác?
    Gửi bởi blumbebe trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 0
    Bài viết cuối: 20-01-2012, 09:33 PM
  2. Bài toán tìm đường đi ngắn nhất với thuật toán Dijsktra
    Gửi bởi biencuongtq1 trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 0
    Bài viết cuối: 17-03-2011, 02:51 AM
  3. thuật toán tìm đường đi ngắn nhất(dijkstra)
    Gửi bởi shogun_vn trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 6
    Bài viết cuối: 22-11-2010, 12:45 AM
  4. 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
    Gửi bởi hunterphu trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 10
    Bài viết cuối: 10-08-2010, 12:05 AM
  5. [c++]Thuật giải tìm đường ngắn nhất
    Gửi bởi hoanglinh9466 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 9
    Bài viết cuối: 01-08-2008, 04:44 PM

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