回溯算法

回溯算法介绍

  回溯算法并不是非常复杂的算法, 很多人接触过但是未必知道这是回溯算法; 典型的回溯算法就是深度优先算法。 树我们是怎么进行深度优先的? 从根节点往左(或右)一直走下去并且放入堆栈中, 当无路可走的时候, 弹出一个节点回到上一级选择另外的子节点. 就像人生不断的做选择, 如果能够回溯, 当我们走错的时候我们就会回到上一次的岔路口选择另外的一条路.

八皇后算法

介绍

  八皇后算法就是再一个8×8的方阵中放入8个棋子, 要求横竖对角线上不能有两个棋子; 典型的回溯解法就是把8个棋子逐次放入第一行、第二行..., 如果满足继续下一行如果不满足换一个位置重试. 找出所有符合规则的摆放方式.

C++实现

#include <stdio.h>
#include <stdlib.h>

int result[8] = { 0 };
bool queen_ok(int row, int col);
void print_queens();

bool cal8queens(int row)
{
    if(row == 8)
    {
        print_queens();
        return true;
    }

    for(int col = 0; col < 8; col++)            //8列
    {
        if(queen_ok(row, col))
        {
            result[row] = col;
            if(cal8queens(row + 1))
            {
                return true;
            }
        }
    }
    return false;
}

bool queen_ok(int row, int col)                     //判断某一个新的皇后的坐标是否符合
{
    if(row > 0)
    {
        for(int i = 1; i <= row; i++)
        {
            int row_v = result[row - i];
            if(row_v == col || row_v == col - i || row_v == col + i)
            //不必考虑负数和达到8, 因为row_v必然是再[0,7]
            {
                return false;
            }
        }
    }

    return true;
}

void print_queens()
{
    for(int i = 0; i < 8; i++)
    {
        for(int j = 0; j < result[i]; j++)
        {
            printf("%s", "*");
        }
        printf("%s", "Q");
        for(int j = result[i] + 1; j < 8; j++)
        {
            printf("%s", "*");
        }
        printf("\n");
    }
}

int main()
{
    cal8queens(0);
    return 0;
}

注意: 这里只是打印出其中一种, 打印全部也很简单.

0-1背包问题

0-1背包问题介绍

  0-1背包问题与贪心算法中在限定重量下获取最高的价值的问题是类似的, 但是与贪心算法不同的是物品不可以分割, 一种物品有多少就需要全部放入背包.

思路

  每种物品只有两种选择, 放入和不放入; 对于每种物品的两种选择都进行遍历, 当然如果放入后重量超出的情况就不必继续下去. 同八皇后的问题一样是遍历获取所有情况, 所以也不需要考虑返回值.

C++实现

/*1, 回溯算法解法 */

/*
* items: 物品的重量及价值
* i: 当前遍历到哪一个
* cv: 当前价值
* cw: 当前重量
* w: 允许重量
*/
#include <limits.h>

#include <iostream>
#include <vector>

using namespace std;

int maxV = INT_MIN;

void func1(vector<pair<int, int>> &items, int i, int cv, int cw, int w)
{
    if(i == items.size() || w == cw)
    {
        if(cv > maxV) maxV = cv;
        return;
    }

    if(cw + items[i].first <= w)
        func1(items, i + 1, cv + items[i].second, cw + items[i].first, w);      
    func1(items, i + 1, cv, cw, w);
}


int main()
{
    int total = 40;
    vector<pair<int, int>> items;
    srand(time(NULL));
    for(int i = 10; i <= 30; i+=2)
    {
        int value = rand() % 30;
        items.push_back(make_pair(i, value));
        printf("key-value: %d-%d\n", i, value);
    }

    func1(items, 0, 0, 0, total);
    cout<<"total: "<<total<<", max Weight: "<<maxV<<endl;

    return 0;
}

ps: 这里没有进行详细的测试, 凭肉眼也很难看出结果对错来; 如果有问题欢迎指正.

正则表达式问题

  这里的正则表达式当然不会是一个功能非常强大的正则表达式, 假设正则表达式中只包含*和?这两种通配符，*大于或等于零个个任意字符, ?匹配零个或者一个任意字符。

  回溯问题, 很简单的就是需要对所有情况处理遍历; 不过与上面有所不同的是, 我们需要判断返回结果, 再匹配成功后就退出.

算法实现

/*正则表达式*/


#include <iostream>
#include <string>
#include <cstring>
using namespace std;

//一, 使用回溯算法实现的`*?`正则匹配
/* 说明:
* 1, ? 匹配0个或1个任意字符
* 2, * 匹配0个或多个任意字符
* 3, 所有字符均以`\0`结尾
*/
class Pattern
{
public:
    bool match(const char *main, const char *regex)
    {
        return rmatch(main, regex);
    }
private:
    bool rmatch(const char *main, const char *regex)
    {
        if(*regex == '\0' && *main == '\0')
        {
            return true;
        }

        if(*main == '\0')
        {
            return false;
        }

        if(*regex == '?')
        {
            if(rmatch(main, regex + 1))
            {
                return true;
            }
            if(rmatch(main + 1, regex + 1))
            {
                return true;
            }

        }
        else if(*regex == '*')
        {
            for(int i = 0; i <= strlen(main); i++)
            {
                if(rmatch(main + i, regex + 1))
                    return true;
            }
        }
        else
        {
            if(*main != *regex)
            {
                return false;
            }
            else
            {
                return rmatch(main + 1, regex + 1);
            }
        }

        return false;
    }   
};

int main()
{
    string main;
    string regex;

    cout<<"请输入主串: ";
    cin>>main;
    cout<<"请输入模式串: ";
    cin>>regex;

    Pattern pat;
    cout<<"match: "<<pat.match(main.c_str(), regex.c_str())<<endl;


    return 0;
}