Минимальное множество прямых (рекурсия с возвратом) Опции

[Даша]

Всем доброго времени суток! Прошу помочь со следующей задачей: найти минимальное множество прямых, проходящих через все заданные точки. То есть заданы координаты точек и ответом должно быть число прямых. Не знаю как организовать перебор всех вариантов, очень прошу написать хотя бы в общем виде сам алгоритм.

[Lapp]

Вот. Выстругал буратинку )).
Но снова она мне не по нутру.. Думаю, можно сделать намного красивее.. Может, кто-нить сделает. Я тоже еще подумаю..

Да, как я сказал, пришлось переделать всю схему перебора. Коротко могу изложить так..
Один вызов Draw (от слова рисовать линию) рисует одну линию в цикле по всем парам точек (в двойном цикле). Нарисовав линию, он проверяет, какие точки она еще задела. Все задетые точки заносит в массив Co (Covered). Затем вызывает вторую (следующую) копию. Когда массив Co заполнен до конца (это проверяется при входе в Draw), она смотрит, сколько проведено линий (Lin). Если это число меньше, чем MinLin - обновляет MinLin. Вот, примерно так.

Ты посмотри прогу и задавай конкретные вопросы. Работает она, похоже, верно, но.. оооочень медленно. То есть массив из 9 точек обсчитывался на моей тачке почти минуту. При этом время растет с числом точек стремительно (думаю, приблизительно по факториалу). Поэтому 10 точек будет считаться гораздо дольше.. Ускорить можно оптимизацией (возможностей куча), но от характера зависимоти не уйти, думаю (но подумаю еще)).

Короче, вот тебе код. Разбирайся и задавай вопросы.

const
  m= 100;
  e= 1e-7;

type
  tPoint= record
    x,y: double;
  end;
  tCo= array [1..m] of boolean;

var
  p: array [1..m] of tPoint;
  Co: tCo;
  n,Lin,MinLin: integer;
  f: text;


function Eq(a,b: tPoint): boolean;
begin
  Eq:= (a.x=b.x) and (a.y=b.y)
end;


function Aligned(a,b,c: tPoint): boolean;
var
  d: tPoint;
begin
  if a.x=b.x then begin
    d:= a;
    a:= c;
    c:= d
  end
  else if a.x=c.x then begin
    d:= a;
    a:= b;
    b:= d
  end;
  Aligned:=
    Eq(a,b) or
    Eq(b,c) or
    Eq(c,a) or
    (a.x=b.x) and (a.x=c.x) or
    (Abs((b.y-a.y)/(b.x-a.x)-(c.y-a.y)/(c.x-a.x))<e)
end;


procedure Draw;
var
  i,j,k: integer;
  b: boolean;
  c: tCo;
begin
  b:= false;
  for i:=1 to n do b:= b or not Co[i];
  if b then
    for i:=1 to n do begin
      b:= Co[i];
      Co[i]:= true;
      for j:=1 to n do if (i<>j) and not Co[j] then begin
        c:= Co;
        Co[j]:= true;
        Inc(Lin);
        for k:=1 to n do
          if (k<>i) and (k<>j) then Co[k]:= Co[k] or Aligned(p[i],p[k],p[j]);
        Draw;
        Dec(Lin);
        Co:= c
      end;
      Co[i]:= b
    end
  else
    if Lin<MinLin then MinLin:= Lin
end;


begin
  Assign(f,'dasha.dat');
  Reset(f);
  n:= 0;
  while not EoF(f) do begin
    Inc(n);
    ReadLn(f,p[n].x,p[n].y);
    Co[n]:= false
  end;
  Close(f);
  MinLin:= MaxInt;
  Lin:= 0;
  Draw;
  WriteLn(MinLin);
  ReadLn
end.

Формат входного файла тот же. Вот на этом выдает 3.

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