我一直在通过HackerRank的人工智能课程,但我已经为一个名为BotClean的挑战编写了一个低效的蛮力解决方案。
面临的挑战是在尽可能少的移动中以5乘5的网格为每个脏单元提供一个清洁机器人。
输入格式 第一行包含两个空格分隔的整数,表示机器人的当前位置。董事会使用Matrix Convention编制索引。跟随表示网格的5行。网格中的每个单元格由以下3个字符中的任何一个表示:
b
(ascii值98)表示机器人的当前位置,d
(ascii值100)表示脏单元格,-
(ascii值45)表示网格中的干净单元格。 注意如果机器人在脏单元格上,则单元格仍然d
在其上。 输出格式 输出是机器人在当前步骤中采取的动作,它可以是4个方向中的一个移动或清理它当前所在的单元格。有效的输出字符串是LEFT
,RIGHT
,UP
和DOWN
或CLEAN
。如果机器人到达脏电池,输出CLEAN
以清洁脏电池。重复此过程,直到清除网格上的所有单元格。 样本输入0 0 b---d -d--d --dd- --d-- ----d
样本输出RIGHT
程序运行多长时间无关紧要,只需要机器人采取的移动次数尽可能小。我创建了一个蛮力算法,使用两个for循环检查每个单元格是否为脏,但是这会使用许多不必要的移动。有什么方法可以改进我的算法,以便将少量的动作写入控制台?我想减少机器人访问每个脏单元所需的移动次数。
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
static void next_move(int posr, int posc, String [] board)
{
if (board[posr][posc] == 'd')
{
Console.Write("CLEAN\n");
return;
}
for(int i = 0; i < board.Length; i++)
{
for (int j = 0; j < board.Length; j++)
{
if (board[i][j] == 'd')
{
if (posr < i) // If the bot's row is higher than the row of the dirt
{
Console.Write("DOWN\n");
}
else if (posr > i) // If the bot's row is lower than the row of the dirt
{
Console.Write("UP\n");
}
else if (posr == i && posc < j) // If the bot's column is to the left of the column of the dirt
{
Console.Write("RIGHT\n");
}
else if (posr == i && posc > j) // If the bot's column is to the right of the column of the dirt
{
Console.Write("LEFT\n");
}
else
{
Console.Write("CLEAN\n"); // If the bot moves onto a dirty square, it needs to clean it
}
return; // Escapes the for loops
}
}
}
}
static void Main(String[] args)
{
String temp = Console.ReadLine();
String[] position = temp.Split(' ');
int[] pos = new int[2];
String[] board = new String[5];
for(int i=0;i<5;i++)
{
board[i] = Console.ReadLine();
}
for(int i=0;i<2;i++) pos[i] = Convert.ToInt32(position[i]);
next_move(pos[0], pos[1], board);
}
}
发布于 2019-05-28 14:17:50
您所拥有的是旅行商问题的变体。值得注意的变化是您的机器人不需要返回其起始位置,您使用曼哈顿距离,并且您有一个矩阵而不是节点。
目前,您的算法会清除污垢,污垢首先按行排序,然后按列排序。在这个示例中,您可以看到为什么这不是最优的:
b----
d---d
d----
这里机器人将遍历板的宽度两次,而只有一次遍历是最佳的。
为了解决这个问题,我首先将污垢块表示为位置列表,而不是矩阵; 像这样:
List Index | x | y
-----------+---+---
0 | 0 | 1
1 | 5 | 2
... | . | .
除了第一个节点(该节点应该是机器人的位置)之外,此列表的顺序无关紧要。
通过这种新的表示,您可以开始使用TSP。
从机器人的初始节点开始,迭代剩余节点的每个排列。在每个排列中:
要获得最佳解决方案,请选择具有最短距离总和的置换。这将是您的机器人将采取的路径。
要将解决方案转换为一系列方向,请(LEFT,RIGHT,UP,DOWN,CLEAN)
迭代解决方案,向着方向移动以接近下一个节点(类似于您已在嵌套for循环中实现的那个),并在到达时清理。
https://stackoverflow.com/questions/-100006833
复制相似问题