来自  资质荣誉 2019-09-20 23:39 的文章
当前位置: 澳门太阳娱乐手机登录 > 资质荣誉 > 正文

两数和问题,用贪心算法解决马踏棋盘问题

开始就用到了c++的哈希表是真的恶心,首先学习一波基础知识

用贪心算法解决马踏棋盘问题时,主要的思想与用递归的方法解决该问题相同,都是用深度优先搜索,只是在选下一个结点的时候做了贪心算法优化,其思路如下:

从起始点开始,根据“马”的走法,它的下一步的可选择数是有0—8个的。

下面放下大佬的代码

已知,当马下一步的可选择数为0的时候(即马没有下一个节点可跳),进行回溯。当下一步的可选择数有1个的时候,我们直接取那一步就可以。但是如果下一步的可选择数有多个的时候呢?

class Solution {public:    vector<int> twoSum(vector<int>& nums, int target) {      vector<int>a;        a.push_back(-1);        for(int i=0;i<nums.size();i++)        {        for(int j=i+1;j<nums.size();j++)           if(nums[i]+nums[j]==target)           {               a[0]=i;               a[1]=j;               return a;           }        }                }};

澳门太阳娱乐在线网址,在之前用的递归+回溯算法中,我们是任意取一个的,只要它在棋盘内,且未遍历就可以了。但其实我们怎么选下一步,对搜索的效率影响是非常大的!

这里是完整版代码

 

