Á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);

            }
        }
    }