Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Алгоритм поиска кратчайшего пути  (Прочитано 18925 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Anaya
Гость
« : 16-04-2007 12:05 » 

Дано:
матрица смежности ( две вершины соединены ребром - 1, не соединены - 0 )

Нужно:
Найти кратчайший путь из вершины k в вершину t. ( ну не суть как их обозвать - из произвольной в произвольную ).

Почему-то Дейсктру клинит ( подозреваю, что потому что "веса" всех ребер =1 )

Какой алгоритм будет наиболее эффективен??
( и вообще - какие алгоритмы тут можно применить? )
если еще и ссылочки на реализации на С/С++ - то вообще просто шикарно!!!

P.S.
Это нужно для диплома, чтобы создать видимо "долгого и мучительного выбора, с исследованиями эффективносит и т.д. и т.п." - помогите - до защиты 1.5 месяца ( как всегда, студентчество "тянет до последнего", простите)

Спасибо большое заранее всем откликнувшимся...
Записан
Sands
Помогающий

ua
Offline Offline

« Ответ #1 : 16-04-2007 13:01 » 

Можно посмотреть на algolist.manual.ru как по мне то один из немногих, где обьясняют нормально и примеры реализаций можно найти.
Записан
bebabo
Помогающий

ru
Offline Offline

WWW
« Ответ #2 : 31-05-2007 08:06 » 

вот реализация поиска пути в глубину от H.Вирта.  можно посмотреть в консольном режиме.

cуть происходящего):
есть лабиринт, в котором "1" обозначает проход, а "0" - стену.

1110110001111
1011101111101
1000101010101
1000111010111
1111100001000
0000100000000
0000111111111

Для того, чтобы найти путь из точки А (0,0) в точку Б (6, 12), пользуясь данным методом поиска, мы должны выбрать некую следующую позицию. В нашем варианте мы будем выбирать любую соседнюю ячейку (исключая ячейки по диагонали) в порядке по часовой стрелке: 1 - строкой выше, 2 - колонкой правее, 3 - строкой ниже, 4 - колонкой левее. Если новая позиция находится на пути к конечной точке - переходим на нее, если нет - выбираем другую позицию. При этом путь ведущий к цели будет помечаться "9", а путь ведущий в тупик - "2".
Вот как будет выглядеть поиск пути в глубину из точки А в точку Б:

9990220002222
1099902222202
1000902020202
1000922020222
1111900001000
0000900000000
0000999999999

Оказавшись в тупике, мы возвращаемся до тех пор, пока не оказываемся в позиции, из которой возможно сделать другой ход и вновь пытаемся достичь конечную точку.
 
Код:
//Position.h
//объявление класса Position

#ifndef POSITION
#define POSITION

class Position
{
private:
    int row;
    int column;
public:
    Position();
    Position(int row, int column);
    void setPosition(int row, int column);
    int getRow();
    int getColumn();
};
#endif

//Position.cpp
//методы класса Position

#include "Position.h"

Position::Position()
{
    row=0;
    column=0;
}

Position::Position(int row, int column)
{
    this->row=row;
    this->column=column;
}

void Position::setPosition(int row, int column)
{
    this->row=row;
    this->column=column;
}

int Position::getRow()
{
    return this->row;
}

int Position::getColumn()
{
    return this->column;
}

//Application.h
//

#ifndef APPLICATION
#define APPLICATION

#include <iostream>
#include "Position.h"

using namespace std;

class Application
{
    friend ostream& operator << (ostream& stream,
        Application& app);
public:
    Position generateInitialState();//генерирует начальное состояние - ввод начальных и конечных точек
    bool valid (Position& pos);//проверка корректности ввода
    void record (Position& pos);//отмечает пройденный путь как "9"
    bool done (Position& pos);//проверка текущей и конечной точек на совпадение
    void undo (Position& pos););//отмечает пройденный путь как "2"

    class Iterator
    {
    public:
        Iterator();
        Iterator (Position& pos);
        Position operator++ (int);
        bool atEnd();
    protected:
        void* fieldPtr;
    };
};
#endif

//BackTrack.h
//

#ifndef BACKTRACK
#define BACKTRACK

#include "Application.h";
#include "Position.h"

class BackTrack
{
public:
    BackTrack (const Application& app);
    bool tryToSolve (Position pos);//рекурсивная функция - попытка найти путь через выбранную позицию
protected:
    Application app;
};
#endif

//BackTrack.cpp
//

#include "BackTrack.h"

using namespace std;

BackTrack::BackTrack (const Application& app)
{
    this->app=app;
}

bool BackTrack::tryToSolve (Position pos)
{
    bool success = false;

    Application::Iterator itr(pos);
    while(!success && !itr.atEnd())
    {
        pos=itr++;
        if(!app.valid(pos))
        {
            app.record(pos);
            if(app.done(pos))
                success=true;
            else
            {
                success = this->tryToSolve(pos);
                if(!success)
                    app.undo(pos);
            }
        }
    }
    return success;
}

//Maze.cpp
//реализация методов класса Аpplication и установка значений лабиринта

#include <iostream>
#include <string>
#include "Application.h"

const short WALL=0;
const short CORRIDOR=1;
const short PATCH=9;
const short TRIED=2;
const short ROWS=7;
const short COLUMNS=13;

short grid [ROWS][COLUMNS] =
{
    {1,1,1,0,1,1,0,0,0,1,1,1,1},
    {1,0,1,1,1,0,1,1,1,1,1,0,1},
    {1,0,0,0,1,0,1,0,1,0,1,0,1},
    {1,0,0,0,1,1,1,0,1,0,1,1,1},
    {1,1,1,1,1,0,0,0,0,1,0,0,0},
    {0,0,0,0,1,0,0,0,0,0,0,0,0},
    {0,0,0,0,1,1,1,1,1,1,1,1,1},
};

Position start, finish;

using namespace std;

Position Application::generateInitialState()
{
    const string START_PROMT = "Введите начальные строку и колонку:";

    const string FINISH_PROMT = "Введите конечные строку и колонку:";

    int row, column;

    cout << START_PROMT;
    cin>>row>>column;
    start.setPosition(row,column);
    cout << FINISH_PROMT;
    cin>>row>>column;
    cin.get();
    finish.setPosition(row,column);       
    return start;
}

bool Application::valid(Position& pos)
{
    if(pos.getRow()>=0 && pos.getRow()<ROWS &&
        pos.getColumn()>=0 && pos.getColumn() < COLUMNS &&
        grid [pos.getRow()][pos.getColumn()] == CORRIDOR)
        return false;
    else
        return true;

}

void Application::record(Position& pos)
{
    grid[pos.getRow()][pos.getColumn()]=PATCH;
}

bool Application::done(Position& pos)
{
    if(pos.getRow()==finish.getRow()&&
        pos.getColumn()==finish.getColumn())
        return true;
    else
        return false;
}

void Application::undo(Position& pos)
{
    grid [pos.getRow()][pos.getColumn()]=TRIED;
}

ostream& operator<< (ostream& stream, Application& app)
{
    cout<<endl;//
    for(int row=0; row<ROWS; row++)//
    {
        for(int column=0; column<COLUMNS; column++)//
            cout<<grid[row][column]<<' ';//
        cout<<endl;//
    }
    return stream;
}

struct itrFields
{
    int row,
        column,
        direction;
};

Application::Iterator::Iterator(Position& pos)
{
    itrFields* itrPtr = new itrFields;//
    itrPtr->row=pos.getRow();//
    itrPtr->column=pos.getColumn();//
    itrPtr->direction=0;//
    fieldPtr=itrPtr;
}

Position Application::Iterator::operator ++ (int)
{
    itrFields* itrPtr = (itrFields*) fieldPtr;
    int nextRow=itrPtr->row,//
        nextColumn=itrPtr->column;

    switch(itrPtr->direction++)//
    {
    case 0: nextRow=itrPtr->row-1;//
        break;
    case 1: nextColumn=itrPtr->column+1;//
        break;
    case 2: nextRow=itrPtr->row+1;//
        break;
    case 3: nextColumn=itrPtr->column-1;//
        break;
    }

    Position next(nextRow, nextColumn);
    return next;
}

bool Application::Iterator::atEnd()
{
    return ((itrFields*)fieldPtr)->direction>=4;//
}

//BackTrackMain.cpp
//функция main

#include <iostream>
#include <string>
#include "BackTrack.h"
#include "Application.h"
#include "Position.h"

using namespace std;

int main()
{
    const string INITIAL_STATE = "Начальное состояние: \n";
    const string SUCCESS = "\n\n Решение найдено:";
    const string FAILURE =     "\n\n Решения нет";
    const string CLOSE_WINDOW_PROMT = "Нажмите Enter, чтобы закрыть окно";

    Application app;
    BackTrack b(app);

    cout<<INITIAL_STATE;//
    Position start = app.generateInitialState();
   
    cout<<app;//ввод начальных значений//

    if(app.valid(start))//проверка на корректность ввода
        cout<<FAILURE<<endl;//
    else
    {
        app.record(start);//помечаем пройденные ячейки как "9"
        if(app.done(start) || b.tryToSolve(start))
            cout<<SUCCESS<<endl<<app;//
        else
        {
            app.undo(start);
            cout<<FAILURE<<endl;//
        }
    }

    cout<<endl<<endl<<CLOSE_WINDOW_PROMT;//
    cin.get();

    return 0;
}
Записан

Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 31-05-2007 08:35 » 

волновой алгоритм вам нужен ) Дёшево и сердито.
например
http://algolist.manual.ru/games/wavealg.php
« Последнее редактирование: 31-05-2007 08:39 от Алексей1153++ » Записан

sfok
Новенький

ru
Offline Offline

« Ответ #4 : 10-06-2011 23:40 » 

под эти условия подойдет - алгоритм поиска пути A*, посмотрите вот здесь: h**p://scr1pter.blogspot.com/p/blog-page.html
« Последнее редактирование: 11-06-2011 03:45 от Finch » Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #5 : 11-06-2011 04:08 » 

Цитата: Anaya
Почему-то Дейсктру клинит ( подозреваю, что потому что "веса" всех ребер =1 )
Пока я не вижу никаких проблем с Дейкстрой.

Где твоё понимание алгоритма, твоя реализация, твой пример и твой неправильный результат в этом примере?

bebabo, твоя матрица - это не матрица смежности, это просто рисунок лабиринта.
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Sla
Команда клуба

ua
Offline Offline
Пол: Мужской

WWW
« Ответ #6 : 11-06-2011 04:11 » 

Dimka,
вот же некроманы Улыбаюсь
Записан

Мы все учились понемногу... Чему-нибудь и как-нибудь.
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #7 : 11-06-2011 08:21 » new

Sla, а я на дату не посмотрел Улыбаюсь
Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines