задача про домино, поиск наибольшей замыкающейся последовательности Опции

[Zenon]

Здравствуйте.
Поставили перед нами такую задачe. Дано n кубиков домино, как известно они имеют номера с двух сторон, но в задаче сказано, что для данного случая они не ограничены цифрой 6, т.е. значения с обеих сторон могут быть боле 6, например 16 и 12 и т.п. (какие - то разумные пределы конечно есть, но просто больше чем в настоящих, т.е. чем 6). Задние состоит в том, чтобы найти самую длинную замкнутую цепочку.... Если честно теряюсь в догадках и по вопросу алгоритма и по вопросу реализации....
Надеюсь на Вашу помощь.

[Michael_Rybak]

Для перебора может быть полезен критерий: в графе существует эйлеров цикл (цикл, проходящий через все ребра ровно 1 раз) тогда и только тогда, когда 1) он связный и 2) все вершины имеют четную степень (т.е. четное количество инцидентных ребер).

Получается, нам нужно удалить как можно меньше ребер, не потеряв при этом связности, и добившись четности всех вершин. Также легко показать, что количество нечетных вершин всегда четно.

При этом, если граф изначально несвязный, рассматриваем каждую компоненту связности отдельно.

EDIT: удалил неправильные мысли

Сообщение отредактировано: Michael_Rybak - 9.10.2006 10:31

[volvo]

Ну, поскольку ты не написал, на каком языке тебе нужно решение - вот так программа выглядит на Паскале (если костяшек больше 28, измени MAX)...

{$M $C000,0,650000}
const
  max         = 28;
  yes         : boolean = false;

  max_num = 20; { <--- Максимальное число на костяшке домино !!! }

var
  m           :array [0..max_num,0..max_num] of boolean;
  n           :byte;
  cep,best :array [1..max*2] of byte;
  p,maxlen        :integer;

procedure ReadData;
var i,a,b : byte;
begin
  p:=1; maxlen:=0;
  assign(input,'dm.txt'); reset(input);
  fillchar(cep,sizeof(cep),0);
  fillchar(m,sizeof(m),false);
  readln(n);
  for i:=1 to n do begin
     readln(a,b);
     m[a,b]:=true; m[b,a]:=true;
  end;
  close(input);
end;

procedure WriteResults;
var i : integer;
begin
  writeln(maxlen div 2);
  if (maxlen>1) then begin
     i:=1;
     while (i<pred(maxlen)) do begin
        write(' <', best[i], ' ', best[i+1],'> :');
        inc(i,2);
     end;
     write(' <', best[pred(maxlen)], ' ', best[maxlen], '>');
  end;
  writeln;
end;

procedure s_cep;
begin
  if (p-1>maxlen) then begin
     move(cep,best,p-1);
     maxlen:=p-1;
     yes:=(maxlen div 2=n);
  end;
end;

function exist(k:integer):boolean;
var i : integer;
begin
  i:=0; while (i<=max_num) and not(m[k,i]) do inc(i);
  exist:=(i<=max_num);
end;

procedure make_cep(f:integer);
var s:integer;
begin
  if yes then exit;
  if (m[f,f]) then begin
         m[f,f]:=false;
         cep[p]:=f; cep[succ(p)]:=f; inc(p,2);
         if exist(f) then make_cep(f) else s_cep;
         dec(p,2);
         m[f,f]:=true;
  end else
  for s:=0 to max_num do
      if (m[f,s]) then begin
         m[f,s]:=false; m[s,f]:=false;
         cep[p]:=f; cep[succ(p)]:=s; inc(p,2);
         if exist(s) then make_cep(s) else s_cep;
         dec(p,2);
         m[f,s]:=true; m[s,f]:=true;
      end;
end;

var i:integer;
begin
  ReadData;
  for i:=0 to max_num do make_cep(i);
  WriteResults;
end.

При исходном файле

5
1 2
1 3
2 16
3 6
5 16

Программа вывела результат:

5
<5 16> : <16 2> : <2 1> : <1 3> : <3 6>

Тестируй...

[Гость]

Извини не подскажешь решение этой задачи на Си, а то я чувствую, что не переведу сам....