class Solution {public:    vector<int> twoSum(vector<int>& nums, int target) {      vector<int>a;        a.push_back(-1);        for(int i=0;i<nums.size();i++)        {        for(int j=i+1;j<nums.size();j++)           if(nums[i]+nums[j]==target)           {               a[0]=i;               a[1]=j;               return a;           }        }                }};void trimLeftTrailingSpaces(string &input) {    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {        return !isspace;    }));}void trimRightTrailingSpaces(string &input) {    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {        return !isspace;    }).base(), input.end;}vector<int> stringToIntegerVector(string input) {    vector<int> output;    trimLeftTrailingSpaces;    trimRightTrailingSpaces;    input = input.substr(1, input.length() - 2);    stringstream ss;    ss.str;    string item;    char delim = ',';    while (getline(ss, item, delim)) {        output.push_back(stoi;    }    return output;}int stringToInteger(string input) {    return stoi;}string integerVectorToString(vector<int> list, int length = -1) {    if (length == -1) {        length = list.size();    }    if (length == 0) {        return "[]";    }    string result;    for(int index = 0; index < length; index++) {        int number = list[index];        result += to_string + ", ";    }    return "[" + result.substr(0, result.length() - 2) + "]";}int main() {    string line;    while (getline(cin, line)) {        vector<int> nums = stringToIntegerVector;        getline(cin, line);        int target = stringToInteger;                vector<int> ret = Solution().twoSum(nums, target);        string out = integerVectorToString;        cout << out << endl;    }    return 0;}

贪心算法:又称贪婪算法,是指在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。

这貌似有点高深但是算法复杂度是非常低的,貌似是4msj解决,我们再利用基础的c暴力解决下,

用贪心算法的思想来解决在棋盘如何选择下一个节点的问题,就是计算马儿的哪个下一节点对应的下一个节点(即下下个节点)的总数最少,就将哪个下一节点视为最优。

双重循环遍历,代码如下

例如:假设a、b、c、d为马儿可以选择的下一个节点,选哪个比较好,就看哪个点的后续下一步比较少。如果马走到a点后的下一步有3个选择;而b的下一步有2个;c有1个,d有2个,那么最优选择是:c点。

int* twoSum(int* nums, int numsSize, int target) {    int *a;    a=(int *)malloc(2*sizeof(int));    for(int i=0;i<numsSize-1;i++)    {        for(int j=i+1;j<numsSize;j++)        {            if((nums[i]+nums[j])==target)             {              a[0]=i;              a[1]=j;             }        }    }    return a;

因为c点的后续下一步很少,如果不先遍历它的话以后可能会很难遍历到它。甚至极端一点的情况是,如果现在不遍历它,以后都遍历不到了。遍历不成功的时候只能回溯,一直回溯到此刻的点,然后选了c点以后才能完成,这就浪费了大量的时间。

但是这个不是最优的,最优算法貌似是采用二分法 代码像这样

选择下一个节点的函数如下图所示,其中,num是马在当前位置时,下一个节点的数目。数组a[]的长度为num,a[]中存放马的每个下一节点所对应的下一个节点的数目。

int* twoSum(int* nums, int numsSize, int target) {    int *a;    a=(int *)malloc(2*sizeof(int));    int mid=numsSize/2;    for(int i=0;i<mid;i++)    {        for(int j=mid;j<numsSize;j++)        {            if((nums[i]+nums[j])==target)             {              a[0]=i;              a[1]=j;             }        }    }    return a;

澳门太阳娱乐在线网址 1

最后在用python解决下吧

用贪心算法求解马踏棋盘问题的一个解的代码如下。当然,一般来讲棋盘的大小应该为8*8,此处,定义的是6*6,主要是为了方便和我之前的用递归+回溯的方法写的代码进行对比,用递归的话,用8*8的棋盘,执行的时间有点长,于是就用了6*6的.

def twoSum(self, nums, target):       hashmap={}       for index, num in enumerate:            another_num = target - num            if another_num in hashmap:                return [hashmap[another_num], index]            hashmap[num] = index       return None
  1     # include <stdio.h>  
  2     # include <stdlib.h>  
  3     # include <math.h>  
  4     # include <time.h>
  5     # define R 6  
  6     # define C 6  
  7     int cheesboard [R] [C];  
  8     const int moveX [8] = {-2,-1,1,2,2,1,-1,-2};  
  9     const int moveY [8] = {1,2,2,1,-1,-2,-2,-1};  
 10     //初始化棋盘,将棋盘所有的位置赋值为0  
 11     void initBoard (int board[][C]){  
 12         int i ,j;
 13         for(i = 0; i < R; i ++){  
 14             for( j = 0; j < C; j ++){  
 15                 board[i][j] = 0;  
 16             }  
 17         }  
 18     }
 19     //从待选的下一个点的集合中,选取它们其中所对应的下一个节点数目最少的一个
 20     int getMinPath (int a[],int num){  //num:下一个节点的数目,
 21         //a[]:每一个 下一个节点 对应的下一节点的数目
 22         //定义下标为  
 23         int i = 0,index=0;  
 24         //定义最小的值为a(0),找到最小的值,而且大于0的值  
 25         int min= a[0];  
 26         //找出数组中第一个大于0的值为min
 27         for(i = 0 ; i< num; i++)  
 28         {  
 29             if(a[i] > 0)  
 30             {  
 31                 min = a[i];  
 32                 index = i;  
 33                 break;  
 34             }  
 35         }  
 36         for(i = index + 1; i < num ;  i++)  
 37         {  
 38             if(a[i] > 0 && min > a[i])  
 39             {  
 40                 min = a[i];  
 41                 index = i;  
 42             }  
 43         }  
 44         if(a[index] > 0)  
 45             return index;  
 46         return -1;  
 47     }
 48     // 打印路径  
 49     void printPath (int board[][C]){  
 50         int i,j;  
 51         for (i = 0; i < R; i++){  
 52             for ( j = 0; j < C; j++){  
 53                 printf("%dt",board[i][j]);  
 54             }  
 55             printf("nn");  
 56         }  
 57     }  
 58     // 获得马行走的路径  
 59     void getPath (int board [][C], int startX, int startY){  
 60         //下一个可行位置的数目
 61         int next = 0;  
 62         //路径最短的可行位置在数组中的位置  
 63         int min;  
 64         //下一个可行位置的可行位置数目  
 65         int nextNext;  
 66         //将棋盘初始化  
 67         initBoard (board);  
 68         // 存放下一个位置对应的下一个位置的数目  
 69         int nextNum[8] = {0,0,0,0,0,0,0,0};  
 70         //下一个位置的在二维数组中对应位置,初始为0  
 71         int nextX[C] = {0};  
 72         int nextY[R] = {0};  
 73         //第一个位置赋值为1  
 74         board [startX] [startY] = 1;  
 75         int m,i,j;  
 76         //走完所有的点要循环63次  
 77         for ( m = 1; m < R*C; m++){  
 78                 //当前点其后面可行的位置设为0  
 79                 next = 0;  
 80         //通过循环来判断该位置是否还可以向下面位置移动  
 81         for ( i =  0; i < 8; i++){  
 82             if(startX + moveX[i] < 0 || startX + moveX[i] >= R  
 83                 || startY + moveY[i] < 0 || startY + moveY[i] >= C 
 84                 || board[startX+moveX[i]][startY+moveY[i]] != 0){  
 85                     continue;  
 86                 }
 87                 //如果可以向下一个位置移动的话,通过next数组保存下来,通过next记录下有多少个  
 88             nextX [next] = startX + moveX[i];  
 89             nextY [next] = startY + moveY[i];  
 90             next ++;  
 91         }  
 92         //循环结束之后,对next的值进行判断,当为1的时候  
 93         if (next == 1){  
 94             //让min=0,表示现在所需要的位置是在我们的保存next数组中的第一位  
 95             min = 0;  
 96         //设置初始点  
 97             goto set_nextpoint;  
 98         }  
 99         //无法向下一个位置移动了  
100         else if (next == 0){  
101             printf("没有路径可走了n");  
102             goto print_path;  
103         }  
104         else {  
105                 /*当有多个路径可以走的时候,检测每一个点还可不可以继续向下走然后 
106                 记录下来该点有几个点可以向下走,找到最少的一个但是不为0的哪一个 
107                 */  
108             for (i = 0; i<next; i++){  
109                 nextNext = 0;  
110                 for(j = 0; j < 8; j++){  
111                     if(nextX[i] + moveX[j] >=0 && nextX[i] + moveX[j] < R  
112                         && nextY[i] + moveY[j] >= 0 && nextY[i] + moveY[j] <C  
113                         && board [nextX[i]+moveX[j]][nextY[i]+moveY[j]] == 0){  
114                             nextNext ++;
115                         }
116                 }  
117                 nextNum[i] = nextNext;  
118             }  
119             if ((min = getMinPath(nextNum,next))>=0 )  
120             {  
121                 goto set_nextpoint;  
122             }  
123             else{  
124                 printf("没有路径可走了n");  
125                 goto print_path;  
126             }  
127         }  
128     set_nextpoint:  
129             startX = nextX[min];  
130             startY = nextY[min];  
131             board[startX][startY] = m+1;  
132         }  
133     print_path:  
134         printPath(board);  
135       
136     }  
137      void judgeExistence(){
138             if(R<=4 || C<=4){//通过已有的理论给出判断条件
139                 printf("棋盘矩阵为%d * %d 时,马从其中一些节点出发,不能够找到"
140                     "n不重复遍历完棋盘中每一格的路径.请重新设置矩阵的大小,矩"
141                     "n阵的大小应满足行数和列数均大于4n",R,C);
142                 exit(0);
143             }
144         }
145     int main (){  
146         int i,j;  
147         //main函数后首先执行一个判断存在性的函数    
148         judgeExistence();
149         clock_t start, finish;  //计算核心方法一共花费了多少时间
150         long duration;
151 
152         //获得最开始的位置  
153         label_1:printf("请输入马初始横坐标(X<=%d):X=n",R);
154         scanf("%d",&i);
155         if(i>R){
156             printf("请输入小于等于%d的数n",R);
157             goto label_1;
158         }
159         label_2:printf("请输入马初始纵坐标(Y<=%d):Y=n",C);
160         scanf("%d",&j);
161         if(j>C){
162             printf("请输入小于等于%d的数n",C);
163             goto label_2;
164         }
165         start=clock();//开始时间
166         i=i-1;
167         j=j-1;
168     
169         //调用该函数获取路径  
170         getPath(cheesboard, i, j); 
171         finish=clock();
172         duration=finish-start;
173         printf("棋盘的大小为%d*%dn",R,C);
174         printf("采用贪心算法所需的时间为%ldt ms n",duration);
175         return 0;
176     }

 

本文由澳门太阳娱乐手机登录发布于 资质荣誉,转载请注明出处:两数和问题,用贪心算法解决马踏棋盘问题

关键词: