Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Нахождение наибольшего пути, Помогите найти ошибку 
V
    Опции темы
sQu1rr
Дата 14.11.2010, 21:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
Дается лабиринт
X - стена
M - начало отсчета
. - пустое место

Проходить по пустотам можно только по общим граням ( если представить ввиде квадрата ) ( тоесть не по диагонали )
Нужно найти самое дальнее пустое место от начала отсчета и обозначить I

Дело в том что из 10 проверочных заданий 2 программе выполнить не удалось точно так же как и мне ошибку в ней.
Извеняйте, писал на скорую руку

Код

#include <fstream>
#include <vector>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
#include <iostream>

int arr[500][500];
char map[500][500];
int n, m;
void Circle( int x, int y, int num );

int main()
{
    int t, posX, posY, bigX, bigY;

    std::string file;
    std::cout << "Task number: ";
    std::cin >> file;

    std::ifstream ifile( ( "minotest." + file + ".sis" ).c_str() );
    ifile >> t >> n >> m;

    std::string line;
    std::getline( ifile, line );

    for( int i = 0; i < n; ++i )
    {
        std::getline( ifile, line );
        for( int j = 0; j < m; ++j )
        {
            map[i][j] = line[j];
            if( line[j] == 'M' )
            {
                posX = i;
                posY = j;
                continue;
            }
            arr[i][j] = ( line[j] == '.' ? 999666999 : -1 );
        }
    }

    ifile.close();

    Circle( posX, posY, 0 );

    int big = -1;
    for( int i = 0; i < n; ++i )
    {
        for( int j = 0; j < m; ++j )
        {
            if( arr[i][j] > big )
            {
                big = arr[i][j];
                bigX = i;
                bigY = j;
            }
        }
    }

    map[bigX][bigY] = 'I';

    std::ofstream ofile( ( "minotest." + file + ".val" ).c_str() );
    ofile << t << std::endl;
    for( int i = 0; i < n; ++i )
    {
        for( int j = 0; j < m; ++j )
            ofile << map[i][j];
        ofile << std::endl;
    }

    ofile.close();

    return 0;
}

void Circle( int x, int y, int num )
{
    if( arr[x][y] < num ) return;

    arr[x][y] = num;

    if( x > 0 ) Circle( x-1, y, num+1 );
    if( x < m-1 ) Circle( x+1, y, num+1 );
    if( y > 0 ) Circle( x, y-1, num+1 );
    if( y < n-1 ) Circle( x, y+1, num+1 );
}


Пример ввода ( первая строка: Номер задания, длина, высота )
Код

0 5 5
XXXXX
X...X
XXX.X
XM..X
XXXXX

Пример ответа ( первая строка: Номер задания )
Код

0
XXXXX
XI..X
XXX.X
XM..X
XXXXX


Этот, например решить не удалось ( да и правильного ответа я не знаю )
Код

3 27 29
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X.....X...X.X...X...........X
X.X.XXX.XXX.X.XXXXX.XXX.XXX.X
X.X.....X.X.....X...X.......X
XXX.XXXXX.X.XXX.X.X.X.XXX.XXX
X.X.....X.X...X...X.X.....X.X
X.XXXXX.X.X.XXX.XXX.XXXXXXX.X
X.X.X...X.....X...X...X...X.X
X.X.X.XXXXX.XXXXX.X.XXXXX.X.X
X.......X.X.......X.X.X.....X
X.X.X.X.X.X.XXXXXXXXX.XXX.X.X
X.X.X.X...X.....X...X.....X.X
X.XXX.XXXXXXX.XXX.X.X.XXX.X.X
X.X.X.....X.X.X...X.X.X...X.X
X.X.XXX.X.X.X.X.X.XXXXXXX.XXX
X.....X.X.....X.X.X.........X
XXXXX.XXX.X.XXXXX.X.XXX.XXX.X
X.X.......X.X.....XMX.....X.X
X.XXX.XXXXXXX.XXX.XXX.XXXXX.X
X.....X.....X...X.X.X.X.....X
X.X.X.X.XXXXX.XXX.X.X.X.XXXXX
X.X.X...X.....X...X.......X.X
X.X.X.XXX.XXXXX.XXX.X.X.XXX.X
X.X.X.......X...X...X.X.....X
X.XXX.XXX.X.XXX.XXX.XXX.X.X.X
X.X.....X.X.X.........X...X.X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX


Зааранее спасибо ;)
PM MAIL Skype GTalk   Вверх
DarkProg
Дата 14.11.2010, 21:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Законченный романтик
***


Профиль
Группа: Завсегдатай
Сообщений: 1784
Регистрация: 11.3.2009
Где: Земля

Репутация: нет
Всего: 19
Можно поинтересоваться - проблема ведь в том что программа виснет намертво при вот том втором тесте на который ответа нет, верно???


--------------------
"И твоя голова всегда в ответе за то куда сядет твой зад..."

"Я студент - скажите с какого я ВУЗа..."

 smile  smile  smile 
PM MAIL   Вверх
sQu1rr
Дата 14.11.2010, 21:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
Цитата(DarkProg @  14.11.2010,  21:28 Найти цитируемый пост)
Можно поинтересоваться - проблема ведь в том что программа виснет намертво при вот том втором тесте на который ответа нет, верно??? 

Программа дает ответ
Код

3
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X.....X...X.X...X..........IX
X.X.XXX.XXX.X.XXXXX.XXX.XXX.X
X.X.....X.X.....X...X.......X
XXX.XXXXX.X.XXX.X.X.X.XXX.XXX
X.X.....X.X...X...X.X.....X.X
X.XXXXX.X.X.XXX.XXX.XXXXXXX.X
X.X.X...X.....X...X...X...X.X
X.X.X.XXXXX.XXXXX.X.XXXXX.X.X
X.......X.X.......X.X.X.....X
X.X.X.X.X.X.XXXXXXXXX.XXX.X.X
X.X.X.X...X.....X...X.....X.X
X.XXX.XXXXXXX.XXX.X.X.XXX.X.X
X.X.X.....X.X.X...X.X.X...X.X
X.X.XXX.X.X.X.X.X.XXXXXXX.XXX
X.....X.X.....X.X.X.........X
XXXXX.XXX.X.XXXXX.X.XXX.XXX.X
X.X.......X.X.....XMX.....X.X
X.XXX.XXXXXXX.XXX.XXX.XXXXX.X
X.....X.....X...X.X.X.X.....X
X.X.X.X.XXXXX.XXX.X.X.X.XXXXX
X.X.X...X.....X...X.......X.X
X.X.X.XXX.XXXXX.XXX.X.X.XXX.X
X.X.X.......X...X...X.X.....X
X.XXX.XXX.X.XXX.XXX.XXX.X.X.X
X.X.....X.X.X.........X...X.X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Что не является верным
PM MAIL Skype GTalk   Вверх
sQu1rr
Дата 15.11.2010, 01:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
 smile 
Голова болит, разберусь завтра

Это сообщение отредактировал(а) sQu1rr - 15.11.2010, 01:38
PM MAIL Skype GTalk   Вверх
Леопольд
Дата 15.11.2010, 13:24 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13
Цитата(sQu1rr @  14.11.2010,  21:17 Найти цитируемый пост)
Проходить по пустотам можно только по общим граням ( если представить ввиде квадрата ) ( тоесть не по диагонали )
Нужно найти самое дальнее пустое место от начала отсчета и обозначить I
Что значит самое дальнее?
Я правильно понимаю, что надо найти все кратчайшие пути до всех точек (стартуя от заданной) и самый длинный путь ведёт к ответу?
Если да, то здесь подходит алгоритм A*.

Я как-то bаловался с ним.
Код
#ifndef ASTAR_SEARCH_HPP
#define ASTAR_SEARCH_HPP

#include <set>
#include <vector>
#include <algorithm>

#include <boost/scoped_ptr.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/foreach.hpp>

class AStarHiddenPlace{
    template<typename Node>
    struct EstimatedNode
    {
        EstimatedNode(Node const& node, Node const& goal, EstimatedNode const* parent) :
            m_node(node), m_parent(parent),
            m_hRealCost(parent == NULL ? Node::heurisicCost(node, node) :
                parent->m_hRealCost + Node::heurisicCost(parent->m_node, node)),
            m_hGoalCost(m_hRealCost + Node::heurisicCost(node, goal))
        {}

        Node m_node;
        EstimatedNode const* m_parent;
        typename Node::HCost m_hRealCost;
        typename Node::HCost m_hGoalCost;

        //! \brief used in std::set
        bool operator< (EstimatedNode const& rsh) const {return this->m_node < rsh.m_node;}

        //! \brief used to compare with the goal Node
        bool operator== (Node const& rsh) const { return this->m_node == rsh; }
        //! \brief used to compare with the goal Node
        bool operator!= (Node const& rsh) const { return !(this->m_node == rsh); }
    };

    template<typename T>
    struct HCostLess{
        bool operator() (T const& lsh, T const& rsh) const {return lsh.m_hGoalCost < rsh.m_hGoalCost;}
    };

    template<typename Node>
    friend boost::shared_ptr<std::vector<Node> > aStarSearch(Node const&, Node const&);
};

/////////////////////////////////////////////////
//! \brief A* algorithm implementation.
//!
//! \tparam
//! The Node type must correspond to STL container requirements.
//! and to the following interface:
//! "bool operator<(Node const&) const" to store in std::set
//! "bool operator ==(Node const&) const" to check equality of node state
//! "std::vector<Node> * expand() const" to expand a node
//! "struct Node::HCost" with "bool operator<", "Node::HCost operator+", "Node::HCost & operator="
//! "static Node::HCost heurisicCost(Node const& from, Node const& to)"
//!
//! \param starting node
//! \param goal node
//! \return path from the starting node to the goal node
/////////////////////////////////////////////////
template<typename Node>
boost::shared_ptr<std::vector<Node> > aStarSearch(Node const& start, Node const& goal)
{
    std::set<AStarHiddenPlace::EstimatedNode<Node> > discovered;
    typedef std::multiset<AStarHiddenPlace::EstimatedNode<Node>, AStarHiddenPlace::HCostLess<AStarHiddenPlace::EstimatedNode<Node> > >  EdgeT;
    EdgeT edge;

    typename EdgeT::const_iterator bestNode = edge.insert(AStarHiddenPlace::EstimatedNode<Node>(start, goal, NULL));

    boost::shared_ptr<std::vector<Node> > result(new std::vector<Node>);
    while(!edge.empty())
    {
        if(*bestNode == goal)
        {
            AStarHiddenPlace::EstimatedNode<Node> const* resNode = &(*bestNode);
            while(resNode != NULL)
            {
                result->push_back(resNode->m_node);
                resNode = resNode->m_parent;
            }
            std::reverse(result->begin(), result->end());
            return result;
        }

        boost::scoped_ptr<std::vector<Node> > expandedList(bestNode->m_node.expand());

        AStarHiddenPlace::EstimatedNode<Node> const* parent = &(*discovered.insert(*bestNode).first);

        edge.erase(bestNode);

        BOOST_FOREACH(Node const& node, *expandedList)
        {
            AStarHiddenPlace::EstimatedNode<Node> toEdge(node, goal, parent);
            if(discovered.insert(toEdge).second)
            {
                edge.insert(toEdge);
            }
        }

        bestNode = edge.begin();
    }

    return result;
} // end of aStarSearch

#endif //ASTAR_SEARCH_HPP

Node местоположение на карте. expand, возвращаёт все возможные передвижения из этой точки на один шаг, heuristic функция пусть считает расстояние от текущей точки (from) до цели (to) (лучше манхэтенское = |x2 - x1| + |y2 - y1|). В результате получаем полный путь от точки до цели в std::vector'e, его размер - 1 == длине пути (количеству нодов, по которым надо переходить). Если размер вектора == 0 (т.е. ни одного нода), значит цель недостижима.

Пятнашки, вот, решал. Если хочешь посмотреть результат, то компиляй с включенной оптимизацией, иначе долго придётся ждать. У пятнашек много разных комbинаций, а A* выливается в "поиск в ширину" если цель не достижима. Т.е. он переbерёт все варианты. На карте же, их столько, сколько достижимых пустых мест. За несколько милисекунд bудет решать.
Код
#include <iostream>
#include <iomanip>

#include "astar.hpp"

enum {SIDE = 4, FIELD = SIDE * SIDE};

std::size_t getIndex(std::size_t const (&state)[FIELD], std::size_t item)
{
    for(std::size_t i = 0; i < FIELD; ++i)
        if(state[i] == item) return i;
    return FIELD;
}

struct Node
{
    Node(std::size_t(&state)[FIELD]) {
        ::memcpy(this->m_state, state, FIELD * sizeof(std::size_t));
    }

    Node(Node const& rhs) {
        ::memcpy(this->m_state, rhs.m_state, FIELD * sizeof(std::size_t));
    }

    Node& operator= (Node const& rhs) {
        ::memcpy(this->m_state, rhs.m_state, FIELD * sizeof(std::size_t));
    }

    Node() {}

    std::size_t m_state[FIELD];

    bool operator<(Node const& rsh) const
    {
        for(std::size_t i = 0; i < FIELD; ++i)
        {
            if(this->m_state[i] < rsh.m_state[i]) return true;
        }
        return false;
    }

    bool operator ==(Node const& rsh) const
    {
        for(std::size_t i = 0; i < FIELD; ++i)
        {
            if(this->m_state[i] != rsh.m_state[i]) return false;
        }
        return true;
    }

    std::vector<Node> * expand() const
    {
        std::vector<Node> * result = new std::vector<Node>;

        std::size_t index = getIndex(this->m_state, 0);

        std::size_t col = index % SIDE;
        std::size_t row = index / SIDE;

        if(0 < col) // move left
        {
            std::size_t copyState[FIELD];
            ::memcpy(copyState, this->m_state, FIELD * sizeof(std::size_t));
            std::swap(copyState[index-1], copyState[index]);
            result->push_back(Node(copyState));
        }
        if(col < SIDE-1) // move right
        {
            std::size_t copyState[FIELD];
            ::memcpy(copyState, this->m_state, FIELD * sizeof(std::size_t));
            std::swap(copyState[index], copyState[index+1]);
            result->push_back(Node(copyState));
        }
        if(0 < row) // move up
        {
            std::size_t copyState[FIELD];
            ::memcpy(copyState, this->m_state, FIELD * sizeof(std::size_t));
            std::swap(copyState[index-SIDE], copyState[index]);
            result->push_back(Node(copyState));
        }
        if(row < SIDE-1) // move down
        {
            std::size_t copyState[FIELD];
            ::memcpy(copyState, this->m_state, FIELD * sizeof(std::size_t));
            std::swap(copyState[index], copyState[index+SIDE]);
            result->push_back(Node(copyState));
        }
        return result;
    }

    typedef std::size_t HCost;

    static Node::HCost heurisicCost(Node const& from, Node const& to)
    {
        std::size_t cost = 0;
        for(std::size_t i = 0; i < FIELD; ++i)
        {
            if(from.m_state[i] != 0 && from.m_state[i] != to.m_state[i])
            {
                std::size_t fromCol = i % SIDE;
                std::size_t fromRow = i / SIDE;
                std::size_t index = getIndex(to.m_state,from.m_state[i]);
                std::size_t toCol = index % SIDE;
                std::size_t toRow = index / SIDE;

                cost += fromCol < toCol ? toCol - fromCol : fromCol - toCol;
                cost += fromRow < toRow ? toRow - fromRow : fromRow - toRow;
            }
        }
        return cost;
    }

    void print() const
    {
        for(std::size_t i = 0; i < FIELD; ++i)
        {
            if(i % SIDE == 0) std::cout<<'\n';
            if(this->m_state[i] == 0)
            {
                std::cout<<"   ";
            }
            else
            {
                std::cout<<std::setw(3)<<this->m_state[i];
            }
        }
        std::cout<<"\n";
    }
};

std::size_t goal[FIELD] = {1, 2, 3, 4,
                           5, 6, 7, 8,
                           9, 10, 11, 12,
                           13, 14, 15, 0};

std::size_t start[FIELD] = {1, 12, 3, 7,
                            15, 2, 14, 4,
                            5, 6, 10, 8,
                            9, 13, 11, 0};

int main()
{
    boost::shared_ptr<std::vector<Node> > result = aStarSearch(Node(start), Node(goal));

    std::size_t i = 0;
    BOOST_FOREACH(Node const& item, *result)
    {
        std::cout<<"step "<<i++;
        item.print();
    }


    return 0;
}



Это сообщение отредактировал(а) Леопольд - 21.11.2010, 18:25


--------------------
вопросов больше чем ответов
PM MAIL   Вверх
Леопольд
Дата 15.11.2010, 14:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13
Цитата(sQu1rr @  14.11.2010,  21:40 Найти цитируемый пост)
Программа дает ответ ... Что не является верным 
Вылазит за ограниченную оbласть. Если я не ошиbся...



--------------------
вопросов больше чем ответов
PM MAIL   Вверх
sQu1rr
Дата 15.11.2010, 20:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
Цитата(Леопольд @  15.11.2010,  14:17 Найти цитируемый пост)
Вылазит за ограниченную оbласть. Если я не ошиbся...

Где, не подскажите? 10 раз код перепроверил smile


Цитата(Леопольд @  15.11.2010,  13:24 Найти цитируемый пост)
Я правильно понимаю, что надо найти все кратчайшие пути до всех точек (стартуя от заданной) и самый длинный путь ведёт к ответу?
Если да, то здесь подходит алгоритм A*.

Вы правильно понимаете, спасибо за алгоритм, буду изучать smile
PM MAIL Skype GTalk   Вверх
Леопольд
Дата 15.11.2010, 22:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13
Цитата(sQu1rr @  15.11.2010,  20:00 Найти цитируемый пост)
Где, не подскажите? 10 раз код перепроверил
Понятия не имею, я код не смотрел smile Я про результат говорил, к нему пути нет от стартовой точки, т.е. он нашёл недостижимую цель. Я бы сделал через А*. Порядок следующий, надо вызвать алгоритм поиска кратчайшего пути от точки до точки столько раз, сколько пустых полей, исключая стартовое. Все достижимые (с непустым результатом) отсоритовать по длинне пути. Взять с наибольшим пройденным путём.

Не очень производительно, но зато вполне понятно. 

Иначе, более производительно модифицировать алгоритм А* таким образом, что-бы он работал бесцельно. Т.е. дать ему пробежаться по всей достижимой области (об этом он сам позаботится). В результате (если heuristic функция нормальная) он вычислит расстояние до всех нодов (их сортировать по расстоянию),  начиная с ближайших  и заканчивая самыми дальними.  Взять самые удалённые, это и есть ответ. За границами достижимого, он не будет считать вообще.

От heuristic много зависит. Здесь наиболее всего подходит "Манхэтенское расстояние".
|x2 - x1| + |y2 - y1|

Это сообщение отредактировал(а) Леопольд - 16.11.2010, 02:42