[Nucris]

2volvo
Понимаешь (ничего, что на ты?) дело в том, что у нас по самому Си пары 4 прошло, а вот графами даже не пахнет.... я понять немогу на кого расчитаны эти задания....


2Michael_Rybak
Примерно понятно, но к сожалению базы не хватает
Не подскажешь где это можно прочесть на русском языке?

[volvo]

Что-то в этом духе:

#include <stdio.h>
#include <mem.h>

enum bool {
  false = 0, true = 1
};

const int max = 28;
const int max_num = 20;

bool yes = false;
bool m[max_num + 1][max_num + 1] = {false};

int n;
int cep[2 * max + 1] = {0};
int best[2 * max + 1];
int p, maxlen;
  // cep,best :array [1..max*2] of byte;
  // p,maxlen		:integer;

int read_data() {
  int i, a, b;
  FILE *f;

  if((f = fopen("DM.TXT", "rt")) == NULL) {
	fprintf(stderr, "Cannot open input file.\n");
	return 1;
  }

  // fillchar(cep,sizeof(cep),0);
  // fillchar(m,sizeof(m),false);
  p = 1; maxlen = 0;
  fscanf(f, "%d", &n); // readln(n);
  for(i = 1; i <= n; ++i) {
	fscanf(f, "%d %d", &a, &b); // readln(a,b);
	m[a][b] = m[b][a] = true;
  }
  fclose(f); // close(input);
  return 0;
}

void write_results() {

  int i;
  printf("%d\n", maxlen / 2);
  if(maxlen > 1) {
	i = 1;
	while(i < maxlen - 1) {
	  printf(" <%d %d> :", best[i], best[i+1]);
	  i += 2;
	}
	printf(" <%d %d>", best[maxlen - 1], best[maxlen]);
  }
  printf("\n");
}

void s_cep() {

  if(p - 1 > maxlen) {
	memmove(&best[0], &cep[0], (p - 1)*sizeof(int));
	// move(cep,best,p-1);
	maxlen = p - 1;
	yes = (maxlen / 2 == n) ? true:false;
  }
}

bool exist(int k) {
  // var i : integer;
  int i = 0;

  while((i <= max_num) && (m[k][i] == false)) i += 1;
  return (i <= max_num) ? true:false;
}

void make_cep(int f) {

  int s;

  if(yes == true) return;

  if(m[f][f] == true) {
	m[f][f] = false;
	cep[p] = f; cep[p + 1] = f; p += 2;
	if(exist(f) == true) make_cep(f); else s_cep();
	p -= 2;
	m[f][f] = true;
  }
  else
  for(s = 0; s <= max_num; ++s)
	if(m[f][s] == true) {
	  m[f][s] = m[s][f] = false;
	  cep[p] = f; cep[p + 1] = s; p += 2;
	  if(exist(s) == true) make_cep(s); else s_cep();
	  p -= 2;
	  m[f][s] = m[s][f] = true;
	}
}

int main() {
  int i;

  read_data();
  for(i = 0; i <= max_num; ++i) make_cep(i);
  write_results();
  return 0;
}

(тестовый пример проходит, погоняй еще, может я где-то ошибся при переносе на С...)

[Nucris]

Огромнео спасибо, протестирую, но спасибо за это решение огромное...
Если я ещё не совсем достал, то очень хотелось бы разобраться хотя бы в этом конкретнои примере , т.е. комментарии к решению услышать...если возможно конечно

Если омжно узнать, а заголовочник что должен в себе содержать, просто я взял один сурс файл и скинул туда исходник при запуске получил свдения об отсутствии header. Что в него вписать?

[volvo]

Ну, это во-первых, зависит от твоего компилятора. Ты ж молчишь, я тебе привел решение, работающее на Turbo C++ 3.0 (1990 года выпуска). Тут мне ничего больше не понадобилось, только этот CPP... В других компиляторах может быть по-другому.

[Nucris]

понятно, да на будущее учту, что точность формулировки крайне важна... Мне бы на C, а компилятор Visual C 2005

[Michael_Rybak]

