8数码问题——A*算法

这学期选修了人工智能课，实验写了个简单的A*算法来处理8数码的问题，在此做个记录。

声明的变量和函数

int Sg[9] = { 1,2,3,8,0,4,7,6,5 };//初始节点Sg
//int Sg[9] = { 8,6,0,3,2,5,4,7,1 };
int findedFlag = 0;//为1时，找到结果
int fn;//启发函数的选择
const int LENGTH = 200000;//结构体数组OP，CLD长度
int codeCount = 0;//总共生成结点数
struct Open //OPEN表
{
    int s[9];//节点
    int fatherId = -1;//默认没有父节点
    int evaluFunc;//评价函数
    int deep = 0;//当前节点深度
};
struct Closed //CLOSED表
{
    int id;//编号
    int s[9];//节点
    int fatherId = -1;//默认没有父节点
    int evaluFunc;//评价函数
    int deep = 0;//当前节点深度
};

//OPEN表结构体数组
struct Open OP[LENGTH];
//CLOSED表结构体数组
struct Closed CLD[LENGTH];
//OPEN表实际长度
int countOP = 0;
//CLOSED表实际长度
int countCLD = 0;

//查找子节点
void search(struct Open op);
//生成子节点,opw为父节点，codeId表示可移动数码的下标,zeroId表示空位下标
void creatNode(Open op, int codeId, int zeroId);
//对OPEN表进行排序
void bubbleSort(struct Open* op);
//OPEN表显示
void ViewOP(struct Open* op);
//CLOSED表显示
void ViewCLD(struct Closed* cld);
//启发函数hn
int hn(int fn);

由于声明的数组长度过长，VS可能会报错，需要在项目属性中设置一下。点击 项目—属性—链接器—系统 ，设置堆栈保留大小，如：16000000

主函数

int main()
{
    cout << "请选择启发函数： 1. h(n)=不在位的数码的总数" << endl;
    cout << "                 2. h(n)=所有数码到目标位置的距离和(曼哈顿距离)" << endl;
    
    cin >> fn;
    if (fn != 1 && fn != 2) {
        cout << "非法！" << endl;
        return 0;
    }
    cout << endl;
    //初始化open表
    OP[countOP] = { {2,8,3,1,6,4,7,0,5},-1,4,0 };//将s0放入open表中
    cout << "请选择8数码输入方式：1.默认    2.手动输入" << endl;
    int choice = 1;
    cin >> choice;
    if (choice == 2) {
        cout << "请依次输入8数码的值（0~8），0表示空位:\n";
        int code;
        for (int i = 0; i < 9; i++) {
            cin >> code;
            while (true) {
                if (code >= 0 && code < 9) {
                    OP[0].s[i] = code;
                    break;
                }
                else {
                    cout << code<<"不合法！请重新输入：" << endl;
                    cin >> code;
                }
            }
        }
        OP[0].deep = 0;
        OP[0].evaluFunc = hn(fn);//deep=0
        int repeat = 0;
        for (int i = 0; i < 9; i++) {//判断是否有重复
            for (int j = i + 1; j < 9; j++) {
                if (OP[0].s[i] == OP[0].s[j])repeat++;
            }
            if (repeat > 0) {
                cout << "8数码输入了重复的数值，启用默认8数码";
                OP[countOP] = { {2,8,3,1,6,4,7,0,5},-1,4,0 };
                break;
            }
        }
    }
    else if (choice != 1) {
        cout << "输入不合法，启用 1.默认方式" << endl;
        OP[countOP] = { {2,8,3,1,6,4,7,0,5},-1,4,0 };
    }
    //显示
    cout << "初始化" << endl;
    cout << "---------------OPEN表---------------" << endl;
    cout << 0 << " | {";
    for (int i = 0; i < 9; i++) {
        cout << OP[countOP].s[i] << ",";
    }
    cout << "} | " << OP[countOP].fatherId << " | " << OP[countOP].evaluFunc << " | " << endl;
    cout << "------------------------------------" << endl;
    //循环次数,用于显示
    int ccount = 0;
    //生成子结点
    
    while (true) {
        //下一层
        //OPEN表中的表首节点赋值到CLOSED表中
        for (int i = 0; i < 9; i++) {
            CLD[countCLD].s[i] = OP[0].s[i];
        }
        CLD[countCLD].evaluFunc = OP[0].evaluFunc;
        CLD[countCLD].fatherId = OP[0].fatherId;
        CLD[countCLD].deep = OP[0].deep;
        
        //CLOSE的表显示
        //ViewCLD(CLD);

        //判断是否为目标Sg，若是，跳出循环，查找结束
        for (int i = 0; i < 9; i++) {
            if (CLD[countCLD].s[i] == Sg[i])findedFlag++;
        }
        if (findedFlag == 9)break;
        else
        {
            findedFlag = 0;
        }

        //查找并生成子节点，并将其加入OPEN表中
        search(OP[0]);
        //对OPEN表进行排序，最小的放在表首,还要对countOP进行适当处理
        //OPEN表排序
        bubbleSort(OP);
        
        //对本次循环的OPEN表显示
        //cout << "第" << ccount + 1 << "次循环" << endl;
        //ViewOP(OP);
        
        //其余处理
        countCLD++;
        if (countCLD == LENGTH) {
            cout << "CLOSED表满未找到!" << endl;
            return -1;
        }
        else{
            CLD[countCLD].id = CLD[countCLD - 1].id + 1;//CLOSED表编号一次递增
        }
        ccount++;//循环次数+1
        
    }
    //CLOSE的表显示
    ViewCLD(CLD);
    cout << "循环结束，最终解答路径如下：" << endl;
    int ccCLD = countCLD;
    cout << ccCLD;
    while (true) {
        if (CLD[ccCLD].fatherId != -1) {
            cout << "->" << CLD[ccCLD].fatherId;
            ccCLD = CLD[ccCLD].fatherId;;
        }
        else {
            break;
        }
    }
    cout << "\n总共生成节点数：" << codeCount << endl;
    
    return 0;
}

查找子节点函数

void search(Open op)
{
    //将OPEN表首置0
    for (int i = 0; i < 9; i++) {
        OP[0].s[i] = 0;
    }
    OP[0].evaluFunc = 0;
    OP[0].deep = 0;
    //查找0的位置并记录
    int zeroId = 0;
    for (int i = 0; i < 9; i++) {
        if (op.s[i] == 0) {
            zeroId = i;
            break;
        }
    }

    //查找可移动数码的位置
    for (int i = 0; i < 9;i++) {//遍历数码，顺序生成子节点
        if (abs(zeroId - i) == 1 || abs(zeroId - i) == 3) {//如果下标和0下标相差1或3，进入节点生成函数
            creatNode(op,i,zeroId);
        }
    }
}

生成子节点函数

void creatNode(Open op,int codeId,int zeroId)
{
    /*0,1,2, 3,4,5 ,6,7,8 中换行不能生成子节点：2<->3 、5<->6
    判断zeroId和codeId的位置，若满足则直接return
    */
    if ((zeroId == 2 && codeId == 3) || (zeroId == 5 && codeId == 6) || 
        (zeroId == 3 && codeId == 2) || (zeroId == 6 && codeId == 5)) {
        return;
    }
    //将数码移动到空位
    int temp = op.s[codeId];
    op.s[codeId] = op.s[zeroId];
    op.s[zeroId] = temp;
    //判断是否为重复状态
    if (CLD[countCLD].fatherId != -1) {
        //该节点的父节点没有对应父节点即 fatherId=-1，那么不可能重复
        //当 fatherId != -1 时，那么将该节点与其父节点的父节点对比，如果相同，那么就重复了
        int CountGrandf = CLD[countCLD].fatherId;
        int flag = 0;//重复数码个数
        for (int i = 0; i < 9; i++) {
            if (op.s[i] == CLD[CountGrandf].s[i])flag++;
        }
        //如果是重复状态，接下去的步骤都不必执行了
        if (flag == 9) {
            return;
        }
    }
    //非重复状态，新节点生成，加入OPEN表
    for (int i = 0; i < 9; i++) {
        OP[countOP].s[i] = op.s[i];//因为父节点弹出，直接修改此值，不用对countOP++
    }
    OP[countOP].fatherId = CLD[countCLD].id;//父节点已经放入了CLOSED表中，直接调用CLOSED表中父节点的id
    //子节点深度+1
    OP[countOP].deep = CLD[countCLD].deep + 1;
    //利用评估函数为该子节点估值
    
    //评估函数f(n)=节点深度deep+启发函数hn
    int evalu = OP[countOP].deep + hn(fn);
    OP[countOP].evaluFunc = evalu;

    //后移指针
    countOP++;
    codeCount++;//节点数++
    
}

OPEN表排序

找出OPEN表中评价函数值最小的项，这个节点就是下一次循环的父节点

void bubbleSort(Open* op)
{
    //表首为空
    int zeroCount = 0;
    for (int i = 0; i < 9; i++) {//遍历表首的数码
        if (OP[0].s[i] == 0)zeroCount++;
        if (zeroCount > 1)break;//若为空状态，跳出
    }
    if (zeroCount > 1) {
        for (int i = 0; i < countOP; i++) {//依次前移
            for (int j = 0; j < 9; j++) {
                op[i].s[j] = op[i + 1].s[j];
            }
            op[i].evaluFunc = op[i + 1].evaluFunc;
            op[i].fatherId = op[i + 1].fatherId;
            op[i].deep = op[i + 1].deep;
        }
        countOP--;
    }
    //冒泡排序
    for (int i = 0; i < countOP - 1; i++) {
        for (int j = 0; j < countOP - 1 - i; j++) {
            if (op[j].evaluFunc > op[j + 1].evaluFunc) {//相邻的元素对比估值函数
                //将估值函数较小的状态放到前面
                struct Open temp;
                //temp=op[j+1]
                for (int k = 0; k < 9; k++) {
                    temp.s[k] = op[j + 1].s[k];
                }
                temp.fatherId = op[j + 1].fatherId;
                temp.evaluFunc = op[j + 1].evaluFunc;
                temp.deep = op[j + 1].deep;
                //op[j+1]=op[j]
                for (int k = 0; k < 9; k++) {
                    op[j + 1].s[k] = op[j].s[k];
                }
                op[j + 1].fatherId = op[j].fatherId;
                op[j + 1].evaluFunc = op[j].evaluFunc;
                op[j + 1].deep = op[j].deep;
                //op[j]=temp
                for (int k = 0; k < 9; k++) {
                    op[j].s[k] = temp.s[k];
                }
                op[j].fatherId = temp.fatherId;
                op[j].evaluFunc = temp.evaluFunc;
                op[j].deep = temp.deep;

            }
        }
    }
}

显示函数

void ViewOP(Open* op)
{
    //显示
    cout << "---------------OPEN表---------------" << endl;
    for (int i = 0; i < countOP; i++) {
        cout << i << " | {";
        for (int j = 0; j < 9; j++) {
            cout << op[i].s[j] << ",";
        }
        cout << "} | " << op[i].fatherId << " | " << op[i].evaluFunc << " | " << endl;
        
    }
    cout << "------------------------------------" << endl;
}

void ViewCLD(Closed* cld)
{
    //显示
    cout << "--------------CLOSED表--------------" << endl;
    for (int i = 0; i <= countCLD; i++) {
        cout << i << " | {";
        for (int j = 0; j < 9; j++) {
            cout << cld[i].s[j] << ",";
        }
        cout << "} | " << cld[i].fatherId << " | " << cld[i].evaluFunc << " | " << endl;

    }
    cout << "------------------------------------" << endl;
}

启发式函数值的计算

根据传入参数的不同，选择不同的方式来计算启发式函数值，并根据启发式函数计算当前节点的评估函数值

int hn(int fn)
{
    int result = 0;
    if (fn == 1) {//不在位数码
        for (int i = 0; i < 9; i++) {
            if (OP[countOP].s[i] == 0)continue;
            if (OP[countOP].s[i] != Sg[i])result++;//同位置数码不一致，hn++
        }
    }
    else if (fn == 2) {//曼哈顿距离
        //当前节点数码的横纵坐标
        int rowCode = 0, colCode = 0;
        //初始节点某数码的横纵坐标
        int rowSg = 0, colSg = 0;
        for (int i = 0; i < 9; i++) {//遍历当前节点的每一个数码
            if(OP[countOP].s[i]!=0){
                //找到它的横纵坐标
                rowCode = i / 3;
                colCode = i % 3;
                for (int j = 0; j < 9; j++) {
                    if (Sg[j] == OP[countOP].s[i]) {//寻找初始节点中对应当前数码的数码的位置
                        rowSg = j / 3;
                        colSg = j % 3;
                        break;
                    }
                }
                result += abs(rowCode - rowSg) + abs(colCode - colSg);//数码到目标位置的距离
            }
        }
    }
    
    return result;
}