--------------------
вопросов больше чем ответов
PM MAIL   Вверх
sQu1rr
Дата 15.11.2010, 23:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
Цитата(Леопольд @  15.11.2010,  22:15 Найти цитируемый пост)
Я про результат говорил, к нему пути нет от стартовой точки, т.е. он нашёл недостижимую цель

Как нету? есть smile


Цитата(Леопольд @  15.11.2010,  22:15 Найти цитируемый пост)
Я бы сделал через А*

Я изучаю какраз его

Цитата(Леопольд @  15.11.2010,  22:15 Найти цитируемый пост)
Не очень производительно, но зато вполне понятно. 

Мне здесь она и не нужна

Цитата(Леопольд @  15.11.2010,  22:15 Найти цитируемый пост)
Иначе, более производительно модифицировать алгоритм А* таким образом, что-бы он искал недостижимую цель.

Всмысле? зачем искать недостежимую цель?
PM MAIL Skype GTalk   Вверх
Леопольд
Дата 16.11.2010, 02:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13
Цитата(sQu1rr @  15.11.2010,  23:08 Найти цитируемый пост)
Всмысле? зачем искать недостежимую цель? 
Перефразировал...

Добавлено через 2 минуты и 58 секунд
Цитата(sQu1rr @  15.11.2010,  23:08 Найти цитируемый пост)
Как нету? есть 
Не могу найти...



--------------------
вопросов больше чем ответов
PM MAIL   Вверх
sQu1rr
Дата 16.11.2010, 02:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
Цитата(Леопольд @  16.11.2010,  02:03 Найти цитируемый пост)
Перефразировал...


Цитата(Леопольд @  15.11.2010,  22:15 Найти цитируемый пост)
 Т.е. дать ему пробежаться по всей достижимой области (об этом он сам позаботится). В результате (если heuristic функция нормальная) он вычислит расстояние до всех нодов (их сортировать по расстоянию),  начиная с ближайших  и заканчивая самыми дальними (только в достижимом пространстве). 


Что за достижимое / недастижимое пространство? Вроде все пути достижимы  smile 
PM MAIL Skype GTalk   Вверх
Леопольд
Дата 16.11.2010, 02:37 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13
Цитата(sQu1rr @  16.11.2010,  02:07 Найти цитируемый пост)
Что за достижимое / недастижимое пространство?
Код
XXXXXXXXX
XM......X
XXXXXX.XX
XI..X...X
XXXXXXXXX
Здесь нельзя пройти от точки М до точки I. Т.е. нет пути...

Это сообщение отредактировал(а) Леопольд - 16.11.2010, 02:40


--------------------
вопросов больше чем ответов
PM MAIL   Вверх
sQu1rr
Дата 16.11.2010, 08:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
Цитата(Леопольд @  16.11.2010,  02:37 Найти цитируемый пост)
Здесь нельзя пройти от точки М до точки I. Т.е. нет пути...

Ладно, предположим, я понял и  первого раза, просто, сразу оговорка: к любой пустой клетке есть путь. А так да, для общего случая, вы, конечно, правы  smile 
PM MAIL Skype GTalk   Вверх
Леопольд
Дата 16.11.2010, 10:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13
Цитата(Леопольд @  15.11.2010,  22:15 Найти цитируемый пост)
Иначе, более производительно модифицировать алгоритм А* таким образом, что-бы он работал бесцельно. Т.е. дать ему пробежаться по всей достижимой области (об этом он сам позаботится). В результате (если heuristic функция нормальная) он вычислит расстояние до всех нодов (их сортировать по расстоянию),  начиная с ближайших  и заканчивая самыми дальними.  Взять самые удалённые, это и есть ответ. За границами достижимого, он не будет считать вообще.

От heuristic много зависит. Здесь наиболее всего подходит "Манхэтенское расстояние".
|x2 - x1| + |y2 - y1|
Что-то я перемудрил тут, heuristic не нужна. A* bез  heuristic это просто поиск в ширину, он всё решит. 
Т.е. А*, конечно, интересен, но здесь он не нужен, он полезен при поиске кратчайшего пути из точки в точку (старт и цель).

