骑士在棋盘上的最短路径

Question

我一直在为即将到来的编程竞赛练习,我偶然发现了一个我完全不知所措的问题.然而,我觉得这是一个我现在应该学习的概念,而不是交叉指责它永远不会出现.

基本上,它涉及棋盘上的骑士棋子.您将获得两个输入:起始位置和结束位置.目标是计算并打印骑士可以到达目标位置的最短路径.

我从来没有处理过最短路径的事情,我甚至不知道从哪里开始.我采用什么逻辑来解决这个问题？

PS如果它有任何相关性,他们希望你补充骑士的正常动作,同时允许它移动到由骑士可以做的(潜在的)八个动作所形成的方形的四个角,因为方形的中心是骑士的位置.

Answer 1

编辑: 看到西蒙的答案,他修复了这里提出的公式.

实际上有一个O(1)公式

这是我用它来形象化的图像(骑士可以在^第 N ^步移动时使用相同颜色绘制的方块).

你能注意到这里的模式吗？

虽然我们可以看到模式,但是很难找到f( x , y )返回从正方形( 0 , 0 )到正方形所需的移动次数的函数( x , y )

但这里的公式是有效的 0 <= y <= x

int f( int x , int y )
{
    int delta = x - y;

    if( y > delta )
        return 2 * ( ( y - delta ) / 3 ) + delta;
    else
        return delta - 2 * ( ( delta - y ) / 4 );
}

注意:这个问题在SACO 2007第1天被问到,
解决方案就在这里

Answer 2

这是一个正确的O(1)解决方案,但是对于骑士只像国际象棋骑士一样移动并且在无限棋盘上的情况:

https://jsfiddle.net/graemian/5qgvr1ba/11/

找到这个的关键是要注意绘制板时出现的模式.在下图中,正方形中的数字是到达该正方形所需的最小移动次数(您可以使用广度优先搜索来查找):

因为解决方案在轴和对角线上是对称的,所以我只绘制了x> = 0和y> = x的情况.

左下方的块是起始位置,块中的数字表示到达这些块的最小移动次数.

有三种模式需要注意:

• 递增的蓝色垂直组4
• "主要"红色对角线(它们从左上角到右下角,像反斜杠一样)
• "次要"绿色对角线(与红色相同的方向)

(确保你看到两组对角线都是从左上角到右下角.它们有一个恒定的移动计数.左下角的右上对角线要复杂得多.)

您可以为每个派生公式.黄色块是特殊情况.所以解决方案变成:

function getMoveCountO1(x, y) {

    var newXY = simplifyBySymmetry(x, y);

    x = newXY.x;
    y = newXY.y;

    var specialMoveCount = getSpecialCaseMoveCount(x ,y);

    if (specialMoveCount !== undefined)
        return specialMoveCount;

    else if (isVerticalCase(x, y))
        return getVerticalCaseMoveCount(x ,y);

    else if (isPrimaryDiagonalCase(x, y))
        return getPrimaryDiagonalCaseMoveCount(x ,y);

    else if (isSecondaryDiagonalCase(x, y))
        return getSecondaryDiagonalCaseMoveCount(x ,y);

}

最困难的是垂直群体:

function isVerticalCase(x, y) {

    return y >= 2 * x;

}

function getVerticalCaseMoveCount(x, y) {

    var normalizedHeight = getNormalizedHeightForVerticalGroupCase(x, y);

    var groupIndex = Math.floor( normalizedHeight / 4);

    var groupStartMoveCount = groupIndex * 2 + x;

    return groupStartMoveCount + getIndexInVerticalGroup(x, y);

}

function getIndexInVerticalGroup(x, y) {

    return getNormalizedHeightForVerticalGroupCase(x, y) % 4;

}

function getYOffsetForVerticalGroupCase(x) {

    return x * 2;

}

function getNormalizedHeightForVerticalGroupCase(x, y) {

    return y - getYOffsetForVerticalGroupCase(x);

}

看其他案件的小提琴.

也许我错过了更简单或更优雅的模式？如果是这样,我很乐意看到他们.特别是,我注意到蓝色垂直情况下的一些对角线图案,但我没有探索过它们.无论如何,该解决方案仍然满足O(1)约束.

Answer 3

这里有一个图表,其中所有可用的移动都是连接的(值= 1),并且不可用的移动是断开的(值= 0),稀疏矩阵将是这样的:

(a1,b3)=1,
(a1,c2)=1,
  .....

使用http://en.wikipedia.org/wiki/Dijkstra's_algorithm可以找到图中两点的最短路径

来自维基百科的伪代码页面:

function Dijkstra(Graph, source):
   for each vertex v in Graph:           // Initializations
       dist[v] := infinity               // Unknown distance function from source to v
       previous[v] := undefined          // Previous node in optimal path from source
   dist[source] := 0                     // Distance from source to source
   Q := the set of all nodes in Graph
   // All nodes in the graph are unoptimized - thus are in Q
   while Q is not empty:                 // The main loop
       u := vertex in Q with smallest dist[]
       if dist[u] = infinity:
          break                         // all remaining vertices are inaccessible from source
       remove u from Q
       for each neighbor v of u:         // where v has not yet been removed from Q.
           alt := dist[u] + dist_between(u, v) 
           if alt < dist[v]:             // Relax (u,v,a)
               dist[v] := alt
               previous[v] := u
   return dist[]

编辑:

1. 作为白痴,说使用 http://en.wikipedia.org/wiki/A*_algorithm 可以更快.
2. 最快的方法是预先计算所有距离并将其保存为8x8全矩阵.好吧,我会称之为作弊,只会因为问题很小而起作用.但有时竞争会检查你的程序运行速度.
3. 重点是,如果您正在为编程竞赛做准备,您必须了解包括Dijkstra在内的常用算法.一个很好的起点是阅读 Introduction to AlgorithmsISBN 0-262-03384-4.或者您可以尝试维基百科,http://en.wikipedia.org/wiki/List_of_algorithms

Answer 4

我最近遇到的非常有趣的问题.在寻找一些解决方案后,我试图恢复O(1) time and space complexity在SACO 2007第1天 解决方案中给出的分析公式().

首先,我想欣赏Graeme Pyle的非常好的可视化,这有助于我修复配方.

由于某种原因(可能是为了简化或美观或只是一个错误),他们将minus标志移入floor操作员,因此他们的公式错误floor(-a) != -floor(a) for any a.

这是正确的分析公式:

var delta = x-y;
if (y > delta) {
    return delta - 2*Math.floor((delta-y)/3);
} else {
    return delta - 2*Math.floor((delta-y)/4);
}

该公式适用于所有(x,y)对(在应用轴和对角线对称之后)除了(1,0)和(2,2)角落情况,这些情况不满足模式并在下面的代码段中进行硬编码:

function distance(x,y){
     // axes symmetry 
     x = Math.abs(x);
     y = Math.abs(y);
     // diagonal symmetry 
     if (x < y) {
        t = x;x = y; y = t;
     }
     // 2 corner cases
     if(x==1 && y == 0){
        return 3;
     }
     if(x==2 && y == 2){
        return 4;
     }
    
    // main formula
    var delta = x-y;
		if(y>delta){
  		return delta - 2*Math.floor((delta-y)/3);
  	}
  	else{
  		return delta - 2*Math.floor((delta-y)/4);
  	}
}


$body = $("body");
var html = "";
for (var y = 20; y >= 0; y--){
	html += '<tr>';
	for (var x = 0; x <= 20; x++){
  	html += '<td style="width:20px; border: 1px solid #cecece" id="'+x+'_'+y+'">'+distance(x,y)+'</td>';
  }
  html += '</tr>';
}

html = '<table>'+html+'</table>';
$body.append(html);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>

注意:jQuery仅用于说明,代码见distance功能.

Answer 5

是的,Dijkstra和BFS将为您提供答案,但我认为这个问题的国际象棋语境提供的知识可以产生比通用最短路径算法快得多的解决方案,尤其是在无限棋盘上.

为简单起见,我们将棋盘描述为(x,y)平面.目标是仅使用候选步骤(+ -1,+ -2),(+ -2,+ -1)和(+ -2)找到从(x0,y0)到(x1,y1)的最短路径,+ -2),如问题PS中所述

这是新观察:绘制一个带角(x-4,y-4),(x-4,y + 4),(x + 4,y-4),(x + 4,y + 4)的正方形.这个集合(称之为S4)包含32个点.从这32个点中的任何一个到(x,y)的最短路径只需要两个动作.

从集合S3中的任何24个点(类似地定义)到(x,y)的最短路径需要至少两个移动.

因此,如果| x1-x0 |> 4或| y1-y0 |> 4,从(x0,y0)到(x1,y1)的最短路径正好比从(x0,y0)到(x0,y0)的最短路径大两个移动S4.后一个问题可以通过简单的迭代快速解决.

设N = max(| x1-x0 |,| y1-y0 |).如果N> = 4,则从(x0,y0)到(x1,y1)的最短路径具有ceil(N/2)步长.

Answer 6

上面的O(1)回答[ 由MustafaSerdarŞanlı撰写的/sf/answers/614501471/ ]并没有真正起作用.(检查(1,1)或(3,2)或(4,4),除了(1,0)或(2,2)的明显边缘情况外.

下面是一个更加丑陋的解决方案(python),它确实有效(添加了"测试"):

def solve(x,y):
        x = abs(x)
        y = abs(y)
        if y > x:
            temp=y
            y=x
            x=temp  
        if (x==2 and y==2):
            return 4
        if (x==1 and y==0):
            return 3

    if(y == 0 or float(y) / float(x) <= 0.5):
        xClass = x % 4
        if (xClass == 0):
            initX = x/2
        elif(xClass == 1):
            initX = 1 + (x/2)
        elif(xClass == 2):
            initX = 1 + (x/2)
        else:
            initX = 1 + ((x+1)/2)

        if (xClass > 1):
            return initX - (y%2)
        else:
            return initX + (y%2)
    else:
        diagonal = x - ((x-y)/2)
        if((x-y)%2 == 0):
            if (diagonal % 3 == 0):
                return (diagonal/3)*2
            if (diagonal % 3 == 1):
                return ((diagonal/3)*2)+2
            else:
                return ((diagonal/3)*2)+2
        else:
            return ((diagonal/3)*2)+1


def test():
    real=[
    [0,3,2,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,1,2,3,4,3,4,5,6,5,6,7,8],
    [2,1,4,3,2,3,4,5,4,5,6,7,6,7],
    [3,2,3,2,3,4,3,4,5,6,5,6,7,8],
    [2,3,2,3,4,3,4,5,4,5,6,7,6,7],
    [3,4,3,4,3,4,5,4,5,6,5,6,7,8],
    [4,3,4,3,4,5,4,5,6,5,6,7,6,7],
    [5,4,5,4,5,4,5,6,5,6,7,6,7,8],
    [4,5,4,5,4,5,6,5,6,7,6,7,8,7],
    [5,6,5,6,5,6,5,6,7,6,7,8,7,8],
    [6,5,6,5,6,5,6,7,6,7,8,7,8,9],
    [7,6,7,6,7,6,7,6,7,8,7,8,9,8]]

    for x in range(12):
        for y in range(12):
            res = solve(x,y)
            if res!= real[x][y]:
                print (x, y), "failed, and returned", res, "rather than", real[x][y]
            else:
               print (x, y), "worked. Cool!"

test()

Answer 7

您需要做的是将骑士的可能移动视为图形,其中棋盘上的每个位置都是一个节点,并且可能移动到其他位置作为边缘.不需要dijkstra的算法,因为每个边缘都具有相同的权重或距离(它们都很容易或很短).您可以从起点开始进行BFS搜索,直到到达结束位置.

Answer 8

Python中第一原理的解决方案

我第一次在Codility测试中遇到过这个问题.他们给了我30分钟的时间来解决它 - 我花了相当长的时间来达到这个结果!问题在于:骑士从0,0到x,需要多少动作才能使用合法的骑士动作.x和y或多或少没有界限(所以我们这里没有谈论一个简单的8x8棋盘).

他们想要一个O(1)解决方案.我想要一个解决方案,该程序明确地解决了问题(即我想要的东西比Graeme的模式更明显 - 模式有习惯在你不看的地方分解),我真的不想依赖于毫无保证的公式,就像穆斯塔法的解决方案一样

所以,这是我的解决方案,它的价值.像其他人一样开始,注意解决方案是关于轴和对角线的对称,所以我们只需求解0> = y> = x.为了简化解释(和代码),我将解决问题:骑士从x,y开始,目标是0,0.

让我们假设我们将问题缩小到原点附近.我们将在适当的时候了解'vicinty'实际意味着什么,但是现在,让我们在一个备忘单中写下一些解决方案(来自左下角):

2 1 4 3
3 2 1 2
0 3 2 3

因此,给定网格上的x,y,我们可以读取到原点的移动次数.

如果我们已经开始在网格之外,我们必须回到它的方式.我们引入'中线',即由y = x/2表示的线.使用一系列8点钟的移动(即:( - 2,-1)移动),该行上x,y处的任何骑士都可以回到棋盘.如果x,y位于中线之上,那么我们将需要连续的8点和7点移动,如果它位于中线下方,我们需要连续8点和10点'时钟移动.这里有两点需要注意:

• 这些序列是可证明最短的路径.(要我证明一下,还是很明显？)
• 我们只关心这些举动的数量.我们可以按任何顺序混合和匹配移动.

那么,让我们来看看上面的中线动作.我们声称的是:

• (dx; dy)=(2,1; 1,2)(n8; n7)(矩阵表示法,没有数学排版 - 列向量(dx; dy)等于方阵矩阵乘以列向量(n8; n7) - 8点移动的数量和7点移动的数量),类似地;

• (dx; dy)=(2,2; 1,-1)(n8; n10)

我声称dx,dy将大致为(x,y),因此(x-dx,y-dy)将位于原点附近(无论'附近'是什么).

代码中计算这些术语的两行是这些术语的解决方案,但它们被选中具有一些有用的属性:

• 上 - 中线公式将(x,y)移动到(0,0),(1,1)或(2,2)中的一个.
• 下中线公式将(x,y)移动到(0,0),(1,0),(2,0)或(1,1)中的一个.

(你想要证明这些吗？)所以,骑士的距离将是n7,n8,n10和cheatsheet [x-dx,y-dy]的总和,我们的cheatsheet减少到这个:

. . 4
. 2 .
0 3 2

现在,这不是故事的结尾.看看底行的3.我们能够实现这一目标的唯一方法是:

• 我们从那里开始,或者
• 我们通过一系列8点和10点的移动移动到那里.但是如果最后一步是8点钟(它有权成为,因为我们可以按任何顺序进行动作),那么我们必须通过(3,1),其距离实际为2(你可以从原始的备忘单看).所以我们应该做的是回溯一个8点的移动,总共节省了两个动作.

对于右上方的4,有一个类似的优化.除了从那里开始,到达那个的唯一方法是从(4,3)8点钟移动.这不是在cheatsheet上,但如果它在那里,它的距离将是3,因为我们可以将7点钟改为(3,1),而距离仅为2.因此,我们应该回溯一个8点钟移动,然后向前走7点钟.

因此,我们需要在备忘单中再添加一个数字:

. . 4
. 2 . 2
0 3 2

(注意:从(0,1)和(0,2)有一整套反向跟踪优化,但由于求解器永远不会把我们带到那里,所以我们不需要担心它们.)

那么,这里有一些Python代码来评估这个:

def knightDistance (x, y):
    # normalise the coordinates
    x, y = abs(x), abs(y)
    if (x<y): x, y = y, x
    # now 0 <= y <= x

    # n8 means (-2,-1) (8 o'clock), n7 means (-1,-2) (7 o'clock), n10 means (-2,+1) (10 o'clock)
    if (x>2*y):
        # we're below the midline.  Using 8- & 10-o'clock moves
        n7, n8, n10 = 0,  (x + 2*y)//4,  (x - 2*y + 1)//4
    else:
        # we're above the midline.  Using 7- and 8-o'clock moves
        n7, n8, n10 = (2*y - x)//3, (2*x - y)//3,  0
    x -= 2*n8 + n7 + 2*n10
    y -= n8 + 2*n7 - n10
    # now 0<=x<=2, and y <= x.  Also (x,y) != (2,1)

    # Try to optimise the paths.
    if (x, y)==(1, 0): # hit the  3.  Did we need to?
        if (n8>0): # could have passed through the 2 at 3,1.  Back-up
            x, y = 3, 1; n8-=1;
    if (x, y)==(2, 2): # hit the 4.  Did we need to?
        if (n8>0): # could have passed through a 3 at 4,3.  Back-up, and take 7 o'clock to 2 at 3,1
            x, y = 3, 1; n8-=1; n7+=1

    # Almost there.  Now look up the final leg
    cheatsheet = [[0, 3, 2], [2, None, 2], [4]]
    return n7 + n8 + n10 + cheatsheet [y][x-y]

顺便提一下,如果你想知道一个实际路线,那么这个算法也提供了这个:它只是一连串的n7 7点移动,接着是(或穿插)n8 8点移动,n10 10-时间移动,无论什么舞蹈都是由cheatsheet决定的(它本身可以放在一张备忘单中).

现在:如何证明这是正确的.仅仅将这些结果与正确答案表进行比较是不够的,因为问题本身是无限的.但是我们可以说,如果骑士的方形s的距离是d,那么如果{m}是从s开始的合法移动的集合,那么骑士的(s + m)距离必须是d-1或d + 1对于所有米.(你需要证明吗？)此外,必须至少有一个这样的方形,其距离为d-1,除非s是原点.因此,我们可以通过显示每个方格的此属性来证明正确性.从而:

def validate (n):

    def isSquareReasonable (x, y):
        d, downhills = knightDistance (x, y), 0
        moves = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1,  2)]
        for dx, dy in moves:
            dd = knightDistance (x+dx,  y+dy)
            if (dd == d+1): pass
            elif (dd== d-1): downhills += 1
            else: return False;
        return (downhills>0) or (d==0)

    for x in range (0,  n+1):
        for y in range (0,  n+1):
            if not isSquareReasonable (x,  y): raise RuntimeError ("Validation failed")

或者,我们可以通过追逐从下坡到原点的路线来证明任何一个方格的正确性.首先,如上所述检查s的合理性,然后选择任何s + m,使得距离(s + m)== d-1.重复,直到我们到达原点.

Howzat？