8数码问题的解

8数码问题有无解应该是可以直接判断的，我没有做这个，具体可以看看别的文章。

完整代码

#include <iostream>
#include <stdlib.h>

using namespace std;

int Sg[9] = { 1,2,3,8,0,4,7,6,5 };//初始节点Sg
//int Sg[9] = { 8,6,0,3,2,5,4,7,1 };
int findedFlag = 0;//为1时，找到结果
int fn;//启发函数的选择
//int deep = 0;//当前节点深度
const int LENGTH = 200000;//结构体数组OP，CLD长度
int codeCount = 0;//总共生成结点数
struct Open //OPEN表
{
    int s[9];//节点
    int fatherId = -1;//默认没有父节点
    int evaluFunc;//评价函数
    int deep = 0;//当前节点深度
};
struct Closed //CLOSED表
{
    int id;//编号
    int s[9];//节点
    int fatherId = -1;//默认没有父节点
    int evaluFunc;//评价函数
    int deep = 0;//当前节点深度
};

//OPEN表结构体数组
struct Open OP[LENGTH];
//CLOSED表结构体数组
struct Closed CLD[LENGTH];
//OPEN表实际长度
int countOP = 0;
//CLOSED表实际长度
int countCLD = 0;

//查找子节点
void search(struct Open op);
//生成子节点,opw为父节点，codeId表示可移动数码的下标,zeroId表示空位下标
void creatNode(Open op, int codeId, int zeroId);
//对OPEN表进行排序
void bubbleSort(struct Open* op);
//OPEN表显示
void ViewOP(struct Open* op);
//CLOSED表显示
void ViewCLD(struct Closed* cld);
//启发函数hn
int hn(int fn);

int main()
{
    cout << "请选择启发函数： 1. h(n)=不在位的数码的总数" << endl;
    cout << "                 2. h(n)=所有数码到目标位置的距离和(曼哈顿距离)" << endl;
    
    cin >> fn;
    if (fn != 1 && fn != 2) {
        cout << "非法！" << endl;
        return 0;
    }
    cout << endl;
    //初始化open表
    OP[countOP] = { {2,8,3,1,6,4,7,0,5},-1,4,0 };//将s0放入open表中
    cout << "请选择8数码输入方式：1.默认    2.手动输入" << endl;
    int choice = 1;
    cin >> choice;
    if (choice == 2) {
        cout << "请依次输入8数码的值（0~8），0表示空位:\n";
        int code;
        for (int i = 0; i < 9; i++) {
            cin >> code;
            while (true) {
                if (code >= 0 && code < 9) {
                    OP[0].s[i] = code;
                    break;
                }
                else {
                    cout << code<<"不合法！请重新输入：" << endl;
                    cin >> code;
                }
            }
        }
        OP[0].deep = 0;
        OP[0].evaluFunc = hn(fn);//deep=0
        int repeat = 0;
        for (int i = 0; i < 9; i++) {//判断是否有重复
            for (int j = i + 1; j < 9; j++) {
                if (OP[0].s[i] == OP[0].s[j])repeat++;
            }
            if (repeat > 0) {
                cout << "8数码输入了重复的数值，启用默认8数码";
                OP[countOP] = { {2,8,3,1,6,4,7,0,5},-1,4,0 };
                break;
            }
        }
    }
    else if (choice != 1) {
        cout << "输入不合法，启用 1.默认方式" << endl;
        OP[countOP] = { {2,8,3,1,6,4,7,0,5},-1,4,0 };
    }
    //显示
    cout << "初始化" << endl;
    cout << "---------------OPEN表---------------" << endl;
    cout << 0 << " | {";
    for (int i = 0; i < 9; i++) {
        cout << OP[countOP].s[i] << ",";
    }
    cout << "} | " << OP[countOP].fatherId << " | " << OP[countOP].evaluFunc << " | " << endl;
    cout << "------------------------------------" << endl;
    //循环次数,用于显示
    int ccount = 0;
    //生成子结点
    
    while (true) {
        //下一层
        //OPEN表中的表首节点赋值到CLOSED表中
        for (int i = 0; i < 9; i++) {
            CLD[countCLD].s[i] = OP[0].s[i];
        }
        CLD[countCLD].evaluFunc = OP[0].evaluFunc;
        CLD[countCLD].fatherId = OP[0].fatherId;
        CLD[countCLD].deep = OP[0].deep;
        
        //CLOSE的表显示
        //ViewCLD(CLD);

        //判断是否为目标Sg，若是，跳出循环，查找结束
        for (int i = 0; i < 9; i++) {
            if (CLD[countCLD].s[i] == Sg[i])findedFlag++;
        }
        if (findedFlag == 9)break;
        else
        {
            findedFlag = 0;
        }

        //查找并生成子节点，并将其加入OPEN表中
        search(OP[0]);
        //对OPEN表进行排序，最小的放在表首,还要对countOP进行适当处理
        //OPEN表排序
        bubbleSort(OP);
        
        //对本次循环的OPEN表显示
        //cout << "第" << ccount + 1 << "次循环" << endl;
        //ViewOP(OP);
        
        //其余处理
        countCLD++;
        if (countCLD == LENGTH) {
            cout << "CLOSED表满未找到!" << endl;
            return -1;
        }
        else{
            CLD[countCLD].id = CLD[countCLD - 1].id + 1;//CLOSED表编号一次递增
        }
        ccount++;//循环次数+1
        
    }
    //CLOSE的表显示
    ViewCLD(CLD);
    cout << "循环结束，最终解答路径如下：" << endl;
    int ccCLD = countCLD;
    cout << ccCLD;
    while (true) {
        if (CLD[ccCLD].fatherId != -1) {
            cout << "->" << CLD[ccCLD].fatherId;
            ccCLD = CLD[ccCLD].fatherId;;
        }
        else {
            break;
        }
    }
    cout << "\n总共生成节点数：" << codeCount << endl;
    
    return 0;
}

void search(Open op)
{
    //将OPEN表首置0
    for (int i = 0; i < 9; i++) {
        OP[0].s[i] = 0;
    }
    OP[0].evaluFunc = 0;
    OP[0].deep = 0;
    //查找0的位置并记录
    int zeroId = 0;
    for (int i = 0; i < 9; i++) {
        if (op.s[i] == 0) {
            zeroId = i;
            break;
        }
    }

    //查找可移动数码的位置
    for (int i = 0; i < 9;i++) {//遍历数码，顺序生成子节点
        if (abs(zeroId - i) == 1 || abs(zeroId - i) == 3) {//如果下标和0下标相差1或3，进入节点生成函数
            creatNode(op,i,zeroId);
        }
    }
}

void creatNode(Open op,int codeId,int zeroId)
{
    /*0,1,2, 3,4,5 ,6,7,8 中换行不能生成子节点：2<->3 、5<->6
    判断zeroId和codeId的位置，若满足则直接return
    */
    if ((zeroId == 2 && codeId == 3) || (zeroId == 5 && codeId == 6) || 
        (zeroId == 3 && codeId == 2) || (zeroId == 6 && codeId == 5)) {
        return;
    }
    //将数码移动到空位
    int temp = op.s[codeId];
    op.s[codeId] = op.s[zeroId];
    op.s[zeroId] = temp;
    //判断是否为重复状态
    if (CLD[countCLD].fatherId != -1) {
        //该节点的父节点没有对应父节点即 fatherId=-1，那么不可能重复
        //当 fatherId != -1 时，那么将该节点与其父节点的父节点对比，如果相同，那么就重复了
        int CountGrandf = CLD[countCLD].fatherId;
        int flag = 0;//重复数码个数
        for (int i = 0; i < 9; i++) {
            if (op.s[i] == CLD[CountGrandf].s[i])flag++;
        }
        //如果是重复状态，接下去的步骤都不必执行了
        if (flag == 9) {
            return;
        }
    }
    //非重复状态，新节点生成，加入OPEN表
    for (int i = 0; i < 9; i++) {
        OP[countOP].s[i] = op.s[i];//因为父节点弹出，直接修改此值，不用对countOP++
    }
    OP[countOP].fatherId = CLD[countCLD].id;//父节点已经放入了CLOSED表中，直接调用CLOSED表中父节点的id
    //子节点深度+1
    OP[countOP].deep = CLD[countCLD].deep + 1;
    //利用评估函数为该子节点估值
    
    //评估函数f(n)=节点深度deep+启发函数hn
    int evalu = OP[countOP].deep + hn(fn);
    OP[countOP].evaluFunc = evalu;

    //后移指针
    countOP++;
    codeCount++;//节点数++
    
}

