如何使用AI找到点之间的最短路线？

Question

我正在尝试通过 hackerrank 上的问题来提高我的 AI 知识。

其中一个问题是：

Princess Peach is trapped in one of the four corners of a square grid. You are in the center of the grid and can move one step at a time in any of the four directions. Can you rescue the princess?

详情为here。

我需要一个提示来系统地解决这个问题。是最短路线问题吗？或者用哪个algorithms/concepts的AI可以解决这个问题？

谢谢。

Answer 1

这是 shortest path problem，其中节点是网格中的单元格，边可能从一个单元格移动到另一个单元格。

最简单的解决方案是使用 BFS (since the graph is unweighted). An improvement is using a bi-directional BFS。

面向AI的改进是使用知情算法，例如A*. You are going to need an admissible heuristic函数来使用它，你能想到吗？（有一个经典的广为人知的，但我会让你自己理解）。

Answer 2

有点晚了，但出于好奇，我在 php 中尝试了这个方法，首先获取公主的位置，然后是马里奥的位置，然后通过循环移动马里奥。这赢得了比赛，但这不是最快的方式，尤其是当网格很大时。

        function displayPathtoPrincess($m, $grid) {
            //get mario and princesses locations
            $gridstring = implode('', $grid);
            $p = strpos($gridstring, 'p') + 1;
            $m = strpos($gridstring, 'm') + 1;

            $positioncount = 0;

            //get marios and princess xy location
            for ($x = 0; $x < count($grid); $x ++) {
                for ($y = 0; $y < count($grid); $y ++) {
                    $positioncount ++;
                    if ($positioncount == $m) {
                        $mario[0] = $x;
                        $mario[1] = $y;
                    }

                    if ($positioncount == $p) {
                        $princess[0] = $x;
                        $princess[1] = $y;
                    }

                    if (isset($mario) > 0 && isset($princess) > 0)
                        break;
                }
            }


        //Find princess
            $moves = '';
            for ($x = 0; $x < count($grid); $x ++) {
                for ($y = 0; $y < count($grid); $y ++) {
                    //if at marios location ...

                    if ($mario[0] == $x && $mario[1] == $y) {
                        $updownmove = $princess[0] - $mario[0];

                        if ($updownmove < 0) {
                            for (; $updownmove < 0; $updownmove++) {
                                $newposition = $mario[0] - 1;
                                if ($newposition >= 0) {
                                    $mario[0] = $newposition;

                                    if (trim($moves) != '') {
                                        $moves .= "\n";
                                    }
                                    $moves .= "UP";
                                }
                            }
                        } else {
                            for (; $updownmove > 0; $updownmove--) {
                                $mario[0] = $mario[0] + 1;
                                if (trim($moves) != '') {
                                    $moves .= "\n";
                                }
                                $moves .= "DOWN";
                            }
                        }

                        $rightleftmove = $princess[1] - $mario[1];
                        if ($rightleftmove < 0) {
                            for (; $rightleftmove < 0; $rightleftmove++) {
                                $newposition = $mario[1] - 1;
                                if ($newposition >= 0) {
                                    $mario[1] = $newposition;

                                    if (trim($moves) != '') {
                                        $moves .= "\n";
                                    }
                                    $moves .= "LEFT";
                                }
                            }
                        } else {
                            for (; $rightleftmove > 0; $rightleftmove--) {
                                $mario[1] = $mario[1] + 1;
                                if (trim($moves) != '') {
                                    $moves .= "\n";
                                }
                                $moves .= "RIGHT";
                            }
                        }
                    }

                    if (isfound($mario, $princess)) {
                        echo $moves;
                        return;
                    }
                }
            }
        }

        function isfound($mario, $princess) {
            if (count($mario) == 0)
                return false;
            if (($mario[0] == $princess[0]) && ($mario[1] == $princess[1])) {
                return true;
            } else {
                return false;
            }
        }

Answer 3

加载输入数据，从网格大小开始。
接受与网格大小对应的输入行。
既然你知道格子是正方形，那么检查角并根据公主所在的角向对角线移动。

7行解决python：

gridsize  = int(input('Enter number of rows: '))
grid      = [ input('Enter row: ') for r in range(gridsize) ]
move_dist = (gridsize-1)//2
if   grid[ 0][ 0] == 'p': print('\n'.join([   'UP\nLEFT'] * move_dist))
elif grid[ 0][-1] == 'p': print('\n'.join([  'UP\nRIGHT'] * move_dist))
elif grid[-1][ 0] == 'p': print('\n'.join([ 'DOWN\nLEFT'] * move_dist))
elif grid[-1][-1] == 'p': print('\n'.join(['DOWN\nRIGHT'] * move_dist))

如何使用AI找到点之间的最短路线？

How to find shortest route between points using AI?

algorithm

artificial-intelligence