当前位置：首页 > 娱乐资讯 > 正文内容

将待解决问题分解为若干规模较小的同类问题

admin2天前娱乐资讯8

[]

分治策略的核心在于将一个整体问题划分为若干个更小的、性质一致的子问题，这些子问题之间互不干扰。通过解决这些子问题分治算法在树的路径问题中的应用，我们能够找到原问题的解决方案。这实际上是一种通过分解目标来实现的程序算法将待解决问题分解为若干规模较小的同类问题，对于简单的问题将待解决问题分解为若干规模较小的同类问题，我们可以采用二分查找的方法来处理。

二、经典案例-汉诺塔

汉诺塔，亦称河内塔，源自印度一则古老的传说分治算法在树的路径问题中的应用，是一种经典的智力游戏。在创世之际，大梵天打造了三根金刚石柱，其中一根柱子上自下而上依次摆放着64片大小不一的黄金圆盘。按照大梵天的旨意，婆罗门需将这些圆盘从底部起，依照大小顺序移至另一根柱子上。同时明确，不得在小圆盘上对大圆盘进行扩展，且在三根柱子构成的框架内分治算法在树的路径问题中的应用，每次仅允许一个圆盘进行单次移动。

2.1 算法思路

2.2 代码示例

需求：递归实现3阶汉诺塔的移动。

public class HanoiTower {
    public static void main(String[] args) {
        HanoiTower hanoi = new HanoiTower();
        // 3阶汉诺塔。
        hanoi.hanoi(3, 'A', 'B', 'C');
        // Direction:A--->C
        // Direction:A--->B
        // Direction:C--->B
        // Direction:A--->C
        // Direction:B--->A

        // Direction:B--->C
        // Direction:A--->C
    }
    /**
     * 使用分治算法，解决汉诺塔问题。
     *
     * @param n           盘子的数目
     * @param origin      源座
     * @param assist      辅助座
     * @param destination 目的座
     */
    public void hanoi(int n, char origin, char assist, char destination) {
        // 只有一个盘的时候，直接从 A->C 。
        if (1 == n) {
            move(origin, destination);
        } else {
            在存在n个及以上的情形下，我们可以将其视为由两部分组成：一是最底层的单个盘子；二是位于其上的所有盘子。
            首先，需将位于顶部的所有盘子从源座A移至目的座B，此过程中将借助辅助座C进行移动。
            hanoi((n - 1对起始点、目的地以及协助事项实施限制。
            // 2. 把最下边的盘 A->C 。
            move(origin, destination);
            将柱B上的所有盘子从B点（即当前源点）转移到C点（即当前目标点），在移动过程中需借助柱A（即当前辅助点）。
            hanoi(n - 1协助确定起点与终点。
        }
    }
    /**
     * 展示移动过程。
     *
     * @param origin      源座
     * @param destination 目的座
     */
    private void move(char origin, char destination) {
        System.out.println("Direction:" + origin + "--->" + destination);
    }
}