文档章节

DFS算法

jit-hakase
 jit-hakase
发布于 2017/08/29 22:42
字数 1029
阅读 36
收藏 1

#DFS算法 ##DFS ###排列数 问题: 生成1~n的排列 思路: 穷举所有可能 在生成结果数组前把重复的去掉 python code

A = [None for i in range(10)]
N = 3

def dfs(cur):
    if cur == N:
        print(A[:N])
    else:
        for i in range(1, N+1):
            if i not in A[:cur]:
                A[cur] = i
                dfs(cur+1)

dfs(0)

使用algorithm头文件的C++ C++ code

#include <iostream>
#include <algorithm>
using namespace std;

int A[10];
int N = 3;

int main()
{
	for (int i = 0; i < N; i++)
        A[i] = i+1;

	do {
        for (int i = 0; i < n; i++)
            cout << A[i];
        cout << endl;
	} while(next_permutation(A, A+N));
	return 0;
}

###素数环 问题: 数字1~n围成一个n个节点的环, 不允许数字重复, 任意2个相邻数字相加, 结果均为素数, 打印所有素数环的组合. 思路: 同排列数, 多了素数判断. python code

A = [None for i in range(0, 10)]
N = 6

def is_prime(n):
    for i in range(2, n//2+1):
        if n%i == 0:
            return False
    return True

def dfs(cur):
    if cur == N:
        if is_prime(A[0]+A[N-1]):
            print(A[:N])
    else:
        for i in range(1, N+1):
            if i not in A[:cur]:
                if cur == 0 or is_prime(i+A[cur-1]):
                    A[cur] = i
                    dfs(cur+1)

dfs(0)

###八皇后 问题: 8×8的国际象棋棋盘上摆放八个皇后,使其不能互相攻击到,有多少种解. 思路: 结果数组存放每个棋子的x坐标, 直到没有冲突放完八个棋子. 解决冲突: 1. 不可能行冲突 2. 列冲突解决同排列数 解决斜线冲突, 利用y-x的特性找出关系. 3. cur-Q[cur] == j-Q[j]

4. cur+Q[cur] == j+Q[j] python code

Q = [None for i in range(0, 8)]
CNT = 0
N = 8

def dfs(cur):
    if cur == N:
        global CNT
        CNT += 1
    else:
        for i in range(0, N):
            Q[cur] = i
            ok = True
            for j in range(0, cur):
                if Q[cur]==Q[j] or cur-Q[cur]==j-Q[j] or cur+Q[cur]==j+Q[j]:
                    ok = False
            if ok:
                dfs(cur+1)
                

dfs(0)
print('ans = ' + str(CNT))

##回溯法 探索到某一步发现原先选择达不到目标, 就退回一步重新选择. 效率比普通DFS高. 可以优化排列数和素数环的程序

访问过某个数后标记这个数已经访问再进行下一步的搜索 搜索完毕之后退回前一个搜索点, 再清除标记, 继续搜索.

排列数和素数环使用回溯法 python code

A = [None for i in range(0, 10)]
V = [False for i in range(0, 10)]
N = 4

def dfs(cur):
    if cur == N:
        print(A[:N])
    else:
        for i in range(1, N+1):
            if not V[i]:
                V[i] = True
                A[cur] = i
                dfs(cur+1)
                V[i] = False

dfs(0)

python code

A = [None for i in range(0, 10)]
V = [False for i in range(0, 10)]
N = 6
def is_prime(n):
    for i in range(2, n//2+1):
        if n%i == 0:
            return False
    return True

def dfs(cur):
    if cur == N:
        if is_prime(A[0]+A[N-1]):
            print(A[:N])
    else:
        for i in range(1, N+1):
            if not V[i]:
                if cur == 0 or is_prime(i+A[cur-1]):
                    V[i] = True
                    A[cur] = i
                    dfs(cur+1)
                    V[i] = False

dfs(0)

八皇后的回溯法 在棋子放下的时候直接判断列和斜线是否存在其他皇后,并标记那些坐标 python code

Q = [None for i in range(0, 8)]

VM = [False for i in range(0, 8)]
VL = [False for i in range(0, 16)]
VR = [False for i in range(0, 16)]

CNT = 0
N = 8

def dfs(cur):
    if cur == N:
        global CNT
        CNT += 1
    else:
        for i in range(0, N):
            if not VM[i] and not VL[cur+i] and not VR[cur-i+N]:
                VM[i] = VL[cur+i] = VR[cur-i+N] = True
                Q[cur] = i
                dfs(cur+1)
                VM[i] = VL[cur+i] = VR[cur-i+N] = False
                

dfs(0)
print('ans = ' + str(CNT))

##二维DFS搜索 二维搜索使用BFS的效率更高且附带最短路径, 用DFS编写扫雷核心算法. 核心算法: 点击到一个空白区域, 可以向四面八方展开空白块和数字. DFS算法的代码更容易编写(BFS当然也可以完成) python code

'''
dfs(x-1, y)
dfs(x+1, y)

dfs(x, y-1)
dfs(x, y+1)

dfs(x-1, y+1)
dfs(x+1, y-1)

dfs(x-1, y-1)
dfs(x+1, y+1)
'''
# serach 8 directions

dx = [-1,  1,  0,  0, -1,  1, -1,  1]
dy = [ 0,  0, -1,  1,  1, -1, -1,  1]

def pour(x, y):
    if M[x][y] == 0:
        show_empty(x, y)
        for i in range(0, 8):
            pour(x+dx[i], y+dy[i])
    elif M[x][y] > 0:
        show_num(x, y)

© 著作权归作者所有

上一篇: BFS
下一篇: 设计模式(4)
jit-hakase
粉丝 3
博文 26
码字总数 30408
作品 0
南京
程序员
私信 提问
算法基础:BFS和DFS的直观解释

算法基础:BFS和DFS的直观解释 https://cuijiahua.com/blog/2018/01/alogrithm_10.html 一、前言 我们首次接触 BFS 和 DFS 时,应该是在数据结构课上讲的 “图的遍历”。还有就是刷题的时候,...

功夫 熊猫
07/26
0
0
Kosaraju算法的分析和证明

Kosaraju算法是求解有向图强连通分量(strong connected component)的三个著名算法之一,能在线性时间求解出一个图的强分量。用Sedgewick爷爷的话说,就是“现代算法设计的胜利”。 什么是强...

liangtee
2013/03/30
362
0
数据结构与算法--图论之寻找连通分量、强连通分量

数据结构与算法--图论之寻找连通分量、强连通分量 寻找无向图的连通分量 使用深度优先搜索可以很简单地找出一幅图的所有连通分量,回忆连通图的概念:如果从任意顶点都存在一条路径达到任意一...

sunhaiyu
2017/11/11
0
0
对求有向图强连通分量的tarjan算法原理的一点理解

先简单叙述一下tarjan算法的执行过程(其他诸如伪代码之类的相关细节可以自己网上搜索,这里就不重复贴出了): 用到两类数组: dfs[]:DFS过程中给定节点的深度优先数,即该节点在DFS中被访问的...

Kukucao
2018/08/21
0
0
DFS算法

DFS算法 三个经典例子 1 排列数 问题: 生成1~n的排列 思路: 一颗N层的树 每层节点为n^n个 在生成结果数组前把重复的去掉 DFS出口: 遍历到排列结果数组长度 DFS实现: 尝试安排数字给结果数组 ...

hakase
2016/10/27
127
0

没有更多内容

加载失败,请刷新页面

加载更多

Flink Graph生成及Hash生成分析

222

MrPei
23分钟前
1
0
[译]Android Activity 和 Fragment 状态保存与恢复的最佳实践

https://blog.csdn.net/growing_tree/article/details/53759564 https://blog.csdn.net/u013588712/article/details/54691791...

shzwork
23分钟前
1
0
调用第三方快递鸟物流单号查询接口API代码示例

最近进行网站后台开发,需要实现物流的即时查询,发现之前集成的 快递100物流查询 API ——【PHP 快递查询源码资源】 已经不能正常使用了; 为了方便以后的业务需求,经过比较,最后选择使用...

程序的小猿
30分钟前
3
0
java Poi 操作执行excel 文件中函数问题

poi 读取excel 文件,当excel 有函数时,poi直接读取返回的是excel 函数,并不能返回函数计算结果: 解决步骤: sheet.setForceFormulaRecalculation(true); 判断该列格式是否为...

早a
38分钟前
4
0
js模拟实现输入框input事件

直接修改value值是无法触发对应元素的事件的。 通过发送输入框input事件了, 可以触发。 这里简单封装了一个方法. window.inputValue = function (dom, st) { var evt = new InputEvent('i...

開援带碼
39分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部