真实算法优化求助

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1847 天前的主题，其中的信息可能已经有所发展或是发生改变。

https://item.taobao.com/item.htm?id=609807807418

这个拼图摆放方式如何用算法实现？

我真的买了，确实拼不出来。不是广告。

我尝试用写了个算法试了下，能跑，很慢。希望大哥们能教教如何优化

 package com.aiware.tianchi; public class puzzle11j { public static int[][][] j_Offset = { {{0, 4}, {0, 3}, {0, 2}, {0, 1}, {0, 0}, {1, 0}, {2, 0}, {2, 1}}, {{4, 2}, {3, 2}, {2, 2}, {1, 2}, {0, 2}, {0, 1}, {0, 0}, {1, 0}}, {{2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {1, 4}, {0, 4}, {0, 3}}, {{0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}, {4, 1}, {4, 2}, {3, 2}}, {{0, 1}, {0, 0}, {1, 0}, {2, 0}, {2, 1}, {2, 2}, {2, 3}, {2, 4}}, {{3, 0}, {4, 0}, {4, 1}, {4, 2}, {3, 2}, {2, 2}, {1, 2}, {0, 2}}, {{2, 3}, {2, 4}, {1, 4}, {0, 4}, {0, 3}, {0, 2}, {0, 1}, {0, 0}}, {{1, 2}, {0, 2}, {0, 1}, {0, 0}, {1, 0}, {2, 0}, {3, 0}, {4, 0}} }; public static int boardMaxLength = 10; public static void main(String[] args) { put(new int[boardMaxLength][boardMaxLength],0,0,11); } // public static int boardMaxLength = 6; // public static void main(String[] args) { // put(new int[boardMaxLength][boardMaxLength],0,0,4); // } public static boolean can_set(int[][] board, int x, int y, int offset_index) { for (final int[] offset : j_Offset[offset_index]) { int real_x_location = x + offset[0]; int real_y_location = y + offset[1]; //不出界 if (real_x_location > boardMaxLength-1) return false; if (real_y_location > boardMaxLength-1) return false; //没重叠 if (board[real_x_location][real_y_location] != 0) return false; } return true; } public static void put(int[][] board, int after_x,int after_y ,int left_j_num) { if (left_j_num == 0) { print_board(board); return; } if(after_x>(boardMaxLength-2) || after_y >(boardMaxLength-2)){ return; } for (int x = after_x; x < boardMaxLength-2; x++) { for (int y = after_y; y < boardMaxLength-2; y++) { board = test_j(board, left_j_num, x, y); } } for (int x = 0; x < after_x; x++) { for (int y = after_y; y < boardMaxLength-2; y++) { board = test_j(board, left_j_num, x, y); } } for (int x = after_x; x < boardMaxLength-2; x++) { for (int y = 0; y < after_y; y++) { board = test_j(board, left_j_num, x, y); } } } private static int[][] test_j(int[][] board, final int left_j_num, final int x, final int y) { for (int j_index = 0; j_index < j_Offset.length; j_index++) { if (can_set(board, x, y, j_index)) { board = mark_board(board, x, y, j_index, left_j_num); put(board, x+1,y+1,left_j_num - 1); board = clean_board(board,x,y,j_index); } } return board; } public static int[][] mark_board(int[][] board, int x, int y, int offset_index, int left_j) { for (final int[] offset : j_Offset[offset_index]) { int real_x_location = x + offset[0]; int real_y_location = y + offset[1]; board[real_x_location][real_y_location] = left_j; } return board; } public static int[][] clean_board(int[][] board, int x, int y, int offset_index) { return mark_board(board, x, y, offset_index, 0); } public static void print_board(int[][] board) { for (int x = 0; x < boardMaxLength; x++) { for (int y = 0; y < boardMaxLength; y++) { System.err.print((char) (board[x][y]+64)+" "); } System.err.println(""); } System.err.println(""); } }

把注释解开，即可测试，没毛病，就是慢。

算法逻辑是这样的：

把 j 的形状枚举出来，包含镜像，一共 8 个
一步一步试验，能不能放进去。
j 的数量越来越少，0 的时候，直接输出对应的图象

可能算是广度优先算法，确实想不到其他的剪枝技巧

第 1 条附言 2020-09-23 21:21:58 +08:00

代码放着跑了 2 天多，终于跑出结果了,append 一下，其实不止这些，输出结果还有很多，但是都差不多。看来剪枝的方式也就是想办法去除重复数据可以考虑一下。其他的剪枝方式是明显有问题的都跳过一下。确实没啥好办法

```

K @ @ @ C C C C C G
K B B B B B E @ C G
K A A A @ B E C C G
K A K A B B E G @ G
K K K A E @ E G G G
J J J A E E E I I I
J @ J A @ D D I @ I
J F F F F F D H H I
J F D D D D D @ H I
J F F @ H H H H H I

K @ @ @ D D D D D G
K C C C C C B @ D G
K A A A @ C B D D G
K A K A C C B G @ G
K K K A B @ B G G G
J J J A B B B I I I
J @ J A @ E E I @ I
J F F F F F E H H I
J F E E E E E @ H I
J F F @ H H H H H I

K @ @ @ D D D D D G
K C C C C C A @ D G
K B B B @ C A D D G
K B K B C C A G @ G
K K K B A @ A G G G
J J J B A A A I I I
J @ J B @ E E I @ I
J F F F F F E H H I
J F E E E E E @ H I
J F F @ H H H H H I

K @ @ @ B B B B B G
K A A A A A D @ B G
K C C C @ A D B B G
K C K C A A D G @ G
K K K C D @ D G G G
J J J C D D D I I I
J @ J C @ E E I @ I
J F F F F F E H H I
J F E E E E E @ H I
J F F @ H H H H H I

```

5 条回复 2020-09-22 13:11:32 +08:00