an algorithm like BFS (breadth-first search) but.. (help)

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

[img=http://img830.imageshack.us/img830/5038/orderr.jpg]

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.


Comments

  • 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...[code][color=Blue]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.[/color][/code]

Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

In this Discussion