Я должен найти кратчайший путь через несколько контрольных точек «гоночной трассы». Как мне управлять контрольными точками с моей BFS?

Полное описание проблемы, которую я пытаюсь решить, можно найти здесь: http://i.imgur.com/uOWe6.png

Я использую BFS и создал объект RaceTrack. Настройка очереди BFS не является проблемой, и этот проект был бы идеальным (я думаю), если бы мне нужно было найти кратчайший путь к одной цели. Но вместо этого мне нужно проехать от начальной точки через каждую контрольную точку по порядку! У кого-нибудь есть идеи, как можно реализовать это со стандартной идеей использования BFS? Я включу свой код, но имейте в виду, что он ОЧЕНЬ незакончен и может не иметь смысла. Метод «переместить» — это то, где большая часть работы должна быть сделана.

Вы заметите, что я остановился на операторе if, который проверяет, является ли пространство, в которое вы перемещаетесь, целым числом.

Ваши предложения приветствуются.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <set>

using namespace std;

class RaceTrack
{
public:
RaceTrack() { count = 0;}

bool isSolved()
{
if (solved == 1)
return true;
else
return false;
}

int solved;
string track;
int count;
set<char> prevChkPt;
};

int main()
{
list<RaceTrack> q;  // queue for BFS
set<RaceTrack> v; // set of visited tracks

RaceTrack x;
string sLine;
vector<int> chkPts;
int start;

int w, h;
int tmp = 0;

cin >> w >> h;

for (int i = 0; i < h; i++)
{
cin >> sLine;
x.track += sLine;
}

q.push_back(x);

while (q.size() > 0 && x.isSolved() == false)
{
x = q.front();
q.pop_front();

start = x.track.find_first_of('0');

if (x.isSolved() == false && v.find(x) == v.end())
{
v.insert(x);

move (start, w, h, x, q, v, 'q');
move (start, w, h, x, q, v, 'u');
move (start, w, h, x, q, v, 'p');
move (start, w, h, x, q, v, 'l');
move (start, w, h, x, q, v, 'r');
move (start, w, h, x, q, v, 'z');
move (start, w, h, x, q, v, 'd');
move (start, w, h, x, q, v, 'm');
}
}

if (x.isSolved == true)
cout << x.count;
else
cout << -1;

// for testing purposes only:
string quit;

// for testing purposes only:
cin >> quit;
if(quit == "quit")
return 0;
}

void move (int start, int w, int h, RaceTrack x, list<RaceTrack> q, set<RaceTrack> v, char direction)
{
int d1, d2, d3, d4; // diagonal indices

if (direction == 'q') // diagonal top left
{
d1 = start - w - 1;

if (start % w == 0 || start < w)
return;
else
{
if (x.track[d1] == 'x')
return;
else if (x.track[d1] == ' ')
{
x.track[d1] = x.track[start];
x.count++;
}
else if (isdigit(x.track[d1]))
x.prevChkPt.insert(x.track[d1]);
}

}

if (v.find(x) == v.end())
q.push_back(x);
}

1

Решение

Как уже упоминалось, вы можете посмотреть на Алгоритм Дейкстры.

                                                         введите описание изображения здесь

2

Другие решения

Других решений пока нет …