如何利用人工智能找到点间最短路径？

Question

我试图通过尝试黑客等级上的问题来提高我的人工智能知识。

问题之一是：

桃公主被困在方格的四个角落之一。您位于网格的中心，可以在任意四个方向上一步一步地移动。你能救公主吗？

详细信息是这里。

我需要一个提示才能系统地解决这个问题。这是最短路线问题吗？或者人工智能的哪些算法/概念可以用来解决这个问题？

谢谢。

Answer 1

这是最短路径问题，其中节点是网格中的单元，边缘可以从单元格移动到单元格。

最简单的解决方案是使用BFS (因为图是未加权的)。一个改进是使用双向BFS。

一个面向人工智能的改进是使用诸如*这样的知情算法。你需要一个容许启发式函数来使用它，你能想到任何吗？(有一个经典的名著，但我会让你自己想办法的)。

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

1. 加载输入数据，从网格大小开始。
2. 接受与网格大小相对应的输入行。
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))