void bubbleSort(Open* op)
{
    //表首为空
    int zeroCount = 0;
    for (int i = 0; i < 9; i++) {//遍历表首的数码
        if (OP[0].s[i] == 0)zeroCount++;
        if (zeroCount > 1)break;//若为空状态，跳出
    }
    if (zeroCount > 1) {
        for (int i = 0; i < countOP; i++) {//依次前移
            for (int j = 0; j < 9; j++) {
                op[i].s[j] = op[i + 1].s[j];
            }
            op[i].evaluFunc = op[i + 1].evaluFunc;
            op[i].fatherId = op[i + 1].fatherId;
            op[i].deep = op[i + 1].deep;
        }
        countOP--;
    }
    //冒泡排序
    for (int i = 0; i < countOP - 1; i++) {
        for (int j = 0; j < countOP - 1 - i; j++) {
            if (op[j].evaluFunc > op[j + 1].evaluFunc) {//相邻的元素对比估值函数
                //将估值函数较小的状态放到前面
                struct Open temp;
                //temp=op[j+1]
                for (int k = 0; k < 9; k++) {
                    temp.s[k] = op[j + 1].s[k];
                }
                temp.fatherId = op[j + 1].fatherId;
                temp.evaluFunc = op[j + 1].evaluFunc;
                temp.deep = op[j + 1].deep;
                //op[j+1]=op[j]
                for (int k = 0; k < 9; k++) {
                    op[j + 1].s[k] = op[j].s[k];
                }
                op[j + 1].fatherId = op[j].fatherId;
                op[j + 1].evaluFunc = op[j].evaluFunc;
                op[j + 1].deep = op[j].deep;
                //op[j]=temp
                for (int k = 0; k < 9; k++) {
                    op[j].s[k] = temp.s[k];
                }
                op[j].fatherId = temp.fatherId;
                op[j].evaluFunc = temp.evaluFunc;
                op[j].deep = temp.deep;

            }
        }
    }
}

void ViewOP(Open* op)
{
    //显示
    cout << "---------------OPEN表---------------" << endl;
    for (int i = 0; i < countOP; i++) {
        cout << i << " | {";
        for (int j = 0; j < 9; j++) {
            cout << op[i].s[j] << ",";
        }
        cout << "} | " << op[i].fatherId << " | " << op[i].evaluFunc << " | " << endl;
        
    }
    cout << "------------------------------------" << endl;
}

void ViewCLD(Closed* cld)
{
    //显示
    cout << "--------------CLOSED表--------------" << endl;
    for (int i = 0; i <= countCLD; i++) {
        cout << i << " | {";
        for (int j = 0; j < 9; j++) {
            cout << cld[i].s[j] << ",";
        }
        cout << "} | " << cld[i].fatherId << " | " << cld[i].evaluFunc << " | " << endl;

    }
    cout << "------------------------------------" << endl;
}

int hn(int fn)
{
    int result = 0;
    if (fn == 1) {//不在位数码
        for (int i = 0; i < 9; i++) {
            if (OP[countOP].s[i] == 0)continue;
            if (OP[countOP].s[i] != Sg[i])result++;//同位置数码不一致，hn++
        }
    }
    else if (fn == 2) {//曼哈顿距离
        //当前节点数码的横纵坐标
        int rowCode = 0, colCode = 0;
        //初始节点某数码的横纵坐标
        int rowSg = 0, colSg = 0;
        for (int i = 0; i < 9; i++) {//遍历当前节点的每一个数码
            if(OP[countOP].s[i]!=0){
                //找到它的横纵坐标
                rowCode = i / 3;
                colCode = i % 3;
                for (int j = 0; j < 9; j++) {
                    if (Sg[j] == OP[countOP].s[i]) {//寻找初始节点中对应当前数码的数码的位置
                        rowSg = j / 3;
                        colSg = j % 3;
                        break;
                    }
                }
                result += abs(rowCode - rowSg) + abs(colCode - colSg);//数码到目标位置的距离
            }
        }
    }
    
    return result;
}