小菜鸟

动态规划

发表于 2023-07-21 更新于 2024-09-03 分类于数据结构与算法阅读次数： Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

动态规划

还是回到贪心算法中的背包问题，使用贪心算法解决背包问题，得到的并不是最优解，而是一个近似算法。那么如何得到最优解呢，那就是动态规划。

动态规划是先解决子问题，在逐步解决大问题

动态规划可在给定约束条件下找到最优解
在问题可分解为彼此独立且离散的子问题时，可使用动态规划来解决

在动态规划中，每种动态规划解决方案都涉及到网格，每个单元格的值就是要优化的值，每个单元格都是一个子问题

阅读全文 »

贪心算法

发表于 2023-07-20 更新于 2023-07-21 分类于数据结构与算法阅读次数： Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

贪心算法

每一步都采取最优的做法，每步都是局部最优解，最终得到的就是全局最优解。贪心算法是一个近似算法，而不是最优解算法

以背包算法为例，有一个小偷，背包可装35磅重的东西，在商场准备偷取商品放入背包。力图往背包中装入价值最高的商品。使用贪心算法，分为两步

盗窃可装入背包的最贵的商品
再盗窃还可装入背包的最贵商品，以此类推

是不是很简单，但是使用该算法得到的不是最优解。有如下商品：

音响 3000元 30磅
笔记本电脑 2000元 20磅
吉他 1500元 15磅

使用贪心算法的话得到的是音响，价格为3000元。而实际偷取笔记本电脑和吉他价格为3500元

阅读全文 »

迪杰斯特拉算法

发表于 2023-07-19 更新于 2024-11-09 分类于数据结构与算法阅读次数： Valine：
本文字数： 4.5k 阅读时长 ≈ 4 分钟

迪杰斯特拉算法

之前在进行最短路径计算时使用了广度优先算法，但是找出的只是换乘最少的路径，每次所用的时间其实是不一样的，如果要找出用时最短的路径，可以使用迪杰斯特拉算法(Dijkstra)

如上述路线，从A到D，如果使用广度优先算法的话会得到A->B->D，花费7分钟。而其实最短时间是A->C->B->D，花费6分钟。

迪杰斯特拉算法包含四个步骤

找出可在最短时间内到达的节点，站在A点，不知道该前往B点还是C点时，此时由于还不知道前往终点需要多长时间，假设是无穷大。此时C点是最近的
第一步算出来C点是距离起点最近的，这一步需要计算出经过C点到其他各邻居节点所需的时间

A->C->B 需要5分钟

A->C->D需要8分钟

OK。此时找到了一条前往B的更短路径。直接前往B需要6分钟，经C之后前往B只需要5分钟。

所以更新一下到各节点的时间开销
- 前往B点的路径时间从6分钟缩短到了5分钟
- 前往终点的时间从无穷大缩短到了8分钟
重复前两步操作。重复第一步时排除掉第一次选出的C点，所以选出的点是B点。重复第二步更新B点所有邻居节点的开销。

此时发现达到终点的时间变为了6分钟。
最终算出到达终点的最短时间

使用的是贪心算法

阅读全文 »

拓扑排序

发表于 2023-07-18 更新于 2024-11-06 分类于数据结构与算法阅读次数： Valine：
本文字数： 1k 阅读时长 ≈ 1 分钟

拓扑排序

之前说过广度优先搜索，是按照度来进行排序的。这里来说一下另外一种图的算法。其中的节点有依赖关系，如果节点A依赖于节点B，则列表中的节点A就必须在节点B后，这就是拓扑排序。

使用拓扑排序来创建一个有序的任务列表

public class TuoPuSort {

    public static void main(String[] args) {
        // 先分出三组依赖的任务队列来
        Queue<String> q1 = new ArrayDeque<>();
        q1.add("锻炼");
        q1.add("洗澡");
        q1.add("穿衣服");

        Queue<String> q2 = new ArrayDeque<>();
        q2.add("刷牙");
        q2.add("吃早餐");

        Queue<String> q3 = new ArrayDeque<>();
        q3.add("打包午餐");

        List<String> taskExeList = new ArrayList<>();
        // 初始任务是起床
        taskExeList.add("起床");

        List<Queue<String>> queueList = new ArrayList<>();
        queueList.add(q1);
        queueList.add(q2);
        queueList.add(q3);
        Random random = new Random();
        while (!queueList.isEmpty()){
            int i = random.nextInt(queueList.size());
            Queue<String> taskQueue = queueList.get(i);
            taskExeList.add(taskQueue.poll());
            if(taskQueue.isEmpty()){
                queueList.remove(i);
            }
        }

        taskExeList.forEach(
                System.out::println
        );

    }
}