启发式算法中哪个最简单,启发式算法是不是每次结果不同

首页 > 教育 > 作者:YD1662024-05-15 11:44:13

启发式算法中哪个最简单,启发式算法是不是每次结果不同(1)

一、什么是“搜索”算法?

public class Graph { // 顶点的个数 private int v; // 每个顶点后面有个链表 private LinkedList<Integer>[] adj; public Graph(int v) { this.v = v; adj = new LinkedList[v]; for (int i = 0; i < v; i ) { adj[i] = new LinkedList<>(); } } /** * 添加边 * @param s 顶点 * @param t 顶点 */ public void addEdge(int s,int t){ // 无向图一条边存两次(联想微信好友) adj[s].add(t); adj[t].add(s); } }

二、广度优先搜索(BFS)

2.1、实现过程

/** * 图的广度优先搜索,搜索一条从 s 到 t 的路径。 * 这样求得的路径就是从 s 到 t 的最短路径。 * * @param s 起始顶点 * @param t 终止顶点 */ public void bfs(int s, int t) { if (s == t) { return; } // visited 记录已经被访问的顶点,避免顶点被重复访问。如果顶点 q 被访问,那相应的visited[q]会被设置为true。 boolean[] visited = new boolean[v]; visited[s] = true; // queue 是一个队列,用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的,只有把第k层的顶点都访问完成之后,才能访问第k 1层的顶点。 // 当访问到第k层的顶点的时候,需要把第k层的顶点记录下来,稍后才能通过第k层的顶点来找第k 1层的顶点。 // 所以,用这个队列来实现记录的功能。 Queue<Integer> queue = new LinkedList<>(); queue.add(s); // prev 用来记录搜索路径。当从顶点s开始,广度优先搜索到顶点t后,prev数组中存储的就是搜索的路径。 // 不过,这个路径是反向存储的。prev[w]存储的是,顶点w是从哪个前驱顶点遍历过来的。 // 比如,通过顶点2的邻接表访问到顶点3,那prev[3]就等于2。为了正向打印出路径,需要递归地来打印,就是print()函数的实现方式。 int[] prev = Arrays.stream(new int[v]).map(f -> -1).toArray(); while (queue.size() != 0) { int w = queue.poll(); LinkedList<Integer> wLinked = adj[w]; // 表示:邻接表存储时顶点为w,所对应的链表 for (int i = 0; i < wLinked.size(); i) { int q = wLinked.get(i); // 判断顶点 q 是否被访问 if (!visited[q]) { // 未被访问 prev[q] = w; if (q == t) { print(prev, s, t); return; } visited[q] = true; queue.add(q); } } } } // 递归打印s->t的路径 private void print(int[] prev, int s, int t) { if (prev[t] != -1 && t != s) { print(prev, s, prev[t]); } System.out.print(t " "); }

原理如下:

2.2、复杂度分析

三、深度优先搜索(DFS)

3.1、实现过程

// 全局变量或者类成员变量,标记是否找到终点 t boolean found = false; /** * 深度优先搜索 * * @param s 起始顶点 * @param t 终止顶点 */ public void dfs(int s, int t) { found = false; // 标记顶点是否被访问 boolean[] visited = new boolean[v]; // prev 用来记录搜索路径,prev[w] = a 表示 w 顶点的上一级节点为 a int[] prev = Arrays.stream(new int[v]) .map(f -> -1).toArray(); recurDfs(s, t, visited, prev); print(prev, s, t); } private void recurDfs(int w, int t, boolean[] visited, int[] prev) { if (found == true) { return; } visited[w] = true; if (w == t) { found = true; return; } LinkedList<Integer> wLinked = adj[w]; for (int i = 0; i < wLinked.size(); i) { int q = wLinked.get(i); if (!visited[q]) { prev[q] = w; recurDfs(q, t, visited, prev); } } }

3.2、复杂度分析

四,两者对比

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.