-
RL之Q Learning：利用强化学习之Q Learning实现走迷宫—训练智能体走到迷宫(复杂迷宫)的宝藏位置
2018-10-21 21:25:17RL之Q Learning：利用强化学习之Q Learning实现走迷宫—训练智能体走到迷宫(复杂迷宫)的宝藏位置 目录 输出结果 设计思路 实现代码 测试记录全过程 输出结果 设计思路 实现代码 ...展开全文RL之Q Learning：利用强化学习之Q Learning实现走迷宫—训练智能体走到迷宫(复杂迷宫)的宝藏位置
目录
输出结果
设计思路
实现代码
from __future__ import print_function import numpy as np import time from env import Env from reprint import output EPSILON = 0.1 ALPHA = 0.1 GAMMA = 0.9 MAX_STEP = 30 np.random.seed(0) def epsilon_greedy(Q, state): if (np.random.uniform() > 1 - EPSILON) or ((Q[state, :] == 0).all()): action = np.random.randint(0, 4) # 0~3 else: action = Q[state, :].argmax() return action e = Env() Q = np.zeros((e.state_num, 4)) with output(output_type="list", initial_len=len(e.map), interval=0) as output_list: for i in range(100): e = Env() while (e.is_end is False) and (e.step < MAX_STEP): action = epsilon_greedy(Q, e.present_state) state = e.present_state reward = e.interact(action) new_state = e.present_state Q[state, action] = (1 - ALPHA) * Q[state, action] + \ ALPHA * (reward + GAMMA * Q[new_state, :].max()) e.print_map_with_reprint(output_list) time.sleep(0.1) for line_num in range(len(e.map)): if line_num == 0: output_list[0] = 'Episode:{} Total Step:{}, Total Reward:{}'.format(i, e.step, e.total_reward) else: output_list[line_num] = '' time.sleep(2)测试记录全过程
开始 ......... ......... . x . ......... . x . .A x o . ......... . x . .A x o . . . ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . x o . . . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . .A x o . .A . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . . x o . . . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . . x o . .A . ......... ......... . x . .A x o . .A . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . .A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . x o . . . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x A . . A . ......... ......... . x . . x A . . . ......... ......... . x . . x A . . . ......... Episode:0 Total Step:17, Total Reward:100 . x . . x A . . . ......... Episode:0 Total Step:17, Total Reward:100 . x A . . . ......... Episode:0 Total Step:17, Total Reward:100 . . ......... Episode:0 Total Step:17, Total Reward:100 ......... Episode:0 Total Step:17, Total Reward:100 ......... ......... . x . ......... . x . .A x o . ......... . x . .A x o . . . ......... . x . .A x o . . . ......... …… ......... . A . . x o . . . ......... Episode:2 Total Step:30, Total Reward:-5 . A . . x o . . . ......... Episode:2 Total Step:30, Total Reward:-5 . x o . . . ......... Episode:2 Total Step:30, Total Reward:-5 . . ......... Episode:2 Total Step:30, Total Reward:-5 ......... Episode:2 Total Step:30, Total Reward:-5 [F …… ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . xAo . . A . ......... ......... . x . . xAo . . . ......... ......... . x . . xAo . . . ......... ......... . x . . xAo . . . ......... ......... . x . . xAo . . . ......... ......... . x . . x A . . . ......... ......... . x . . x A . . . ......... ......... . x . . x A . . . ......... Episode:98 Total Step:8, Total Reward:100 . x . . x A . . . ......... Episode:98 Total Step:8, Total Reward:100 . x A . . . ......... Episode:98 Total Step:8, Total Reward:100 . . ......... Episode:98 Total Step:8, Total Reward:100 ......... Episode:98 Total Step:8, Total Reward:100 ......... ......... . Ax . ......... . Ax . . x o . ......... . Ax . . x o . . . ......... . Ax . . x o . . . ......... ......... . Ax . . x o . . . ......... ......... . Ax . . x o . . . ......... ......... . Ax . . x o . . . ......... ......... . Ax . . x o . . . ......... ......... . Ax . . x o . . . ......... ......... . Ax . . x o . . . ......... ......... . x . . x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . A x o . . . ......... ......... . x . . x o . . . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . Ax o . . A . ......... ......... . x . . Ax o . . . ......... ......... . x . . Ax o . . . ......... ......... . x . . Ax o . . . ......... ......... . x . . Ax o . . . ......... ......... . x . . x o . . . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . x o . . A . ......... ......... . x . . xAo . . A . ......... ......... . x . . xAo . . . ......... ......... . x . . xAo . . . ......... ......... . x . . xAo . . . ......... ......... . x . . xAo . . . ......... ......... . x . . x A . . . ......... ......... . x . . x A . . . ......... ......... . x . . x A . . . ......... Episode:99 Total Step:11, Total Reward:100 . x . . x A . . . ......... Episode:99 Total Step:11, Total Reward:100 . x A . . . ......... Episode:99 Total Step:11, Total Reward:100 . . ......... Episode:99 Total Step:11, Total Reward:100 ......... Episode:99 Total Step:11, Total Reward:100 Episode:99 Total Step:11, Total Reward:100
-
Java-复杂迷宫求解
2018-04-17 02:38:55总体的思路不太复杂：首先创建一个栈结构，可以方便的输出最短的路径，然后就是合理的运用递归的思想来进行路径的回溯。先上代码。interface Method{//实现迷宫的栈结构的接口 int MAX = 50;//栈的最大存储量，也...展开全文最近用C学了数据结构的迷宫求解问题，但是个人感觉用C实现特别麻烦。索性用Java来实现了。总体的思路不太复杂：首先创建一个栈结构，可以方便的输出最短的路径，然后就是合理的运用递归的思想来进行路径的回溯。先上代码。
嗯，如果有不合理的地方还请大神指教。interface Method{//实现迷宫的栈结构的接口 int MAX = 50;//栈的最大存储量，也就是路径的最长量 void StackInit(StackList stackList);//初始化 void StackAdd(StackList stackList, place Number);//插入 void StackDelete(StackList stackList);//删除 void Display(StackList stackList);//打印（测试用） } class StackList{//栈结构 place[] data; int size; int capacity; } class My_Method implements Method{//实现栈相关方法的类 @Override public void StackInit(StackList stackList) { if(stackList == null){ return; } stackList.data = new place[MAX]; stackList.capacity = MAX; stackList.size = 0; } @Override public void StackAdd(StackList stackList, place Number) { if(stackList == null){ return; } if(stackList.size == stackList.capacity){ return; } stackList.data[stackList.size] = Number; stackList.size++; } @Override public void StackDelete(StackList stackList) { if(stackList == null){ return; } if(stackList.size == 0){ return; } stackList.size--; } @Override public void Display(StackList stackList) { if(stackList == null){ return; } for(int i = 0;i<stackList.size;i++){ System.out.print(" "+stackList.data[i]); } } } //----------------------------------------------------------- interface Maze_Method{//有关迷宫地图的实现方法的接口 int ROW = 6;//迷宫的行与列 int COL = 6; boolean Exit(Maze maze,place now_place,place start);//检查是不是出口 void mark(Maze maze, place now_place, place prev_place);//做标记 boolean CanStay(Maze maze, place now_place, place prev_place);//判断是否可以落到这个位置上 void Walk(Maze maze, place start, place now_place, place prev_place, StackList cur, StackList _short, Method My_Test);//递归函数 void Init(Maze maze);//初始化地图 void Display(Maze maze);//打印地图 } interface Maze_area{ int ROW = 6;//迷宫的大小 int COL = 6; } class Maze implements Maze_area{//迷宫地图 int[][] map = new int[ROW][COL]; } class My_Maze_Method implements Maze_Method{//实现迷宫相关的方法 @Override public void Init(Maze maze) {//初始化地图 int[][] New_Map = new int[][]{{0,1,0,0,0,0}, {1,1,0,0,0,0}, {0,1,0,1,1,1}, {1,1,1,1,0,0}, {0,0,0,1,0,0}, {0,0,0,1,0,0,}}; maze.map = New_Map; } @Override public void Display(Maze maze) {//打印地图 for(int i = 0;i<maze.map.length;i++){ for(int j = 0;j<maze.map[0].length;j++){ System.out.print(" "+ maze.map[i][j]); } System.out.println(); } } @Override public boolean Exit(Maze maze, place now_place, place start) {//检查是否是出口 if(now_place == start){ return false; } if(now_place.row == 0 || now_place.row == ROW-1 || now_place.col == 0 || now_place.col == COL-1){ return true; } return false; } @Override public boolean CanStay(Maze maze, place now_place, place prev_place) {//检查某位置是否合法 if((now_place.row >= ROW) || (now_place.row < 0) || (now_place.col >= COL) || (now_place.col < 0)){ return false; } if(maze.map[now_place.row][now_place.col] == 0){ return false; } if(maze.map[now_place.row][now_place.col] == 1){ return true; } if(maze.map[prev_place.row][prev_place.col] > (maze.map[now_place.row][now_place.col] + 1)){ return true; } return false; } @Override public void mark(Maze maze, place now_place, place prev_place) {//标记一个位置 if (prev_place.row == -1 && prev_place.col == -1) { maze.map[now_place.row][now_place.col] = 2; } else { maze.map[now_place.row][now_place.col] = maze.map[prev_place.row][prev_place.col] + 1; } } @Override public void Walk(Maze maze, place start, place now_place, place prev_place, StackList cur, StackList _short, Method My_test) {//递归函数 if(!CanStay(maze,now_place,prev_place)){//看是否可以在这个位置走 return; } mark(maze,now_place,prev_place);//做标记 My_test.StackAdd(cur,now_place);//将能走的地方入栈 if(Exit(maze,now_place,start)){//如果是出口，那么把cur栈和_short栈的大小做比较， if(_short.size == 0) {//把比较小的那个保存在_short栈中 _short.data = cur.data; _short.size = cur.size; _short.capacity = cur.capacity; } if(_short.size > cur.size){ _short.data = cur.data; _short.size = cur.size; _short.capacity = cur.capacity; } My_test.StackDelete(cur);//如果是出口，那么删除栈顶，回溯 System.out.println("找到一个出口"); return; } //顺时针扫描一个位置的上下左右 place up = new place(now_place.row-1,now_place.col); prev_place = now_place; Walk(maze,start,up,prev_place,cur,_short,My_test); place right = new place(now_place.row,now_place.col+1); prev_place = now_place; Walk(maze,start,right,prev_place,cur,_short,My_test); place down = new place(now_place.row+1,now_place.col); prev_place = now_place; Walk(maze,start,down,prev_place,cur,_short,My_test); place left = new place(now_place.row,now_place.col-1); prev_place = now_place; Walk(maze,start,left,prev_place,cur,_short,My_test); My_test.StackDelete(cur); } } //------------------------------------------------------- class place{//描述点的位置 int row; int col; place(int row, int col){ this.row = row; this.col = col; } place(){} } public class Main{ public static void main(String[] args){ Maze My_Maze = new Maze();//创建栈对象 Method Test_stack = new My_Method();//创建栈的实现对象 StackList stackList_cur = new StackList();//创建每条路径的栈对象 StackList stackList_short = new StackList();//创建代表最短路径的栈对象 Test_stack.StackInit(stackList_cur);//初始化栈对象 Test_stack.StackInit(stackList_short);//初始化栈对象 Maze_Method New_Test = new My_Maze_Method();//初始化迷宫的实现对象 place Enter = new place(0,1);//创建入口对象 place Prev = new place(-1,-1);//创建前一个对象（这里的赋值主要针对入口点，我们可以直接把它赋值成特定的非法值） Maze maze = new Maze();//创建地图对象 New_Test.Init(maze);//初始化地图 New_Test.Walk(maze,Enter,Enter,Prev,stackList_cur,stackList_short,Test_stack);//实现迷宫求解的主要递归方法 New_Test.Display(maze);//打印迷宫路径 System.out.println("迷宫的最短路径是："); for(int i = 0; i<stackList_short.size;i++){//打印最短路径 System.out.println("("+stackList_short.data[i].row+","+stackList_short.data[i].col+")"); } } }
-
数据结构---对复杂迷宫进行求解（通路间带环）
2018-04-23 17:03:29我们通常见的迷宫多种多样，在这里以多通路迷宫为例，对迷宫进行求解，找出最短路径，用C语言对其进行编写，涉及到一些操作包括： 1. 初始化迷宫地图数据 --》2. 检测迷宫的入口是否有效 --》 3. 检测当前位置...展开全文我们通常见的迷宫多种多样，在这里以多通路迷宫为例，对迷宫进行求解，找出最短路径，用C语言对其进行编写，涉及到一些操作包括：
1. 初始化迷宫地图数据 --》2.检测迷宫的入口是否有效 --》 3. 检测当前位置是否为迷宫的出口 --》4. 保存最短路径 --》5. 检测当前位置的下一步是否能够走通 --》6. 走迷宫 --》7. 具体走迷宫方式 --》8. 打印迷宫地图数据 --》9. 打印路径
下面用C实现该操作的一些代码：
maze.c-->下面是用递归的方式找到迷宫中的最短路径
#define _CRT_SECURE_NO_WARNINGS 0; #include "maze.h" #include "stack.h" #include <stdio.h> #include <assert.h> //初始化迷宫 void MazeInit(maze* s, DataTypeMaze arr[MAZE_ROW][MAZE_COL]) { assert(s); int i = 0, j = 0; for (i = 0; i < MAZE_ROW; i++) { for (j = 0; j < MAZE_COL; j++) { s->maze[i][j] = arr[i][j]; } } } //打印迷宫 void PrintMaze(maze m) { int i = 0, j = 0; for (i = 0; i < MAZE_ROW; i++) { for (j = 0; j < MAZE_COL; j++) { printf("%d ", m.maze[i][j]); } printf("\n"); } } // 检测迷宫的入口是否有效 int IsValidEnter(maze *m, PosType enter) { assert(m); if ((enter._x == 0) || (enter._y == 0) || (enter._x == MAZE_ROW - 1) || (enter._y == MAZE_COL - 1)) { if (m->maze[enter._x][enter._y] >= 1) return 1; } return 0; } // 检测cur位置是否为迷宫的出口 int IsMazeExit(maze* m, PosType cur, PosType enter) { assert(m); if (cur._x == enter._x && cur._y == enter._y) return 0; if (cur._x == 0 || cur._x == MAZE_COL - 1 || cur._y == 0 || cur._y == MAZE_ROW - 1) { return 1; } return 0; } // 检测当前位置是否为通路 int IsPass(maze* m, PosType cur) { assert(m); if (m->maze[cur._x][cur._y] == 1) return 1; return 0; } // 打印路径 void PrintPath(Stack* s) { assert(s); printf("over"); while (!IsEmptyStack(s)) { printf("<- %d,%d ", StackTop(s)); StackPop(s); } } // 检测当前位置的下一步是否能够走通 int IsNextPass(maze* m,PosType cur, PosType next) { assert(m); if ((m->maze[next._x][next._y] == 1) || (m->maze[cur._x][cur._y]< m->maze[next._x][next._y])) return 1; return 0; } void printPath(Stack Path) { int i = 0; for (; i < stackSize(&Path); i++) { printf("%d,%d-> ", Path.arr[i]); } printf("over \n"); } // 保存最短路径 void SaveShortPath(Stack* path, Stack* shortPath) { assert(path); assert(shortPath); int i = 0; shortPath->_top = 0; for (; i < stackSize(path); i++) { StackPush(shortPath, path->arr[i]); } } // 走迷宫 void PassMaze(maze* m, PosType enter, Stack* ShortPath) { assert(m); assert(ShortPath); Stack path; if (!IsValidEnter(m, enter)) { printf("无效的入口点"); return; } StackInit(&path); _PassMaze(m, enter, enter,&path,ShortPath); } // 复杂迷宫--》具体走迷宫方式 void _PassMaze(maze *m, PosType enter,PosType cur, Stack *path,Stack* shortPath) { assert(path); assert(shortPath); PosType next = cur; if (cur._x ==enter._x && cur._y == enter._y) m->maze[cur._x][cur._y] = 2; StackPush(path, cur); if (IsMazeExit(m, cur, enter)) { if (shortPath->_top == 0 || stackSize(path)<stackSize(shortPath)) SaveShortPath(path, shortPath); StackPop(path); return; } //上 next = cur; next._x -= 1; if (IsNextPass(m, cur, next)) { m->maze[next._x][next._y] = m->maze[cur._x][cur._y] + 1; _PassMaze(m,enter, next, path, shortPath); } //右 next = cur; next._y += 1; if (IsNextPass(m, cur, next)) { m->maze[next._x][next._y] = m->maze[cur._x][cur._y] + 1; _PassMaze(m, enter, next, path, shortPath); } //左 next = cur; next._y -= 1; if (IsNextPass(m, cur, next)) { m->maze[next._x][next._y] = m->maze[cur._x][cur._y] + 1; _PassMaze(m, enter, next, path, shortPath); } //下 next = cur; next._x += 1; if (IsNextPass(m, cur, next)) { m->maze[next._x][next._y] = m->maze[cur._x][cur._y] + 1; _PassMaze(m, enter, next, path, shortPath); } StackPop(path); }
下面是用测试代码
上面就是实现复杂迷宫求解的C代码，下一篇会写用循环和递归两种方式对简单迷宫进行求解！！！//多通络带环迷宫 void testMaze() { maze m; Stack shortPath; StackInit(&shortPath); DataType x; x._x = 5; x._y = 1; DataTypeMaze arr[MAZE_ROW][MAZE_COL] = { { 0,0 },{ 0, 1,1,1 },{ 0, 1,0,1 },{ 0, 1, 0, 1},{ 0,1,1,1,1,1 },{ 0, 1} }; MazeInit(&m, arr); PrintMaze(m); PassMaze(&m, x, &shortPath); printf("迷宫最短路径--："); PrintPath(&shortPath); printf("**********************\n"); PrintMaze(m); } int main() { testMaze(); system("pause"); return 0; }
-
#复杂迷宫求解（2）
2018-08-30 20:48:22// 初始化迷宫 void InitMaze ( Maze * m , int map [ ROW ] [ COL ] ) ; // 打印迷宫 void PrintMaze ( Maze * m ) ; // 检测是否为有效的入口 int IsValidEnter ( Maze * m , ...展开全文#头文件
#pragma once #include <stdio.h> #include <string.h> #include <assert.h> #include <stdlib.h> #define ROW 6 #define COL 6 typedef struct Maze { int _map[ROW][COL]; }Maze; typedef struct Position { int _x; int _y; }Position; //Stack.h #define MAX 100 typedef Position DataType; typedef struct Stack { int top; DataType stack[MAX]; }Stack; void StackInit(Stack* s); void StackPush(Stack* s, DataType data); void StackPop(Stack* s); DataType GetStackTop(Stack*s); int GetStackSize(Stack*s); int StackEmpty(Stack *s); // 初始化迷宫 void InitMaze(Maze* m, int map[ROW][COL]); // 打印迷宫 void PrintMaze(Maze* m); // 检测是否为有效的入口 int IsValidEnter(Maze* m, Position enter); // 检测pos是否在出口的位置 int IsExit(Position pos, Position enter); // 检测cur的下一步next是否为通路： // next位置为1 || next位置保存数据 大于 cur位置保存数据 int IsNextPass(Maze* m, Position next, Position cur); // 保存最短的路径 void SaveShortPath(Stack* path, Stack* shortPath); // 走迷宫 void _GetMazeShortPath(Maze* m, Position cur, Position enter, Stack* path, Stack* shortPath); void PassMaze(Maze* m, Position enter, Stack* shortPath);#操作函数
//Stack.c #include"HardMaze.h" void StackInit(Stack* s) { s->top = 0; } void StackPush(Stack* s, DataType data) { if (s->top == MAX) { printf("栈已满！无法入栈元素\n"); return; } (s->top)++; s->stack[s->top] = data; } void StackPop(Stack *s) { if (s->top == 0) { printf("栈为空，无法出栈元素\n"); return; } (s->top)--; } DataType GetStackTop(Stack*s) { if (s->top == 0) { printf("栈为空，无法获取栈顶\n"); } return s->stack[s->top]; } int GetStackSize(Stack* s) { return s->top; } int StackEmpty(Stack *s) { if (s->top == 0) { return 1; } else { return 0; } }//Maze.c #include"HardMaze.h" void InitMaze(Maze * m, int map[ROW][COL]) { int i = 0; int j = 0; assert(m); for (i = 0; i < ROW; i++) { for (j = 0; j < COL; j++) { m->_map[i][j] = map[i][j]; } } } void PrintMaze(Maze* m) { assert(m); int i = 0; int j = 0; for (i = 0; i < ROW; i++) { for (j = 0; j < COL; j++) { printf(" %d ", m->_map[i][j]); } printf("\n"); } printf("\n"); } int IsValidEnter(Maze* m, Position enter) { assert(m); if (enter._x == ROW - 1 || enter._x == 0 || enter._y == COL - 1 || enter._y == 0) { return 1; } else return 0; } // pos 必须在地图中 pos位置如果是1 int IsPass(Maze* m, Position pos) { assert(m); if (pos._x >= ROW || pos._x < 0 || pos._y >= COL || pos._y >= COL) { return 0; } else if (m->_map[pos._x][pos._y] != 1) { return 0; } else return 1; } // 检测是否在出口的位置 int IsExit(Position pos, Position enter) { if ((pos._x == ROW - 1 || pos._x == 0 || pos._y == COL - 1 || pos._y == 0) && ((pos._x != enter._x) || (pos._y) != enter._y)) { return 1; } return 0; } int IsNextPass(Maze* m, Position next, Position cur) { if (m->_map[next._x][next._y] == 1) { return 1; } else if (m->_map[next._x][next._y] > m->_map[cur._x][cur._y]) { return 1; } return 0; } // 保存最短的路径 void SaveShortPath(Stack* path, Stack* shortPath) { int i = 0; if (StackEmpty(shortPath)) { for (i = 0; i < GetStackSize(path); i++) { StackPush(shortPath, path->stack[i]); } } else if (GetStackSize(path) < GetStackSize(shortPath)) { shortPath->top = 0; for (i = 0; i < GetStackSize(path); i++) { StackPush(shortPath, path->stack[i]); } } } void PassMaze(Maze* m, Position enter, Stack* shortPath) { Stack path; if (!IsValidEnter(m, enter)) { printf("迷宫的入口异常!!!\n"); return; } StackInit(&path); StackInit(shortPath); _GetMazeShortPath(m, enter, enter, &path, shortPath); } void _GetMazeShortPath(Maze* m, Position cur, Position enter, Stack* path, Stack* shortPath) { PrintMaze(m); m->_map[enter._x][enter._y] = 2; if (IsExit(cur, enter)) { SaveShortPath(path, shortPath); } StackPush(path, cur); Position next = cur; next._x -= 1; if (IsNextPass(m, next, cur)) { m->_map[next._x][next._y] = m->_map[cur._x][cur._y] + 1; _GetMazeShortPath(m, next, enter, path, shortPath); } next = cur; next._y -= 1; if (IsNextPass(m, next, cur)) { m->_map[next._x][next._y] = m->_map[cur._x][cur._y] + 1; _GetMazeShortPath(m, next, enter, path, shortPath); } next = cur; next._y += 1; if (IsNextPass(m, next, cur)) { m->_map[next._x][next._y] = m->_map[cur._x][cur._y] + 1; _GetMazeShortPath(m, next, enter, path, shortPath); } next = cur; next._x += 1; if (IsNextPass(m, next, cur)) { m->_map[next._x][next._y] = m->_map[cur._x][cur._y] + 1; _GetMazeShortPath(m, next, enter, path, shortPath); } StackPop(path); }#include"HardMaze.h" int main() { int map[ROW][COL] = { { 0,0,0,0,0,0 }, { 0,1,1,1,0,0 }, { 0,1,0,1,0,0 }, { 0,1,0,1,0,0 }, { 0,1,1,1,1,1 }, { 0,1,0,0,0,0 } }; Maze m; Stack shortPath; InitMaze(&m, map); Position enter; enter._x = 5; enter._y = 1; PrintMaze(&m); PassMaze(&m, enter, &shortPath); PrintMaze(&m); system("pause"); return 0; }
-
DQN实现走迷宫（tkinter编写环境）
2020-07-30 23:38:12Python实现走迷宫，迷宫环境可视化，代码参考莫烦python，可以直接运行，DQN网络使用tensorflow搭建，代码注释非常全，基本每一句都有，而且可以使用tensorboard查看日志，需要将log_out参数设置为true -
复杂迷宫问题的递归实现以及最短路径
2017-03-12 19:25:26复杂迷宫就是有多条通路的迷宫，而且要求解最短路的话就要用递归集合栈，用递归探测，寻找所有通路，用栈保存所走过的路径，具体方法为： （1）从当前点为起点探测由它开始能前进的点（这里的探测方向为上，有，左... -
迷宫问题（二）------复杂迷宫
2018-08-20 16:02:24"迷宫地图为\n-------------------\n" ); for (row = 0 ; row ; row++) { for (col = 0 ; col ; col++) { printf ( " %d " , maze-> map [row][col]); } printf ( "\n" ); } } //检测当前节点... -
复杂迷宫最短路径BFS总结
2020-03-02 21:24:02关于BFS的迷宫问题刷题刷到今天已经接近尾声了，对于比较复杂的迷宫问题特意选了两道比较有代表意义的例题写篇blog。两题的共通点就是走迷宫时的限制条件比较多，且用常规的vis二维数组标记无法解决重复遍历问题... -
RL之SARSA：利用强化学习之SARSA实现走迷宫—训练智能体走到迷宫(复杂陷阱迷宫)的宝藏位置
2018-10-22 11:46:50RL之SARSA：利用强化学习之SARSA实现走迷宫—训练智能体走到迷宫(复杂陷阱迷宫)的宝藏位置 目录 输出结果 设计思路 实现代码 测试记录全过程 输出结果 设计思路 实现代码 后期更新... -
数据结构---复杂迷宫求解（多路径带环）
2018-04-27 00:50:38上一篇博客我们提到了多出口迷宫的情况，但是在此基础上迷宫路径如果带环呢，如何解决？ 情况如下图： 可以看出，红色圈出来的部分形成了一个环。那如果我们还是采用上次的办法，看看能不能找出最短路径。 ... -
maze_solver:一个解决任意维数迷宫的程序-源码
2021-03-14 02:47:48maze_solver 一个解决任意维数迷宫的程序。 -
求复杂迷宫算法源码？
2015-01-04 17:15:18网上说"随机普里姆法"生成的迷宫比较复杂，有这种方法的源码吗？ 获取还有那种方法比较复杂些？ -
迷宫问题 很好用的 c++语言实现的 源代码
2009-05-20 08:37:49迷宫问题 很好用的 c++语言实现的 源代码 完全可以当做数据结构课设 -
习题：基于gym环境构建迷宫世界
2020-11-26 20:30:27迷宫世界效果演示环境测试代码测试代码的调用环境构建代码 效果演示 迷宫世界的最终演示效果如图。 黑色为墙不可通行，白色为道路可通行，黄色为出口。 环境测试代码 # 环境测试 import gym import random import ... -
强化学习极简例子--迷宫问题
2020-08-25 11:09:53迷宫 图1为一个小型迷宫，其中S为入口，−-−表示墙，+++表示出口。你说出口不在边缘？对的，就是这么任性。 图1. 迷宫 解法1: 单源最短路径 我们把迷宫的各个可达状态进行编号，获得图2. 图2. 编号后的迷宫 将各可... -
在迷宫环境中使用图像目标导向深度强化学习笔记（一）
2019-12-31 20:30:57在迷宫环境中，计算了机器人通过传过的action到达到哪个位置，实际上机器人确实已经在那个位置，但是环境没有更新，环境回落后于真实动作，这里我将更新动作加在了根据action移动之后，这样动作和环境就一同被更新了... -
Java 迷宫问题，复杂多条件迷宫问题
2016-09-18 21:35:27复杂迷宫问题，查找最短路径等。 基本步骤同上，需注意几个问题。 考察最短路径，不同路径之间可以有一段重复。不应该再使用全局的Boolean数组。可以考虑使用List.contains()方法避免有重复的点。 需要... -
强化学习之迷宫问题（MC, Sarsa, Q-learning实现）
2019-09-03 00:34:14通过简易迷宫问题，理解Monte-Carlo算法和Sarsa算法 3×33\times33×3的迷宫如下 可以通过每一步都随机地走，直到走到S8为止 这里主要写通过强化学习，找到最佳路线 MC算法： 首先定义一个policy，它是一个... -
经验分享：三套简单的迷宫地图生成方案
2019-04-30 01:24:05概述：文章基于一种基础的地图，来...其中不少方法来自于游戏界前辈，我根据自己的基础地图做了不少修正（毕竟迷宫和地图的形式多种多样，适合自己游戏的才是最好的）。 根据方案生成地图之后，还可以加上一些静... -
强化学习实战-使用Q-learning算法解决迷宫问题
2021-08-13 17:15:05Q-learning简介 Q-learning也是采用Q表格的方式存储Q值（状态动作价值），决策部分与Sarsa是一样的，采用ε-greedy方式增加探索。 Q-learning跟Sarsa不一样的地方是更新Q表格的方式。...迷宫问题 如下图所示， -
用DQN来走迷宫
2019-01-11 11:30:54这是用DQN来走迷宫的一个代码，可以看出DQN的完整用法。 -
利用DQN实现迷宫寻路
2019-02-03 14:48:28从q-learning到Deep-Q-Network 笔者在利用q-learning算法在Tkinter模块中进行自主寻路，由于网格维度过大而导致训练结果不理想，设置1500次迭代再反复试验后发现q-learning算法在面临大量学习数据集问题上表现出结果... -
实践Q Learning 实现走迷宫
2018-02-25 19:12:16一、环境构建搭建一个简单的迷宫环境，红色位置出发，黑色位置代表失败，黄色位置代表成功，让红色块慢慢通过不断探索学习的方式走到黄色的位置 #初始化迷宫 def _build_maze(self): h = self.MAZE_H*self.UNIT w... -
MATLAB强化学习入门——二、网格迷宫、Q-learning算法、Sarsa算法
2020-01-19 19:27:32本文为《MatLab强化学习入门》系列的第二篇。 在解决了单步决策问题以后，我们可以将多步问题分解为多个单步问题进行处理。使用ε-greedy等策略的基础在于对智能体当前...分析网格迷宫的编程实现，并对结果进行讨论。
收藏数
9,838
精华内容
3,935