Не подскажешь где это можно прочесть на русском языке?

Погугли "поиск максимального цикла" или "гамильтонов цикл".

Вообще, вынужден я тут признать, что это я глупость написал:

Дело в том, что, если бы эту задачу можно было решать эффективно, то таким же алгоритмом можно было бы искать гамильтонов цикл - если он есть, то наше решение его выдаст, если нету - выдаст меньший цикл.

Глупость потому, что гамильтонов цикл обязан проходить по каждой вершине ровно 1 раз, а цикл по доминошкам - нет.

Вообще забей на это, как я понимаю, переборное решение тебя в любом случае устраивает, так что просто разбирайся с кодом volvo

[Nucris]

Понятно, но все равно тебе спасибо

Очень прошу volvo перевести это решение на чистый С, чтобы оно работало под компилятор Visual C 2005 ... просто у нас завтро проверка что делать никто не знате, пытаться что то доказывать преподу дело гиблое...

[Michael_Rybak]

Ты может BuildLog запости, не у всех ведь есть VC.

[volvo]

Очень прошу volvo перевести это решение на чистый С

А где, собственно, ты увидел отклонения от чистого С? Программа полностью соответствует Стандарту, компилируется и работает в GCC, а если VC НЕ компилирует такие программы - то это его проблемы.

У меня VC, кстати, именно по этой причине и нету.

Ну, хорошо. Вот это попробуй (убрал я тип bool, на который давалось предупреждение... Теперь нет предупреждений вообще...):

#include <stdio.h>
#include <mem.h>

#define max_num 20
#define max 28

int m[max_num + 1][max_num + 1] = {};
int yes = 0;

int n;
int cep[2 * max + 1] = {0};
int best[2 * max + 1];
int p, maxlen;

int read_data() {
  int i, a, b;
  FILE *f;

  if((f = fopen("DM.TXT", "rt")) == NULL) {
	fprintf(stderr, "Cannot open input file.\n");
	return 1;
  }

  p = 1; maxlen = 0;
  fscanf(f, "%d", &n); 
  for(i = 1; i <= n; ++i) {
	fscanf(f, "%d %d", &a, &b);
	m[a][b] = m[b][a] = 1;
  }
  fclose(f);
  return 0;
}

void write_results() {

  int i;
  printf("%d\n", maxlen / 2);
  if(maxlen > 1) {
	i = 1;
	while(i < maxlen - 1) {
	  printf(" <%d %d> :", best[i], best[i+1]);
	  i += 2;
	}
	printf(" <%d %d>", best[maxlen - 1], best[maxlen]);
  }
  printf("\n");
}

void s_cep() {

  if(p - 1 > maxlen) {
	memmove(&best[0], &cep[0], (p - 1)*sizeof(int));
	maxlen = p - 1;
	yes = (maxlen / 2 == n) ? 1 : 0;
  }
}

int exist(int k) {
  int i = 0;

  while((i <= max_num) && (!m[k][i])) i += 1;
  return (i <= max_num) ? 1 : 0;
}

void make_cep(int f) {

  int s;
  if(yes) return;

  if(m[f][f]) {
	m[f][f] = 0;
	cep[p] = f; cep[p + 1] = f; p += 2;
	if(exist(f)) make_cep(f); else s_cep();
	p -= 2;
	m[f][f] = 1;
  }
  else
  for(s = 0; s <= max_num; ++s)
	if(m[f][s]) {
	  m[f][s] = m[s][f] = 0;
	  cep[p] = f; cep[p + 1] = s; p += 2;
	  if(exist(s)) make_cep(s); else s_cep();
	  p -= 2;
	  m[f][s] = m[s][f] = 1;
	}
}

int main() {
  int i;

  read_data();
  for(i = 0; i <= max_num; ++i) make_cep(i);
  write_results();
  return 0;
}

[Nucris]

Запустил, а этот visual собака ругается и вот это выкидыват

1>c:\documents and settings\vbproffi\my documents\visual studio 2005\projects\srav\srav\main.c(2) : fatal error C1083: Cannot open include file: 'mem.h': No such file or directory

Ещё, понимаю что ужасно достал уже всех с этой задачей, но если бы небльшие поясннеия к исходнику (мы вообще то здаём не на компах а как бы так на проверку, потому от чатси галвное продемонстрировать понимание решения), вот собственно хотелось бы его понять

Сообщение отредактировано: Nucris - 9.10.2006 14:40

[Michael_Rybak]

1>c:\documents and settings\vbproffi\my documents\visual studio 2005\projects\srav\srav\main.c(2) : fatal error C1083: Cannot open include file: 'mem.h': No such file or directory

А может, попробуй создать пустой mem.h да и всё
А не получится - посмотри хоть какую нибудь прогу, которая компилится на этом жутком вижуале , из экзамплов там, и посмотри, че там в хедерах такого особоннего надо писать.

Кроме того, если вы сдаете не на компах - в чем проблема, скачай себе эти 17 метров MINGW и всё круто будет. Или, могу тебе старый добрый ТС 3.0 выслать, он 3 метра весит. Кстати, volvo, мой ТС 3.0 не понимает "int m[max_num + 1][max_num + 1] = {};"

Ещё, понимаю что ужасно достал уже всех с этой задачей, но если бы небльшие поясннеия к исходнику (мы вообще то здаём не на компах а как бы так на проверку, потому от чатси галвное продемонстрировать понимание решения), вот собственно хотелось бы его понять

Как раз наоборот - намного приятнее, когда хочешь разобраться, чем когда хочешь просто сдать.

[volvo]

Кстати, volvo, мой ТС 3.0 не понимает "int m[max_num + 1][max_num + 1] = {};"

Ребят, вам шашечки, или ехать? Первая программа работала на TC - не понравилось, теперь работает в ICC/GCC - опять нехорошо...

[Nucris]

Вышли пожалуйста на lit12@bk.ru

[Michael_Rybak]

Ура!

Короче я вот спросил на форуме TopCoder'a, и там ulzha родил гениальную мысль.

Вот полученная им цепочка рассуждений:

1. Представим все возможные числа на доминошках - вершинами в графе, а сами доминошки - ребрами. Теперь перед нами стоит задача построения самого длинного замкнутого маршрута, проходящего через каждое ребро не больше 1 раза, а через каждую вершину - произвольное кол-во раз.

2. Пусть в графе n вершин и m ребер. Добавим к каждой вершине цикл длины m+1, т.е. m новых, фиктивных вершин.

Получится, что, если в начальном графе существовал замкнутый маршрут, проходящий через каждую вершину как минимум один раз, то в новом графе, дополненном циклами, обязательно существует маршрут длины большей, чем n*(m+1) - ведь из каждой вершины мы можем пройтись по ее дополнительному циклу.

Понятно, что верно и обратное утверждение: получить в новом графе маршрут длины большей, чем n*(m+1), можно *только* посетив каждую вершину оригинального графа как минимум один раз.

3. M. R. Garey, D. S. Johnson и R. Endre Tarjan показали, что поиск гамильтонова цикла в планарном, кубическом, 3-связном графе является NP-полной задачей.

4. Кубический граф - такой, у которого степень каждой вершины равна 3. Получается, замкнутый маршрут в таком графе не может побывать в какой-нибудь вершине больше одного раза - ведь это означало бы, что ее степень - как минимум 4.

5. Сведем это воедино.

• Рассмотрим кубический, планарный, 3-связный (n, m) граф. Добавим к каждой вершине цикл длины m+1.
• Найдя такой цикл, мы однозначно сможем определить (критерий - ребер в найденном цикле больше n(m+1)), существует ли в изначальном графе цикл, проходящий через каждую вершину как минимум 1 раз; если существует, то мы его уже построили - просто удаляем фиктивные ребра из ответа
• В кубическом графе никакой цикл не может проходить в какую-нибудь вершину больше 1 раза, поэтому фактически мы научились строить гамильтонов цикл (в случае его существования)
• Итак, мы свели NP-полную задачу к исходной, т.е. показали, что, умея решать задачу про доминошки за полиномиальное время, научимся решать за такое же время NP-полную задачу.

Браво, ulzha!