Поиск пути между точками, следуя правилам. Каким алгоритмом пользоваться?

На вход программе даются две точки: точка старта и точка финиша. Необходимо из точки старта попасть в точку финиша. Шагать из любой точки можно несколькими способами.
int start; //точка старта 2*start; //из любой точки (3*start)+1; //тоже из любой точки start/2; //только из точек с четным номером (start-1)/3; //из точек номер которых при делении на 3 дает остаток от деления 1
Как сделать перебор всех вариантов и вывести самый короткий путь? Интересует сам алгоритм.
Пример программы.
На вход 1 6.
На выход
7
1 4 8 16 5 10 3 6.

Ответ

Вобщем, строим граф на лету, индексы - номера вершин. Поиск в ширину. Классика, так сказать...
На коленке писанный код тут и ниже. Оптимизации, ввод-вывод и т.п. - напишите сами, я этим не заморачивался, жестко прошил 1 и 6....
#include #include #include #include #include #include
using namespace std;
struct Node { Node(int i, int p = -1):idx(i),prev(p){} int idx; // Индекс int prev; // Предыдущий узел - для восстановления пути bool operator <(const Node& n) const { return idx < n.idx; } };
int main() { int start = 1, stop = 6;
queue Q; // Очередь BFS set S; // Множество уже обработанных узлов
Q.push(Node(start)); while(!Q.empty()) { S.insert(Q.front()); // Внесли в обработанные int index = Q.front().idx; // Индекс if (index == stop) break; // Найден! Q.pop(); // Убираем из очереди vector next; // Возможные варианты next.push_back(2*index); next.push_back(3*index+1); if (index%2 == 0) next.push_back(index/2); if (index%3 == 1) next.push_back((index-1)/3); for(int i: next) // Обработка возможных вариантов { Node n(i,index); if (S.find(n) != S.end()) continue; // Уже отработан Q.push(n); // Внесение в очередь еще не рассмотренных } }
// Вывод цепочки - так как в обратном порядке, используем стек stack path; for(int index = Q.front().idx; index != -1; ) { path.push(index); auto i = S.find(Node(index)); // Поиск предыдущего if (i == S.end()) break; // Береженого Бог бережет :) index = i->prev; // Предыдущий в цепочке } // Вывод из стека while(!path.empty()) { cout << path.top() << " "; path.pop(); } cout << endl; }