Pascal

Moderators: None (Apply to moderate this forum)
Number of threads: 4106
Number of posts: 14016

This Forum Only
Post New Thread
Single Post View       Linear View       Threaded View      f

Report
an algorithm like BFS (breadth-first search) but.. (help) Posted by shikalike on 12 Nov 2010 at 9:30 AM
http://en.wikipedia.org/wiki/Breadth-first_search <- BFS wiki
How could i find the path to something making sure that all requirements
are filled. By requirements I mean smth like that



to get to 5 you need to have been in both 3 and 4. So with BFS i would go to 5 straight after getting to 3. Ty in advance.


Report
Re: an algorithm like BFS (breadth-first search) but.. (help) Posted by _Atex_ on 12 Nov 2010 at 8:35 PM
Here's an example how to implement it using recursion. Uses a 2D array instead of a search-tree, it should give a starting point anyway...
const max_size=10;

type graf_element=record flag:boolean;
                         value:byte;
                  end;
     graf=array[1..max_size,1..max_size] of graf_element;


var g:graf;
    found:boolean;
    xpos,ypos:byte;
    steps:word;


procedure init_graf;
 var i,j:byte;
 begin
  randomize;
  for i:=1 to max_size do
   for j:=1 to max_size do begin g[i,j].flag:=false;g[i,j].value:=0;end;
  i:=random(max_size)+1;j:=random(max_size)+1;
  g[i,j].value:=1; { <-- put a nonzero value at a random place }
 end;


procedure search(x,y:byte);
 begin
  if g[x,y].flag or found then exit;
  if g[x,y].value=1 then begin
   found:=true;
   xpos:=x;ypos:=y;
   exit;
  end;
  g[x,y].flag:=true;
  writeln(x,',',y,'  step:',steps);
  inc(steps);
  if x>1        then search(x-1,y  );
  if y>1        then search(x  ,y-1);
  if x<max_size then search(x+1,y  );
  if y<max_size then search(x  ,y+1);
 end;

begin
 steps:=0;found:=false;
 init_graf;
 xpos:=random(max_size)+1;ypos:=random(max_size)+1;
 writeln('Starting at: ',xpos,',',ypos);
 search(xpos,ypos);
 writeln('Value found at ',xpos,',',ypos,'  ',steps,' steps');readln;
end.





 

Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic
© Copyright 2011 Programmersheaven.com - All rights reserved.
Reproduction in whole or in part, in any form or medium without express written permission is prohibited.
Violators of this policy may be subject to legal action. Please read our Terms Of Use and Privacy Statement for more information.
Operated by CommunityHeaven, a BootstrapLabs company.