.:: CODE SNIPPET ::.

"Your time is limited, so don't waste it living someone else's life"

Áp dụng giải thuật AKT vào bài toán tháp Hà Nội


Chương trình áp dụng giải thuật AKT, mội trạng thái được mô tả bằng mảng hai chiều. Để ước lượng đối với trạng thái của trò chơi, ta sẽ tính trạng thái của cột thứ ba. Tại một trạng thái, thì số bước để đưa cột thứ ba về đúng như trạng thái đích là bao nhiêu? Ta thấy tại một trạng thái của cột thứ ba thì có một số đĩa nằm đúng vị trí của nó, và cũng có một số đĩa không nằm đúng vị trí của nó. Số lượt để ta có thể đưa cột thứ ba về đúng trạng thái đích bằng tổng số lượt mang những đĩa không đúng vị trí ra khỏi cột thứ ba cộng với số lượt mang những đĩa còn lại vào cho đúng vị trí của nó trong cột thứ ba.
Một số hàm chính trong chương trình:

 int GetNumberOfDiskOfPillar(Integer[] pPillar) Tính tổng số đĩa hiện có trong một cột nào đó.
 int GetRightPositions(Integer[] pPillar) Tính số đĩa nằm đúng vị trí trong một cột nào đó
 void H() // Là hàm tri thức bổ sung có giá trị bằng số vị trí sai trên cột thứ 3.
 Void Generate() Tính toán các bước đi cho bài toán Áp dụng giải thuật AKT

Mặc dù thuật giải tương đối đơn giản, bài toán với n đĩa sẽ cần ít nhất 2n-1 lần di chuyển. Tuy nhiên với số lượng Cọc nhiều hơn 3 thì vẫn chưa biết được sẽ cần ít nhất bao nhiêu lần di chuyển để giải bài toán. Do vậy việc áp dụng bước tiến dãy (tiếng Anh sequential advancement) để xác định vị trí của một số lượng lớn các đĩa trên ba cọc sau một số lớn tuỳ ý các bước tiến là không thực tế. Lời giải tối ưu cho bài toán Tháp Hà Nội với bốn cọc hay nhiều hơn vẫn còn là một bài toán mở. Đây là một ví dụ tiêu biểu cho thấy một bài toán đơn giản, có thể giải được vẫn có thể trở thành khó hơn rất nhiều bằng cách hơi nới lỏng một số ràng buộc của nó.
Mặc dù không biết được chính xác cần bao nhiêu lần di chuyển, có thể có một vài kết quả tiệm cận. Có một “lời giải được coi như tối ưu” có thể áp dụng một cách đệ quy để tìm một lời giải–xem giải thích cũng như một vài biến thể của bài toán bốn cọc trong bài khảo sát của Paul Stockmeyer.
3.5. Cấu trúc dữ liệu
Xem một tháp Hà Nội được kết cấu từ một mảng hai chiều có 3 dòng và số cột là số đĩa mà chương trình cho phép mô phỏng. Mảng hai chiều này chỉ chứa những số tự nhiên. Những vị trí có đĩa thì các số tự nhiên sẽ xếp theo chiều giảm dần của các số tự nhiên lớn hơn 0 như:
– 3 đĩa sẽ là: 2,1,0
– 4 đĩa sẽ là: 3,2,1,0

Còn những vị trí không có đĩa sẽ chứa lưu số -1.
Như vậy, ban đầu khi khởi tạo chương trình thì mảng hai chiều sẽ là:
S0={{2,1,0},{-1,-1,-1},{-1,-1,-1}}
Ứng với một trạng thái của chương trình thì còn có những thuộc tính tương ứng như:
• Chi phí đi từ trạng thái khởi đầu đến trạng thái hiện tại.
• Chỉ số ước lượng Heuristic, là chi phí để đi đến đích từ trạng thái đó.
• Chỉ số f là tổng hai chi phí bên trên.
• Và trạng thái cha của trạng thái hiện tại.

Trong đó hàm ước lượng sẽ như sau:

public void heuristic()
    {
        this.valueH = this.disks[2].length;
        for (int i = 0; i < this.disks[2].length; i++)
        {
            if (this.disks[2][i].getDiskId() == i + 1)
            {
                this.valueH--;
            }
        }
    }

Hàm tính toán khá đơn giản, chi phí để đưa trạng thái về trạng thái đích là chi phí bỏ các đĩa nằm không đúng vị trí trong cột thứ ba ra, cộng với chi phí đưa những đĩa còn lại vào cột thứ ba cho đúng vị trí của nó.
Hàm quan trọng trong chương trình là hàm tính giải thuật AKT:

public void resolve()
    {
        Snapshot originalSnapshot = new Snapshot(this.diskCount);
        this.lstOpenedSnapshots.add(originalSnapshot);

        while (this.lstOpenedSnapshots.size() > 0)
        {
            Snapshot processingSnapshot = this.lstOpenedSnapshots.get(0);
            this.lstSteps.add(processingSnapshot);
            this.lstOpenedSnapshots.remove(0);
            if (processingSnapshot.getValueH() == 0)
            {
                break;
            }
            List<Snapshot> lstGeneratedSnapshots = new ArrayList<Snapshot>();
            processingSnapshot.getAllGeneratedSnapshot(lstGeneratedSnapshots);

            for (Snapshot snap : lstGeneratedSnapshots)
            {
                if (!this.isValidSnapshot(snap))
                {
                    continue;
                }
                int i = 0;
                while (i < this.lstOpenedSnapshots.size()
                        && snap.getvalueF() > this.lstOpenedSnapshots.get(i).getvalueF())
                {
                    i++;
                }
                this.lstOpenedSnapshots.add(i, snap);

            }
        }
    }
Advertisements

10 responses to “Áp dụng giải thuật AKT vào bài toán tháp Hà Nội

  1. Invisible June 15, 2013 at 10:57 PM

    Cái này là anh minh họa bằng ngôn ngữ Kava hả anh?

  2. Invisible June 15, 2013 at 10:58 PM

    Cái này là anh minh họa bằng ngôn ngữ Java hả anh

  3. Hoàng Minh June 18, 2013 at 9:09 AM

    uhm, Java do ban

  4. Anonymous March 15, 2014 at 9:37 AM

    Sao khong post day du di ban. Post vay sao chay dc

  5. Minh Trần March 15, 2014 at 9:44 AM

    Mình chỉ implement phần giải thuật thôi, còn những cái khác, bạn dễ dàng làm thành 1 demo hoàn chỉnh mà. Chứ mình post hoàn chỉnh thì lỡ bạn chạy được, nhưng người khác lại không.

  6. Anonymous March 15, 2014 at 11:03 AM

    MoveTopDisk(), traceBack(): khong biet no xu ly gi ben trong, nhờ chỉ dùm.

  7. saobanghp310gmail.com Nguyen March 16, 2014 at 10:18 PM

    bạn chỉ dùm cách tính di chuyển đĩa đi pạn

  8. Minh Trần March 16, 2014 at 11:48 PM

    Bạn muốn hỏi về giải thuật hay là về cài đặt?

  9. văn đương October 22, 2015 at 1:20 AM

    gửi cho mình bản demo đầy đủ được không?

  10. Cường Thế April 8, 2017 at 3:11 PM

    có bạn nào đã giải thành 1 bài hoàn thiện không vậy? cho mình tham khảo với

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

%d bloggers like this: