Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Pascal
Перезагрузить страницу Гамильтонов путь
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
OdinKamui OdinKamui вне форума
Member
 
Сообщений: 26
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 12.06.2008
По умолчанию 22.06.2009, 22:58

Алгоритм нахождения Гамильтонова пути
алгоритм вроде верно написал, но при вводе любых вершин всегда нет пути
И кто-нибудь киньте ссылку на нахождение кратчайшего пути между двумя вершинами графа(использовать метод поиска в ширину)
Код:
Program HamiltonPaht;
uses crt;
Const n=6;
C:array[0..n,0..n] of integer=((0,1,1,0,0,1,1),
                               (1,0,1,1,0,0,0),
                               (1,1,0,1,1,0,0),
                               (0,1,1,0,1,1,0),
                               (0,0,1,1,0,1,1),
                               (1,0,0,1,1,0,0),
                               (1,0,0,0,1,0,0));
  Var visit:array[0..n]of boolean;
      v,w,i:integer; p:boolean;
Function HamiltonPath(v,w,d:integer): boolean;
     var k:integer; p:boolean;
   begin If (v=w)and(d=0) then HamiltonPath:=true
                          else begin visit[v]:=false;write(d,' ');
                                     for k:=0 to n do
                                     if (C[v,k]=1)and(visit[k]) then
                                        if HamiltonPath(k,w,d-1) then begin
                                           HamiltonPath:=true;break;
                                                                         end;
                                     visit[v]:=true;inc(d);
                                     HamiltonPath:=false;
                                end;
    end;
Begin clrscr;
      writeln('Vvedite nachlo i verwina');
      readln(v,w);
      for i:=0 to n do
          visit[i]:=true;
      p:=HamiltonPath(v,w,n);
      If p=true then write('Pyt cywectvyet') else write('Het pytu');
 End.

Вот и сам метод поиск в ширину(здесь нужно где-то запоминать путь и сравнивать с предыдущем)
Код:
program B_F_S;
const n=9;
A:array[1..n,1..n]of byte=((0,1,0,0,0,1,0,0,0),
                           (1,0,1,0,0,0,1,0,0),
                           (0,1,0,1,0,0,0,0,0),
                           (0,0,1,0,1,0,0,0,0),
                           (0,0,0,1,0,1,0,1,1),
                           (1,0,0,0,1,0,0,0,0),
                           (0,1,0,0,0,0,0,0,0),
                           (0,0,0,0,1,0,0,0,0),
                           (0,0,0,0,1,0,0,0,0));
var visit:array[1..n]of boolean;
i,v:integer;
procedure BFS(v:integer);
var och:array[1..n]of integer;
uk,un:integer;
Begin write(v:3);
      visit[v]:=false;
      uk:=0;un:=0;
      inc(uk); och[uk]:=v;
      while un<uk do
          Begin un:=un+1; v:=och[un];
                for i:=1 to n do
                if (A[v,i]=1) and (visit[i]) then begin write(i:3);
                                                        visit[i]:=false;
                                                        inc(uk); och[uk]:=i;
                                                  end;
          end;
end;
Begin writeln('Vvedite verwuny');
      readln(v);
      for i:=1 to n do
      visit[i]:= true;
      BFS(v);
End.
Ответить с цитированием
  (#2 (permalink)) Старый
Exmap Exmap вне форума
Member
 
Сообщений: 1,045
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 17.09.2007
По умолчанию 23.06.2009, 09:40

Задача эта NP-полная. Проще говоря, перебор тут рулит.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Путь загрузки sapir IT 5 09.03.2011 14:29
Путь к сохранику Dialog567 Компьютерные игры 8 23.02.2011 16:52
Гамильтонов путь и связность единиц positron Алгоритмы 0 13.12.2010 00:38
Воздушный путь PavelPPP Prolog 1 12.11.2009 13:43
Эйлеров путь Dimitsuri Prolog 1 03.09.2007 17:08
Пропишите в C++Builder6 путь к разархивированной папке где найти этот путь Evangelion C++ Builder 3 11.01.2007 18:13
Гамильтонов цикл AlexBugor Prolog 3 23.11.2006 18:14
Относительный путь Loid Алгоритмы 3 11.03.2006 19:56
минимальный путь groznii Prolog 1 07.10.2005 23:38
Построить гамильтонов граф для каркаса n-мерного куба Фумска Pascal 0 03.06.2004 14:37
*********Путь Воина******** Anonymous Офтопик 0 03.06.2004 11:52
Левый путь Anonymous PHP 1 07.07.2003 17:15



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов