pascal回溯题目,到底怎么做才不会超时,求解答呀!

发布网友 发布时间：2024-10-23 16:54

我来回答

共3个回答

热心网友 时间：3小时前

确实如楼上所述，只有进行回溯迭代来求解。
不过你可以加一些优化来减少不必要的回溯。
我大概看了你的程序，可以优化的地方有很多。
我这里直接改写一下：

var b:array[1..1000] of integer;//用记录独立集中的相邻节点，可以节省下pd函数。

procedure search(max,t:longint);
var
i,j:longint;
begin
if (max+n-t<=ans) then exit;//强剪枝，当前数量+剩余数量<=最大结果时，返回。
if t>=n then
begin
if max>ans then
begin
ans:=max;
for i:=1 to n do
begin
a[i]:=s[i];
end;
exit;
end;
end;
for i:=t to n do
begin
if (b[i]=0) then //当前独立集与该节点不相邻
begin
s[i]:=1;
for j:=t+1 to n do b[j]:=b[j]+g[i,j];//邻接矩阵用1,0储存,1为邻接,读入的时候赋值g[j,i]:=g[i,j]=1
search(max+1,i+1);
for j:=t+1 to n do b[j]:=b[j]-g[i,j];
s[i]:=0;
end else search(max,i+1);
end;
end;

你用这个跑一下试试，还有一些优化手段，你可以仔细想想。

热心网友 时间：3小时前

有数据范围吗？

= =

好吧仔细看了看这道题是求一般图的最大独立集啊

NP-C问题

简单的说就是只能暴搜= =

但是暴搜的技巧有很多 例如可行性剪枝 最优性剪枝

加上这些应该就可以了

等我拍一份代码

==================================

顺便一提 祝Pascal选手早日转C

==================================

var
   n, m, ne, i, ans, bits, ansx, x, y: longint;
   next, _to, link: array[0..20] of longint;

procedure addedge(x, y: longint); inline;
begin
   inc(ne);
   next[ne] := link[x];
   _to[ne] := y;
   link[x] := ne;
end;

function countbit(x: longint): longint; inline;
var
   ret : longint;
begin
   ret := 0;
   while x > 0 do
   begin
      if (x and 1 = 1) then
         inc(ret);
      x := x shr 1;
   end;
   exit(ret);
end;

function check(x: longint): boolean; inline;
var i, j: longint;
begin
   for i := 0 to n - 1 do
      if ((x shr i) and 1) = 1 then
      begin
         j := link[i];
         while j <> 0 do
         begin
            if ((x shr _to[j]) and 1) = 1 then
               exit(false);
            j := next[j];
         end;
      end;
   exit(true);
end;

begin
   readln(n, m);
   for i := 1 to m do
   begin
      readln(x, y);
      addedge(x - 1, y - 1);
      addedge(y - 1, x - 1);
   end;
   
   ans := 0; bits := 0;
   for i := 0 to (1 shl n) - 1 do
   begin
      ansx := countbit(i);
      if check(i) and (ansx > ans) then
      begin
         ans := ansx;
         bits := i;
      end;
   end;
   
   writeln(ans);
   for i := 0 to n - 2 do
      write((bits shr i) and 1, ' ');
   writeln((bits shr (n-1)) and 1);
end.

只拍了你给的样例

有问题问我

【不过我对会不会T不是很有自信= =先测一下试试看？】

复杂度是裸的O(2^n * (n + m))

热心网友 时间：3小时前

var
a:array[1..200,1..200] of boolean;
b:array[1..200] of integer;
c:array[1..200] of boolean;
n,m:integer;
i,j,k,p,q:integer;
max,num:integer;
f:text;
begin
for i:=1 to 200 do for j:=1 to 200 do a[i,j]:=false;
assign(f,'独立集.in'); reset(f);
readln(f,n,m);
for i:=1 to m do begin readln(f,p,q); a[p,q]:=true; a[q,p]:=true; end;
close(f);
for i:=1 to n do c[i]:=true;

repeat
for i:=1 to n do begin
b[i]:=0;
for j:=1 to n do if a[i,j] then inc(b[i]);
end;
num:=0;
for i:=1 to n do if b[i]>0 then inc(num);
if num>0 then begin 
max:=b[1];
k:=1;
for i:=2 to n do if b[i]>=max then begin k:=i; max:=b[i]; end;
{带等号则序号小的优先，否则序号大的优先}
for i:=1 to n do begin a[i,k]:=false; a[k,i]:=false; end; 
c[k]:=false;
end;
until num=0;

for i:=1 to n do if c[i] then write(i:3);
end.