奋斗了一上午，终于让IDA*相比迭代加深搜索有了一点微弱的优势= =
程序代码：
#include <stdio.h>
#include <stdlib.h>
#define N 1000000
#define FLOOR(a, b) ((a) / (b) + ((a) % (b) != 0))
#define GET_LOW(a, b) FLOOR(b, a)
#define GET_HIGH(a, b, k) FLOOR((k) * (b), (a))
#define GET_H(c, d, e) FLOOR((c) * (e), (d))
struct
{
int c, d, e, deep;
} stack[N];
int last, a, b, ans[N], cur[N], clen, limit;
void simply(int *a, int *b)
{
int c = *a, d = *b;
while (d != 0)
{
int t = d;
d = c % d;
c = t;
}
*a /= c;
*b /= c;
}
void push_child(int c, int d, int k, int g)
{
int i, b, e;
b = GET_HIGH(c, d, k);
e = GET_LOW(c, d);
if (clen != -1 && e <= cur[clen])
e = cur[clen] + 1;
for (i = b; i >= e; --i)
{
stack[last].c = c * i - d;
stack[last].d = i * d;
simply(&stack[last].c, &stack[last].d);
if (stack[last].c > 0 && stack[last].d > 0
&& stack[last].d < 0xFFFF)
{
stack[last].e = i;
stack[last].deep = g;
if (last == N)
exit(2);
++last;
}
}
}
int idastar(void)
{
int i;
simply(&a, &b);
ans[0] = -1;
last = 0;
limit = GET_H(a, b, GET_LOW(a, b)) - 1;
while (ans[0] == -1 && ++limit < N)
{
clen = -1;
push_child(a, b, limit + 1, 0);
while (last > 0)
{
--last;
clen = stack[last].deep;
cur[clen] = stack[last].e;
if (stack[last].c == 1)
{
if (cur[clen] < stack[last].d
&& (ans[0] == -1 || stack[last].d < ans[clen + 1]))
{
for (i = 0; i <= clen; ++i)
ans[i] = cur[i];
ans[clen + 1] = stack[last].d;
}
}
else if (limit >= clen
+ GET_H(stack[last].c, stack[last].d, cur[clen]))
push_child(stack[last].c,
stack[last].d, limit - clen, clen + 1);
}
}
return ans[0] != -1;
}
int main(void)
{
int i;
while (scanf("%d%d", &a, &b) != EOF)
{
if (!idastar())
puts("can't find answer");
else
{
for (i = 0; i <= limit; ++i)
printf("%d%c", ans[i], i == limit ? '\n' : ' ');
}
}
return 0;
}
这次问题少多了。手头有一份完全没问题的IDA*代码，可惜效率比较差，遍历的节点数比IDFS还要多。这一份比IDFS快，但是总有几个小数据有点毛病。目前这个是通过了大部分数据的了（真奇怪为什么判定0就可以忽略掉那些溢出错误，而判定1却没法忽略……）。其实就是某些地方的加一减一的问题，有时间的话推一下上下界公式，这样会比较好一点。
回LS某人的问题，11 999 是返回216 296 333没错，因为是要求分数自大向小排列的，因此333是三个分数在中最小的一个，而他比其他的解（比如你提出的）最小的要大，因此它是最优解。注意这个分数序列是有顺序的。
[
本帖最后由 StarWing83 于 2009-9-12 16:23 编辑 ]
2009-09-10 23:15