Алгоритм поясню на примере:
Код
#include <limits>

// XXXXXX
// XXXX.X
// XM...X
// X.XX.X
// XXXXXX
char map[][6] =
{
    {'X','X','X','X','X','X'},
    {'X','X','X','X','.','X'},
    {'X','М','.','.','.','X'},
    {'X','.','X','X','.','X'},
    {'X','X','X','X','X','X'}
};

unsigned const uMax = std::numeric_limits<unsigned>::max();

unsigned distances[][6] =
{
    {uMax,uMax,uMax,uMax,uMax,uMax},
    {uMax,uMax,uMax,uMax,uMax,uMax},
    {uMax,0,uMax,uMax,uMax,uMax},
    {uMax,uMax,uMax,uMax,uMax,uMax},
    {uMax,uMax,uMax,uMax,uMax,uMax},
};
На вход идёт вектор, содержащий один элемент, координаты начальной точки {map[2][1]}. Порождаем из этой точки новые две, в которые можно перейти по карте: map[2][2] и map[3][1] (лучше вынести это в отдельную функцию expand). Расстояние до них равно дистанции до текущей точки distances[x][y] + 1 шаг (distances[2][1] == 0) . Проверяем каждую "новую" точку: если в distances по её координатам стоит значение uMax, заменяем его на расстояние до точки и сохраняем её координаты в std::vector, который перейдёт на следующую итерацию.
На следующей итерации bерём полученный вектор {map[2][2], map[3][1]} и проводим ту же процедуру со всеми точками из него. Если опять получен непустой вектор точек, то продолжаем раbотать с ним, если получен пустой, то в текущем векторе содержится результат.

Конкретно в этом случае bудет раbотать так:
Код
{map[2][1]} (dist == 0)            -> {map[2][2], map[3][1]} (dist == 1)
{map[2][2], map[3][1]} (dist == 1) -> {map[2][3]} (dist == 2)
{map[2][3]} (dist == 2)            -> {map[2][4]} (dist == 3)
{map[2][4]} (dist == 3)            -> {map[1][4], map[3][4]} (dist == 4)
{map[1][4], map[3][4]} (dist == 4) -> {}


Это и есть поиск в ширину (полный переbор). Решение получено в один проход. Как сделать bыстрее, не знаю.
Ещё есть ограничение на допустимое максимальное расстояние: оно  не должно превышать uMax - 1.


Это сообщение отредактировал(а) Леопольд - 16.11.2010, 21:53


--------------------
вопросов больше чем ответов
PM MAIL   Вверх
sQu1rr
Дата 16.11.2010, 15:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13
Цитата(Леопольд @  16.11.2010,  10:28 Найти цитируемый пост)
На вход идёт вектор, содержащий один элемент, координаты начальной точки {map[2][1]}. Порождаем из этой точки новые две, в которые можно перейти по карте: map[2][2] и map[3][1] (лучше вынести это в отдельную функцию expand). Расстояние до них равно дистанции до текущей точки distances[x][y] + 1 шаг (distances[2][1] == 0) . Проверяем каждую "новую" точку: если в distances по её координатам стоит значение uMax, заменяем его на расстояние до точки и сохраняем её координаты в std::vector, который перейдёт на следующую итерацию.
На следующей итерации bерём полученный вектор {map[2][2], map[3][1]} и проводим ту же процедуру со всеми точками из него. Если опять получен непустой вектор точек, то продолжаем раbотать с ним, если получен пустой, то в текущем векторе содержится результат.


Примерно тот же алгоритм, я и использовал, за исключением того что выполнил в рекурсии smile
НО ТАМ ЕСТЬ ОШИБКА!  smile 
PM MAIL Skype GTalk   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1037 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.