boost labirynt c++

<email> [email protected] </email>

Mamy dany labirynt:

#include <boost/graph/graph_utility.hpp>
#include <boost\graph\adjacency_list.hpp>
#include <boost\graph\properties.hpp>
#include <iostream>
#include <string>
using namespace boost;

// T_Labirynth type - models labirynth in form of a graph
typedef
      boost::adjacency_list< 
                             vecS, vecS,
		             undirectedS,
                             property< vertex_name_t, std::string >
                    
			   > T_Labirynth;
    
// forwardig decl.
void create_my_labirytnh (T_Labirynth & lab);

int main(void)
{  
     T_Labirynth lab;
    
     create_my_labirytnh(lab);
      
     print_graph(lab);
     
     return 0;
}


// function creating an exemplar labirynth
void create_my_labirytnh (T_Labirynth & lab)
{
    property_map<T_Labirynth, vertex_name_t>::type
                                           labirynth_tail_xy = get(vertex_name, lab);
  
  typedef graph_traits<T_Labirynth>::vertex_descriptor Vertex;
  
  Vertex u1 = add_vertex(lab); Vertex u2= add_vertex(lab); Vertex u3 = add_vertex(lab); 
  Vertex u4 = add_vertex(lab); Vertex u5= add_vertex(lab); Vertex u6= add_vertex(lab); 
  Vertex u7 = add_vertex(lab); Vertex u8 = add_vertex(lab); Vertex u9 = add_vertex(lab); 

  /* ------------> LABIRYNTH < -------------- */

  labirynth_tail_xy[u1] = "[1,1]"; labirynth_tail_xy[u2] = "[1,2]"; labirynth_tail_xy[u3] = "[1,3]"; 
        
  labirynth_tail_xy[u4] = "[2,1]"; labirynth_tail_xy[u5] = "[2,2]"; labirynth_tail_xy[u6] = "[2,3]";
  
  labirynth_tail_xy[u7] = "[3,1]"; labirynth_tail_xy[u8] = "[3,2]"; labirynth_tail_xy[u9] = "[3,3]";
  
  add_edge(u1,u4,lab);
  add_edge(u4,u5,lab);
  add_edge(u5,u2,lab);
  add_edge(u2,u3,lab);
  add_edge(u3,u6,lab);
  add_edge(u6,u9,lab);
  add_edge(u7,u8,lab);

  /* -------------------------------------- */

  return;

}

jak widać w postaci grafu. Chciałbym tu poruszyć temat heurystyk. Jak wam się wydaje, jakie ciekawe "strategie" chodzenia po labiryncie najpewniej doprowadza człowieka do wyjścia (najmniej łażenia bez efektu)?
Jakie labirynty istnieją/istniały w rzeczywistości, lub w grach. Szczególnie ci co lubią grac w gry może mają jakieś swoje sposoby.

<url>www.turek3j.aspnet.pl</url>
</url>

W zasadzie chodzi mi o następujący fakt - program mający dany graf, jest jak człowiek który widzi labirynt "z góry"; Wiadomo że człowiek patrzący z góry na niewielki labirynt szybko znajdzie drogę wyjścia - jak on to robi? Program mógłby zrobić to samo z dużym labiryntem.

Nie konieczne ;)
Oto choćby glupi przykład: jak ktoś chce sobie np. posortować karty to zapewniam cię że nikt nie będzie tego robił quicksortem mimo ze teoretycznie byłoby szybciej niż za pomocą wstawiania/wybierania (a tak przeważnie ludzie układają sobie karty ;) )
Człowiek szuka wyjścia z labiryntu za pomocą DFS'a, ale w tym przypadku lepiej chyba puścić BFS ;)

To, że człowiek nie widzący labiryntu z góry używa DFSa to fakt, ale każdy przyzna że widzieć labirynt z góry to co innego.
Tu znajduje jakoś szybciej... Coś w tym musi być.

Bo wybierasz takie drogi które powinny prowadzić w kierunku wyjscia. Czyli np. mniej chętnie testujesz drogę która prowadzi w innym kierunku. Ale to żadna reguła, wszystko zalezy od labiryntu.

Mi sie wydaje, że człowiek patrząc na labirynt zauważa drogę od razu w całości - nie wodzi gdzieś wzrokiem po rogach, choć to właśnie zalezy od labiryntu.

http://www.turek3j.aspnet.pl

ja osobiście z góry to robię ile mam pewne z jednej strony wyjścia i pewne z drugiej i próbuję to jakoś połączyć :D

Właśnie to mnie ciekawi - labirynt narysowany w klasycznej postaci, czy też w postaci grafu - jeśli nie jest zbyt duży można łatwo ogarnąć bo widać w którą stronę idzie ścieżka od początku i od końca.
A jak to ma zrobić komputer, hmm wyrazić właśnie to "idzie we właściwą stronę".

http://www.turek3j.aspnet.pl