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

#cpp #алгоритм

На вход программе даются две точки: точка старта и точка финиша.
Необходимо из точки старта попасть в точку финиша. Шагать из любой точки можно несколькими
способами.

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

Вобщем, строим граф на лету, индексы - номера вершин. Поиск в ширину. Классика, так
сказать...

На коленке писанный код тут и ниже. Оптимизации, ввод-вывод и т.п. - напишите сами,
я этим не заморачивался, жестко прошил 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;
}