關(guān)于圖論的知識很早就想給自己做一個整理咐柜，關(guān)于圖的知識，應該是算法與數(shù)據(jù)結(jié)構(gòu)里面最有意思的一部分了攘残，也是我個人很喜歡的一塊拙友。之前一直覺得自己水平不夠，寫得不好肯腕。前幾天參加數(shù)學建模的競賽献宫，拿到的題目的本質(zhì)就是一道圖搜索的題目。于是实撒，比賽的時候惡補了一波姊途，賽后又總結(jié)了一下。于是知态，把自己總結(jié)的貼在這里捷兰，做一個記錄。
圖的本質(zhì)负敏，描述的是一堆點與點的關(guān)系贡茅，這個點可以是道路結(jié)點，也可以是人，也可以是其他實體顶考。
下面是我想寫的：
- 遞歸
- 深度遍歷和廣度遍歷
- 全排列和組合問題
- 八皇后問題
- A-star 算法
1. 遞歸和回溯
對于遞歸赁还，如果這個問題，可以被調(diào)用自身并且在每一次調(diào)用的過程里面問題的規(guī)模還在不斷的減少驹沿，那么這個遞歸的方法可以來解決這個問題艘策。
舉個典型的例子，二分查找渊季，代碼如下：
int binarySearch(int * arr ,int begin ,int end,int key){
//遞歸的減枝條件
//pass
//遞歸結(jié)束條件
if (begin >end ){
return -1
}
//找到解的情況
if(key==arr[(end-begin)/2+begin]){
return (end-begin)/2+begin;
}
//進入下一波遞歸
if(key <arr[(end-begin)/2+begin] ){
binarySearch(arr,begin,mid-1,key);
}
else{
binarySearch(arr,mid+1,end,key);
}
}
寫一個遞歸的代碼朋蔫，我的理解是從四點入手，
- 遞歸結(jié)束的條件是什么
- 進入下一層遞歸的條件是什么
- 找到解的情況
- 為了減少搜索的規(guī)模却汉，可以考慮減枝驯妄。減枝有兩種，一種是合法性的減枝合砂，一種是能夠減少搜索規(guī)模的減枝
下面寫一個其他的青扔，組合問題。
LeetCode78:Subsets
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
思路：
對于一個元素既穆，有兩種選擇赎懦，一種是把這個元素加入到當前的集合然后處理后面的元素，另一個是不把這個元素加入到當前結(jié)合然后處理后面的元素幻工。
完全滿足遞歸的思想：
- 可以調(diào)用自身
- 問題的規(guī)模在變小
so励两，代碼如下：
#include <iostream>
#include <vector>
using namespace std;
void print_res(vector<vector<char>> &ans, vector<int> &path,vector<char> vc){
//以print的方式輸出
for (int i=0;i<path.size();i++){
if(path[i]==1){
cout<<vc[i]<<" ";
}
}
cout<<endl;
//將結(jié)果pushbach到ans里面
vector<char> row;
for (int i=0;i<path.size();i++){
if(path[i]==1){
row.push_back(vc[i]);
}
}
ans.push_back(row);
}
void dfs(vector<vector<char>> &ans ,vector<int> path,int index ,vector<char> &vc ){
//減枝
if (index >vc.size()){
return ; //剪枝 表示結(jié)束，需要return
}
//找到結(jié)果
if(index==vc.size()){
print_res(ans,path,vc);
return; //找到結(jié)果囊颅，也意味著這一層的搜索結(jié)束当悔，然后return
}
//進入下一層的遞歸，進入遞歸之后踢代，創(chuàng)建兩個機器人干活盲憎，一個機器人取當前元素加入集合干活，另外一個機器人不取當前元素加入集合胳挎，然后干活
//取 創(chuàng)建一個機器人饼疙，進入遞歸干活
path[index]=1;
dfs(ans,path,index+1,vc);
// 對于進入遞歸之后，從遞歸出來慕爬，一定要記的清楚上一次遞歸的狀態(tài)窑眯，這個非常非常的重要!!!!
path[index]=0;
//不取
dfs(ans,path,index+1,vc);
}
vector<vector<char>> subset(vector<char> & vc){
vector<vector <char>> ans;
vector<int> path(vc.size(),-1);
int index=0;
//進入遞歸
//取當前元素，進入遞歸
path[index]=1;
dfs(ans,path,index+1,vc);
//對于進入遞歸之后医窿，從遞歸出來磅甩，一定要記的清楚上一次遞歸的狀態(tài)，這個非常非常的重要!!!!
path[index]=0;
//不取當前元素姥卢，進入遞歸
dfs(ans,path,index+1,vc);
return ans;
}
int main(){
vector<char> vc;
vc.push_back('a');
vc.push_back('b');
vc.push_back('c');
vc.push_back('d');
vector<vector <char>> ans=subset(vc);
return 0;
}
深度優(yōu)先遍歷和廣度優(yōu)先遍歷
深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法本身并不是很難卷要，很多書已經(jīng)寫的很好了渣聚。但是，深度優(yōu)先的實現(xiàn)可以解決很多除了圖遍歷之外僧叉，還很適合解決很多搜索類的問題奕枝。而dfs的本質(zhì)，也是一種遞歸瓶堕。
看看八皇后問題
在8×8格的國際象棋上擺放八個皇后倍权，使其不能互相攻擊，即任意兩個皇后都不能處于同一行捞烟、同一列或同一斜線上，問有多少種擺法当船。
這個問題题画，在搜索所有的狀態(tài)空間，時間復雜度是O(N^N)德频。搜索過程苍息，如下：
#include <iostream>
#include <vector>
#include <set>
#include <stdlib.h>
using namespace std;
//記錄一下結(jié)果的個數(shù)
int times=0;
void print_res(vector<int> path ){
times++;
for (auto it =path.begin();it!=path.end();it++){
cout<<*it<<" ";
}
cout<<endl;
}
bool isHang(vector<int> path){
set<int> path_set;
for (auto it =path.begin();it!=path.end();it++){
path_set.insert(*it);
}
if(path_set.size()==path.size()){
return true;
}
else{
return false;
}
}
bool isXiexian(vector<int> path){
for(int i=0;i<path.size()-1;i++){
for(int j=i+1;j<path.size();j++){
if(abs(path[i]-path[j])==abs(i-j) ){
return false;
}
}
}
return true;
}
void dfs(int index,int n,vector<int> path){
//找到結(jié)果
if(index==n){
//判斷結(jié)果的合法性
if(isHang(path) && isXiexian(path)){
print_res(path);
}
return ;
}
//進入下一層遞歸
for(int i=0;i<n;i++){
path[index]=i;
dfs(index+1,n,path);
path[index]=-1;
}
}
void n_queen(int n){
vector<int> path(n,-1);
int index=0;
for(int i=0;i<n;i++){
path[index]=i;
dfs(index+1,n,path);
//清除上一次進入遞歸的狀態(tài)
path[index]=-1;
}
}
int main(){
const int n=8;
n_queen(n);
cout<<endl;
cout<<"times : "<<times<<endl;
return 0;
}
A-star 算法
to-do
