Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C++] Нахождение минимального пути между городами

Автор: Paulskit 2.5.2008, 23:57

Задачка по консольному С/С++
Есть N городов. Для каждой пары городов можно построить дорогу такую, которая бы не заходила в другие города. Собственно нужно найти такую дорогу количество шагов в которой было бы минимально.
Как сделал я - строится матрица (например 6х6), дальше, случайным образом генерируются N городов. Дальше идет выбор начального пункта и пункта назначения (записываю их координаты). Но вот как найти наименьший путь пока не могу придумать. Пробовал перебирать ячейки через switch + random (то есть в switch возможные шаги и рандомом их выбираем) - в принципе дорогу прокладывает, но зачастую она очень не рациональна (то есть или куча лишних шагов или идет по одному из самых длинных путей), ну и потом - слишком много "холостого хода" - очень часто алгоритм выдает что-то типа - подняться на 1 вверх, спуститься на 1 вниз (естественно такая возможность в программе исключена - но все равно итерация потеряна).
В общем помогите с алгоритмом.
user posted image

Автор: GIK 3.5.2008, 11:40

Цитата

(то есть в switch возможные шаги и рандомом их выбираем) - в принципе дорогу прокладывает, но зачастую она очень не рациональна (то есть или куча лишних шагов или идет по одному из самых длинных путей

ДА УЖ... Рандомом пользоваться в таких ращетах, эт круто smile

Добавлено через 4 минуты и 34 секунды
Где-то такое я уже встречал, там метод конкретный использовался, не помню какой.
Я бы сделал просто, создал бы цикл в которм конкретно перебирал города (строился путь), после каждой постройки пути, записывал бы в объект координаты и их последовательность. Попробую написать если время будет smile

Автор: Paulskit 3.5.2008, 14:24

Цитата

ДА УЖ... Рандомом пользоваться в таких ращетах, эт круто smile

Та я сам понимаю - потому и написал сюда ибо алгоритма пока придумать не могу.

Цитата

Я бы сделал просто, создал бы цикл в котором конкретно перебирал города (строился путь), после каждой постройки пути, записывал бы в объект координаты и их последовательность.

Так смысл в том чтобы обходить города. Или я не правильно понял смысл вашего предложения ?

Автор: orthrus 3.5.2008, 15:58

Тут вам скорее с графами нужно мутить. Вот http://algolist.manual.ru/maths/graphs/shortpath/ есть описания алгоритмов для нахождения кратчайшего пути.

Автор: Paulskit 4.5.2008, 15:04

Цитата(orthrus @ 3.5.2008, 15:58)

Там везде описывается поиск кратчайшего пути по вершинам, а не обходя их. Пробовал алгоритм Дейкстры. Но опять же он предпологает наличие расстояний между городами. Я уже придумал алгоритм нахождения расстояний (на листочке, может он и не совсем рациональный, но длина всегда определяется правильно - вот только написать на С++ я его пока не могу). Может у кого есть проверенный алгоритм поиска расстояний от одной точки к другой обходя другие ?

Автор: t_gran 5.5.2008, 03:50

Расстояние от одной точки до другой это школьная математика:
len^2= X^2 + Y^2 (теорема Пифагора smile

)
где X - разность расстояний по оси X, а Y - разность расстояний по оси Y.
А всё остальное, как orthrus писал smile

Автор: Paulskit 14.5.2008, 21:05

Цитата(t_gran @ 5.5.2008, 03:50)

Расстояние от одной точки до другой это школьная математика:
len^2= X^2 + Y^2 (теорема Пифагора smile

)
где X - разность расстояний по оси X, а Y - разность расстояний по оси Y.
А всё остальное, как orthrus писал smile

Теорема Пифагора в постановке этой задачи - это жесть. Как вы себе это представляете на квадратной матрице ?

В общем я написал так:

Код


void move()
{
    int u=0;            //индекс волны
    bool flag=true;        //прошла/не прошла волна
    while (flag) 
    {
        flag=false;
        for (int i=0;i<k;i++)
            for (int j=0;j<k;j++)
                if (s[i][j]==u) 
                {
                    //Проверка соседних клеток на проходимость
                    if ( (s[i-1][j]==127)&&(i>=1) )        { s[i-1][j]=u+1; flag=true; }
                    if ( (s[i+1][j]==127)&&(i+1<k) )    { s[i+1][j]=u+1; flag=true; }
                    if ( (s[i][j-1]==127)&&(j>=1) )        { s[i][j-1]=u+1; flag=true; }
                    if ( (s[i][j+1]==127)&&(j+1<k) )    { s[i][j+1]=u+1; flag=true; }
                }
        u++;    
    }
}

P.S. Точка начало - "0", пустая (проходимая) область - "127", k - размер кв. матрицы

Автор: Kakadu 15.5.2008, 09:20

Мне очень кажется что тут нужен обход графа поиском в глубину...

Автор: Paulskit 15.5.2008, 21:53

Ну уже незачем - с кодом выше отлично работает поиск. А построение просто - находим минимальный элемент около точки финиша и двигаемся в направлении к нулю.
Сегодня увидел другой вариант задачи - города-вершины графа, расстояния забиваются через рандом, каждый город соеденен с любым другим непосредственно. Собственно так же найти минимальный путь, но уже строить его не нужно. Тут думаю алгоритм Дейкстры отлично подойдет.