php Peg难题解决程序上的超时
第一次来这里。
我正在使用递归的方法开发一个php解决程序。对于小型和简单的板，我得到了想要的结果(脚本正确地解决了这个难题)，但是对于更大的和完整的板(即，除了一个占用的插槽)，我得到了一个php超时。我需要让它与7x7板一起工作，布局如下：
x x 1 1 1 x x
x x 1 1 1 x x
1 1 1 1 1 1 1
1 1 1 0 1 1 1
1 1 1 1 1 1 1
x x 1 1 1 x x
x x 1 1 1 x x在'x‘是不可用的地方，'1’是一个带钉的插槽，'0‘是一个自由插槽。
板由7x7数组(数组的数组)表示。我一次遍历一个键，执行以下检查：
这个键的值是'1‘吗？如果是，下面的键的值也是'1‘和下面的'0’吗？(这意味着有一个挂钩，并有一个空间来移动第一个)。如果是，那么我创建一个板的副本并应用这些更改，并将其重新发送到函数中。如果没有，我检查另一个方向(当前检查顺序是:右、左、上、下)。
当脚本无法从该位置找到有效路径时，递归结束。然后，我做了一个检查，看看是否只剩下一个钉住(这意味着董事会已经解决)，或是否有钉住(这将意味着董事会没有解决)。在后一种情况下，整个路径应该被抛弃。
我会复制和粘贴我的代码，但由于它仍然有点混乱，我更愿意解释它。
我尝试了Rodolphe Courtier的算法(这里)，得到了同样的结果。
提前感谢！
编辑： Ok，到目前为止，使DFS非递归并没有多大帮助(仍然需要很多步骤)。所以，现在我正在考虑检查板上的模式，这些模式首先会产生一个无法解决的谜题，如果是这样的话，我指示脚本从一开始就不要费心地遍历它。和以前一样，我会发布我的发现。
回答 2
Stack Overflow用户
发布于 2011-06-18 02:58:37
我以前曾用c++和c#写过这篇文章。我可以告诉您，7x7数组不是最好的。考虑一个标准的深度优先搜索算法和一个板表示为位板。我可能可以张贴一个完整的解决方案在c，但为一个不同的董事会，如果你愿意。
此外，考虑到该解决方案需要深度优先搜索，您真的无法绕过递归。我的第一次尝试做了一些类似你正在做的事情，而且很慢。位板实现在几秒钟内完成，而不是分钟。
编辑：
这是我的解决方案，一个15钉板，是一个三角形的形状。启动板上除了三角形的顶部外，所有的挂钩都已就位，而获胜的解决方案被定义为最后一次挂钩，最终位于顶部位置。该算法应该对您同样有效，除非您需要重新定义哪些移动可用，哪些移动是合法的。
基本说明:董事会的安排如下：
p1
p2 p3
p4 p5 p6
p7 p8 p9 pa
pb pc pd pe pf每个位置映射到16位int上的一个位。除了p1以外，板上的所有位数都开始了。“移动”是由三位组成的三重奏。例如，(p1，p2，p4)是一个可能的举动。如果p1、p2位被设置、p4是清除的、OR p2、p4被设置、p1是清除的，则移动是“合法的”。所有移动都有查找表，以及合法的移动定义。
为了进行深度优先搜索，我们需要：
- 结束状态(一位:我将其定义为仅p1 on，这是微不足道的)。
- 做和撤销移动(对候选人移动的当前板，同样琐碎)
- 生成候选移动集(同样，一些二进制xor/和操作。唯一复杂的部分，如果需要的话，我可以稍后再详细说明.)
守则：
#include <vector>
#include <iostream>
using namespace std;
typedef short state_t;
struct Move {
short move;
const char * desc;
};
typedef Move move_t;
struct Options {
short moves[4];
int size;
};
// name the bits
# define P1 1
# define P2 1 << 1
# define P3 1 << 2
# define P4 1 << 3
# define P5 1 << 4
# define P6 1 << 5
# define P7 1 << 6
# define P8 1 << 7
# define P9 1 << 8
# define P10 1 << 9
# define P11 1 << 10
# define P12 1 << 11
# define P13 1 << 12
# define P14 1 << 13
# define P15 1 << 14
// not valid location
# define P16 1 << 15
// move triplets
Options options[15] = {
{{P1|P2|P4, P1|P3|P6}, 2},
{{P2|P4|P7, P2|P5|P9},2},
{{P3|P5|P8, P3|P6|P10},2},
{{P1|P2|P4, P4|P7|P11, P4|P5|P6, P4|P8|P13},4},
{{P5|P8|P12, P5|P9|P14},2},
{{P1|P3|P6, P4|P5|P6, P6|P9|P13, P6|P10|P15},4},
{{P7|P4|P2, P7|P8|P9},2},
{{P8|P5|P3,P8|P9|P10},2},
{{P9|P8|P7,P9|P5|P2},2},
{{P10|P6|P3,P10|P9|P8},2},
{{P11|P7|P4,P11|P12|P13},2},
{{P12|P8|P5,P12|P13|P14},2},
{{P13|P12|P11,P13|P14|P15,P13|P8|P4,P13|P9|P6},4},
{{P14|P9|P5,P14|P13|P12},2},
{{P15|P10|P6,P15|P14|P13},2}
};
// legal moves
Options legal[15] = {
{{P1|P2, P1|P3}, 2},
{{P2|P4, P2|P5},2},
{{P3|P5, P3|P6},2},
{{P4|P2, P4|P7, P4|P5, P4|P8},4},
{{P5|P8,P5|P9},2},
{{P6|P3, P6|P5, P6|P9, P6|P10}, 4},
{{P7|P4, P7|P8},2},
{{P8|P5, P8|P9},2},
{{P9|P8,P9|P5},2},
{{P10|P6,P10|P9},2},
{{P11|P7,P11|P12},2},
{{P12|P8,P12|P13},2},
{{P13|P12,P13|P14,P13|P8,P13|P9},4},
{{P14|P9,P14|P13},2},
{{P15|P10,P15|P14},2}
};
// for printing solution
struct OptionDesc {
const char* name[4];
int size;
};
OptionDesc desc[15] = {
{{"p1 => p4", "p1 => p6"}, 2},
{{"p2 => p7", "p2 => p9"}, 2},
{{"p3 => p8", "p3 => p10"}, 2},
{{"p4 => p1", "p4 => p11", "p4 => p6", "p4 => p13"}, 4},
{{"p5 => p12", "p5 => p14"}, 2},
{{"p6 => p1", "p6 => p4", "p6 => p13", "p6 => p15"}, 4},
{{"p7 => p2", "p7 => p9"}, 2},
{{"p8 => p3", "p8 => p10"}, 2},
{{"p9 => p7", "p9 => p2"}, 2},
{{"p10 => p3", "p10 => p8"}, 2},
{{"p11 => p4", "p11 => p13"}, 2},
{{"p12 => p5", "p12 => p14"}, 2},
{{"p13 => p11", "p13 => p15", "p13 => p4", "p13 => p6"}, 4},
{{"p14 => p5", "p14 => p12"}, 2},
{{"p15 => p6", "p15 => p13"}, 2}
};
int LEGAL_COUNT = sizeof (legal) / sizeof (Options);
state_t START = P2|P3|P4|P5|P6|P7|P8|P9|P10|P11|P12|P13|P14|P15;
// make move: just xor
inline void make_move(state_t& s, move_t m)
{
s ^= m.move;
}
// undo move: just xor
inline void unmake_move (state_t& s, move_t m)
{
s ^= m.move;
}
// define end state as peg in top position
inline bool end_state (state_t s)
{
return (s ^ START) == (START|P1);
}
// generates moves from table of legal moves, and table of all possible move options
inline void generate_moves(state_t s, vector<move_t>& moves)
{
for (int i = 0; i < LEGAL_COUNT; i++) {
for (int j = 0; j < legal[i].size; j++) {
short L = legal[i].moves[j];
short M = L ^ options[i].moves[j];
if ((s & L) == L && (s & M) == 0) {
move_t m;
m.move = options[i].moves[j];
m.desc = desc[i].name[j];
moves.push_back(m);
}
}
}
}
// basic depth first search:
bool dfs (state_t& s, int& count)
{
bool found = false;
if (end_state(s)) {
count++;
return true;
}
vector<move_t> moves;
generate_moves(s, moves);
for (vector<move_t>::iterator it = moves.begin();
it != moves.end(); it++) {
make_move (s, *it);
found = dfs(s,count);
unmake_move(s, *it);
if (found && 0) {
cout << it->desc << endl;
return true;
}
}
return false;
}
void init(state_t& s)
{
s = START;
}
int main(int argc, char* argv[])
{
state_t s;
int count = 0;
init(s);
bool solved = dfs (s, count);
//cout << "solved = " << solved << endl;
cout << "solutions = " << count << endl;
char c;
cin >> c;
return 0;
}Stack Overflow用户
发布于 2011-06-18 02:19:22
根据你的描述，我怀疑主要的慢点是( a)递归，( b)复制板很多次。如果您可以将它放在一个循环中而不是使用递归，这可能会有所帮助。如果您可以使用一个或几个板的副本(例如，每个潜在路径一个板，通过引用函数传递它)，这也可能会有所帮助。
您的运行时将根据板的大小和挂钩的数量成倍增长；您想要做的是使它尽可能缓慢地增长。
例如，假设你有一个20x20的板子，除了一个点位之外，全部都是满的。有(20^2-1) 399个螺丝钉。其中的每一个都可能会迭代其他398个连接以找到解决方案:这意味着递归循环迭代20x20x20x20次，每次都会生成一个新的400-peg板。这是很多循环，那是很多板！
基于你所链接的代码，我现在看到的唯一优化就是让董事会一次只计算出一个移动，试着看一下移动到哪里，而不是计算每个阶段的所有移动。这是一个线性优化，而不是指数优化；它可能在一定程度上有所帮助，但不会有太大帮助。(例如，不做n^2的计算来计算每一个移动，董事会将做平均(n^2)/2-仍然是O(n^2) )。
而且，getMoves函数本身非常慢--在我看来，它可以被重写得更快，特别是当它被调用16万次时。
https://stackoverflow.com/questions/6393391
复制相似问题
腾讯云开发者
