4 Replies - 882 Views - Last Post: 06 January 2013 - 04:53 AM Rate Topic: -----

#1 squarepenguin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 34
  • Joined: 16-May 12

unweighted shortest path algorithm using std::map<pair<int,int

Posted 05 January 2013 - 08:31 AM

Hey everyone!

I've been stuck on this issue for a while now, and I feel like I can ask for help now.

the problem:

I basically need a search algorithm that finds the shortest path in an undirected, unweighted graph using std::map to access each Node with coordinates represented as std::pair<int,int>.

The reason I need to use std::map while a list would have made more sense is because the search algorithm is rarely used (yet essential!), and the rest of the program benefits substantially from using std::map.

the reason this problem exists:
>The full assignment is to get a robot through a maze.
>The maze is grid-like (with uniform distances in four directions)
>The starting point, exit point and maze size are unknown.
>The exit point can be detected by sensors.
>The robot can only see one space in the four cardinal directions.

My solution is to use std::map to record every 'tile' so the robot won't search for an exit where it has already searched (preventing it from running in circles). If the robot has only explored tiles around it(which is possible but rare), it uses the search algorithm to find the nearest unexplored part of the maze.

what I've done:

The whole code is finished and runs well and efficiently, the only thing missing is the search-algorithm.

I've tried using list as data-structure, as well as a hybrid between a list and a map. the resources to maintain the list part of the data-structure were too big.

I've researched a lot of algorithms, with Dijkstra's algorithm getting closest to my needs. However, it utilizes std::list and is used for weighted graphs (to be fair: all weights could be set to 1).

I've made some functions to easily access the adjacent tiles.

SO:

Can anyone help me find an effective algorithm?

NOTE: the search algorithm is implemented as a function that has complete and unobstructed access to the std::map (same class).

This post has been edited by squarepenguin: 05 January 2013 - 08:45 AM


Is This A Good Question/Topic? 0
  • +

Replies To: unweighted shortest path algorithm using std::map<pair<int,int

#2 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1327
  • View blog
  • Posts: 4,554
  • Joined: 19-February 09

Re: unweighted shortest path algorithm using std::map<pair<int,int

Posted 05 January 2013 - 12:04 PM

It doesn't sound like you want a shortest path but a path through a maze.

You will need to record whether a path (tile) leads to a dead end as well as whether it was visited, because the robot will need to backtrack.
Was This Post Helpful? 0
  • +
  • -

#3 squarepenguin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 34
  • Joined: 16-May 12

Re: unweighted shortest path algorithm using std::map<pair<int,int

Posted 05 January 2013 - 01:13 PM

No, I want to find the shortest path between the robot's current location and a location where it knows where more unexplored tiles are adjacent to. The rest of the algorithm (that tackles the maze) is already fully operational.

Also:
if a tile exists in the map (checkable with map.count() ) the location has been visited. and it has a vector of 4 Boolean values that tell if the adjacent tile is accessible (= sensors indicate no obstacle to the adjacent tile)

This post has been edited by squarepenguin: 05 January 2013 - 01:20 PM

Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3540
  • View blog
  • Posts: 10,959
  • Joined: 05-May 12

Re: unweighted shortest path algorithm using std::map<pair<int,int

Posted 05 January 2013 - 06:45 PM

Silly question: Why not transform the map into a list for the needs of your search algorithm? Is the graph dynamic that it you would have to recreate the list each time you need to search? Even if it were dynamic, you said that search is rarely called so the overhead of generating the list should be acceptable.
Was This Post Helpful? 0
  • +
  • -

#5 squarepenguin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 34
  • Joined: 16-May 12

Re: unweighted shortest path algorithm using std::map<pair<int,int

Posted 06 January 2013 - 04:53 AM

View PostSkydiver, on 05 January 2013 - 06:45 PM, said:

Silly question: Why not transform the map into a list for the needs of your search algorithm? Is the graph dynamic that it you would have to recreate the list each time you need to search? Even if it were dynamic, you said that search is rarely called so the overhead of generating the list should be acceptable.


Thanks for the suggestion. That's a very valid solition, and I feel silly for not considering it!

Perhaps it's not the most elegant solution, but it would certainly do!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1