首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >一种清洁机器人,使用尽可能少的移动来清洁5x5网格中的脏单元

一种清洁机器人,使用尽可能少的移动来清洁5x5网格中的脏单元
EN

Stack Overflow用户
提问于 2019-05-28 04:33:10
回答 1查看 0关注 0票数 0

我一直在通过HackerRank的人工智能课程,但我已经为一个名为BotClean的挑战编写了一个低效的蛮力解决方案。

面临的挑战是在尽可能少的移动中以5乘5的网格为每个脏单元提供一个清洁机器人。

输入格式 第一行包含两个空格分隔的整数,表示机器人的当前位置。董事会使用Matrix Convention编制索引。跟随表示网格的5行。网格中的每个单元格由以下3个字符中的任何一个表示:b(ascii值98)表示机器人的当前位置,d(ascii值100)表示脏单元格,-(ascii值45)表示网格中的干净单元格。 注意如果机器人在脏单元格上,则单元格仍然d在其上。 输出格式 输出是机器人在当前步骤中采取的动作,它可以是4个方向中的一个移动或清理它当前所在的单元格。有效的输出字符串是LEFTRIGHTUPDOWNCLEAN。如果机器人到达脏电池,输出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);
    }
}
EN

回答 1

Stack Overflow用户

发布于 2019-05-28 14:17:50

您所拥有的是旅行商问题的变体。值得注意的变化是您的机器人不需要返回其起始位置,您使用曼哈顿距离,并且您有一个矩阵而不是节点。

目前,您的算法会清除污垢,污垢首先按行排序,然后按列排序。在这个示例中,您可以看到为什么这不是最优的:

b----
d---d
d----

这里机器人将遍历板的宽度两次,而只有一次遍历是最佳的。

为了解决这个问题,我首先将污垢块表示为位置列表,而不是矩阵; 像这样:

List Index | x | y
-----------+---+---
0          | 0 | 1
1          | 5 | 2
...        | . | .

除了第一个节点(该节点应该是机器人的位置)之外,此列表的顺序无关紧要。

通过这种新的表示,您可以开始使用TSP。

从机器人的初始节点开始,迭代剩余节点的每个排列。在每个排列中:

  1. 按顺序迭代其中的节点
  2. 计算从当前节点到下一个节点的曼哈顿距离,直到所有节点都已计入
  3. 存储距离的总和作为该排列的成本

要获得最佳解决方案,请选择具有最短距离总和的置换。这将是您的机器人将采取的路径。

要将解决方案转换为一系列方向,请(LEFT,RIGHT,UP,DOWN,CLEAN)迭代解决方案,向着方向移动以接近下一个节点(类似于您已在嵌套for循环中实现的那个),并在到达时清理。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/-100006833

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档