Полная версия этой страницы: Intelligent scissors
Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)
Какой алгоритм ?
Цитата(Алексей1153 @ 20.8.2010, 17:32) 
Какой алгоритм ?
Название сабжа
ааа, вона чего... То есть выбор произвольной замкнутой области на битмапе
wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации
wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации
Цитата(Алексей1153 @ 20.8.2010, 20:19)
ааа, вона чего... То есть выбор произвольной замкнутой области на битмапе
wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации
wiz29, ну дык, словесный алгоритм и саму реализацию - в студию попросим ) Для оптимизации
нет, ты говоришь про так называемый Magic Wand алгоритм , здесь другой алгоритм, просто хотел проконсультироваться с человеком который вероятно сталкивался с ним. Материала слишком много , чтобы писать в посте, поэтому и написал ("Если кто то сталкивался").
Последнюю реализацию я смог ускорить в 5 раз, но время решения всеравно занимает порядка 1сек на моей не медленной машине, хотелось бы быстрее
приведи код реализации, посмотрим.
Раскрывающийся текст
namespace liveware
{
//solve for seed point with coord (xSeed, ySeed)
void Dijkstra(ImageGraph& graph, int xSeed, int ySeed);
}//namespace liveware
namespace liveware
{
//---------------------------------------------------------------------------------------------------------
enum NodeSate
{
NONE = 0x00, //if node was not processed
PROCESSED = 0x01, //node was processed
ACTIVE = 0x02 //node in active queue
};
//---------------------------------------------------------------------------------------------------------
//functor
//reset all calc dijkstra data
class cleanGraph
{
public:
void operator()(GraphNode* pNode)
{
if (pNode)
{
pNode->SetState(NONE);//reset state
pNode->SetPrevNode(NULL);//reset prev node
pNode->SetWeight(1.0e+10);//set "infinite" weight
}
}
};
//---------------------------------------------------------------------------------------------------------
//functor
//calculate transit cost for neighborhood nodes
class calcCost
{
public:
calcCost(PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& pq,
GraphNode* pCurrNode)
: m_pq(pq)
, m_pCurrNode(pCurrNode)
{
}
~calcCost()
{
}
public:
void operator()(std::pair<GraphNode*, double>& pDstNodeData)
{
GraphNode* pNode(pDstNodeData.first);
if (!(pNode->state() & PROCESSED))
{
double localCost(m_pCurrNode->Weight() + pDstNodeData.second);
if (!(pNode->state() & ACTIVE))
{//node is not in queue
pNode->SetWeight(localCost);
pNode->SetPrevNode(m_pCurrNode);
m_pq.push(pNode);
pNode->SetState(ACTIVE);
}
else if (localCost < pNode->Weight())
{//node already in queue
pNode->SetWeight(localCost);
pNode->SetPrevNode(m_pCurrNode);
m_pq.update();
}
}
}
private:
PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& m_pq;
GraphNode* m_pCurrNode;
};
//---------------------------------------------------------------------------------------------------------
//solve for seed point with coord (xSeed, ySeed)
void Dijkstra(ImageGraph& graph, int xSeed, int ySeed)
{
std::for_each(graph.Begin(), graph.End(), cleanGraph());//clean all dijkstra data
PriorityQueue<GraphNode*, std::vector<GraphNode*>, less> pq;//construct empty priority queue
//of active nodes
GraphNode* pCurr(graph.ElementAt(xSeed, ySeed));//take seed node
pCurr->SetWeight(0.0);
pq.push(pCurr);//push seed node into queue
pCurr->SetState(ACTIVE);//set active node state
while(!pq.empty())
{
pCurr = pq.top();
pq.pop();
pCurr->SetState(PROCESSED);
std::for_each(pCurr->NeighborhoodBegin(), pCurr->NeighborhoodEnd(),
calcCost(pq, pCurr));
}
}
//---------------------------------------------------------------------------------------------------------
}//namespace livewareблин нелзя файлы почемуто прикрепить
оберни плз в тег code, чтобы читабельность сохранилась, а то без indent'ов сложно воспринимать
в zip-архиве можно )
CODE
#ifndef LWSOLVE_H
#define LWSOLVE_H
#include "lwimagegraph.h"
namespace liveware
{
//solve for seed point with coord (xSeed, ySeed)
void Dijkstra(ImageGraph& graph, int xSeed, int ySeed);
}//namespace liveware
#endif //LWSOLVE_H
#include "lwsolve.h"
#include "lwpriorityqueue.h"
#include <algorithm>
#include <functional>
#include <QDebug>
namespace liveware
{
//---------------------------------------------------------------------------------------------------------
enum NodeSate
{
NONE = 0x00, //if node was not processed
PROCESSED = 0x01, //node was processed
ACTIVE = 0x02 //node in active queue
};
//---------------------------------------------------------------------------------------------------------
//functor
//reset all calc dijkstra data
class cleanGraph
{
public:
void operator()(GraphNode* pNode)
{
if (pNode)
{
pNode->SetState(NONE);//reset state
pNode->SetPrevNode(NULL);//reset prev node
pNode->SetWeight(1.0e+10);//set "infinite" weight
}
}
};
//---------------------------------------------------------------------------------------------------------
//functor
//calculate transit cost for neighborhood nodes
class calcCost
{
public:
calcCost(PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& pq,
GraphNode* pCurrNode)
: m_pq(pq)
, m_pCurrNode(pCurrNode)
{
}
~calcCost()
{
}
public:
void operator()(std::pair<GraphNode*, double>& pDstNodeData)
{
GraphNode* pNode(pDstNodeData.first);
if (!(pNode->state() & PROCESSED))
{
double localCost(m_pCurrNode->Weight() + pDstNodeData.second);
if (!(pNode->state() & ACTIVE))
{//node is not in queue
pNode->SetWeight(localCost);
pNode->SetPrevNode(m_pCurrNode);
m_pq.push(pNode);
pNode->SetState(ACTIVE);
}
else if (localCost < pNode->Weight())
{//node already in queue
pNode->SetWeight(localCost);
pNode->SetPrevNode(m_pCurrNode);
m_pq.update();
}
}
}
private:
PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& m_pq;
GraphNode* m_pCurrNode;
};
//---------------------------------------------------------------------------------------------------------
//solve for seed point with coord (xSeed, ySeed)
void Dijkstra(ImageGraph& graph, int xSeed, int ySeed)
{
std::for_each(graph.Begin(), graph.End(), cleanGraph());//clean all dijkstra data
PriorityQueue<GraphNode*, std::vector<GraphNode*>, less> pq;//construct empty priority queue
//of active nodes
GraphNode* pCurr(graph.ElementAt(xSeed, ySeed));//take seed node
pCurr->SetWeight(0.0);
pq.push(pCurr);//push seed node into queue
pCurr->SetState(ACTIVE);//set active node state
while(!pq.empty())
{
pCurr = pq.top();
pq.pop();
pCurr->SetState(PROCESSED);
std::for_each(pCurr->NeighborhoodBegin(), pCurr->NeighborhoodEnd(),
calcCost(pq, pCurr));
}
}
//---------------------------------------------------------------------------------------------------------
}//namespace liveware
#define LWSOLVE_H
#include "lwimagegraph.h"
namespace liveware
{
//solve for seed point with coord (xSeed, ySeed)
void Dijkstra(ImageGraph& graph, int xSeed, int ySeed);
}//namespace liveware
#endif //LWSOLVE_H
#include "lwsolve.h"
#include "lwpriorityqueue.h"
#include <algorithm>
#include <functional>
#include <QDebug>
namespace liveware
{
//---------------------------------------------------------------------------------------------------------
enum NodeSate
{
NONE = 0x00, //if node was not processed
PROCESSED = 0x01, //node was processed
ACTIVE = 0x02 //node in active queue
};
//---------------------------------------------------------------------------------------------------------
//functor
//reset all calc dijkstra data
class cleanGraph
{
public:
void operator()(GraphNode* pNode)
{
if (pNode)
{
pNode->SetState(NONE);//reset state
pNode->SetPrevNode(NULL);//reset prev node
pNode->SetWeight(1.0e+10);//set "infinite" weight
}
}
};
//---------------------------------------------------------------------------------------------------------
//functor
//calculate transit cost for neighborhood nodes
class calcCost
{
public:
calcCost(PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& pq,
GraphNode* pCurrNode)
: m_pq(pq)
, m_pCurrNode(pCurrNode)
{
}
~calcCost()
{
}
public:
void operator()(std::pair<GraphNode*, double>& pDstNodeData)
{
GraphNode* pNode(pDstNodeData.first);
if (!(pNode->state() & PROCESSED))
{
double localCost(m_pCurrNode->Weight() + pDstNodeData.second);
if (!(pNode->state() & ACTIVE))
{//node is not in queue
pNode->SetWeight(localCost);
pNode->SetPrevNode(m_pCurrNode);
m_pq.push(pNode);
pNode->SetState(ACTIVE);
}
else if (localCost < pNode->Weight())
{//node already in queue
pNode->SetWeight(localCost);
pNode->SetPrevNode(m_pCurrNode);
m_pq.update();
}
}
}
private:
PriorityQueue<GraphNode*, std::vector<GraphNode*>, less>& m_pq;
GraphNode* m_pCurrNode;
};
//---------------------------------------------------------------------------------------------------------
//solve for seed point with coord (xSeed, ySeed)
void Dijkstra(ImageGraph& graph, int xSeed, int ySeed)
{
std::for_each(graph.Begin(), graph.End(), cleanGraph());//clean all dijkstra data
PriorityQueue<GraphNode*, std::vector<GraphNode*>, less> pq;//construct empty priority queue
//of active nodes
GraphNode* pCurr(graph.ElementAt(xSeed, ySeed));//take seed node
pCurr->SetWeight(0.0);
pq.push(pCurr);//push seed node into queue
pCurr->SetState(ACTIVE);//set active node state
while(!pq.empty())
{
pCurr = pq.top();
pq.pop();
pCurr->SetState(PROCESSED);
std::for_each(pCurr->NeighborhoodBegin(), pCurr->NeighborhoodEnd(),
calcCost(pq, pCurr));
}
}
//---------------------------------------------------------------------------------------------------------
}//namespace liveware
если кому интересна данная задача могуть дать литературу
блин, интересно, конечно, но сейчас вапще некогда ((( А так бы посидел поковырялся
И покажи код где ты этот алгоритм запускаешь и какие в него данные.
Пока косо смотрю на дейкстру, не думаю что это лучший вариант когда вычисляется не маршрут.
Пока косо смотрю на дейкстру, не думаю что это лучший вариант когда вычисляется не маршрут.
Здесь именно вычисляется маршрут от SeedNode до всех осталных вершин
от SeedNode до всех осталных вершинCODE
namespace liveware
{
class ImageGraph
{
public:
typedef std::vector<GraphNode*>::iterator iterator;
typedef std::vector<GraphNode*>::const_iterator const_iterator;
public:
ImageGraph(void);
~ImageGraph(void);
public:
//set size for image graph
void SetSize(int w, int h);
//return begin iterator for ImageGraph
iterator Begin();
//return begin iterator for ImageGraph
const_iterator Begin() const;
//return end iterator for ImageGraph
iterator End();
//return end iterator for ImageGraph
const_iterator End() const;
//return elemet count of ImageGraph
size_t GetSize() const;
//return width of ImageGraph
int GetWidth() const;
//return height of ImageGraph
int GetHeight() const;
//return element at cell
GraphNode* ElementAt(int x, int y);
GraphNode* ElementAt(int index);
//make image graph from QImage
bool LoadImage(const QImage& img);
private:
//release resources
void release();
private:
int m_w;//width of image graph
int m_h;//height of image graph
std::vector<GraphNode*> m_nodes;//image graph nodes
};//class ImageGraph
}//namespace liveware
namespace liveware
{
class less;
class ImageGraph;
class GraphNode
{
public:
friend class liveware::less;
friend class liveware::ImageGraph;
//first param of pair is dst node
//second param of pair is transition cost to dst node
typedef std::vector<std::pair<GraphNode*, double> > NeighboorhoodContainer;
typedef NeighboorhoodContainer::iterator iterator;
typedef NeighboorhoodContainer::const_iterator const_iterator;
public:
GraphNode(double weight = 0.0);
~GraphNode();
public:
//return x coord of node
int GetX() const;
//return y coord of node
int GetY() const;
//set x coord of node
void SetX(int);
//set y coord of node
void SetY(int);
//set x, y coord of node
void SetXY(int x, int y);
//set state of node (used for live ware)
void SetState(int);
//return state of node
int state() const;
//set weight of node
void SetWeight(double);
//return const reference for node weight
double Weight() const;
//return itertor for first neighborhood node
iterator NeighborhoodBegin();
//return const itertor for first neighborhood node
const_iterator NeighborhoodBegin() const;
//return iterator for end neighborhood node
iterator NeighborhoodEnd();
//return const iterator for end neighborhood node
const_iterator NeighborhoodEnd() const;
//return prev Node (for solve)
GraphNode* PrevNode();
//set prev Node
void SetPrevNode(GraphNode*);
private:
int m_x;//x coord of node
int m_y;//y coord of node
int m_state;// node state (for live ware algo)
double m_weight;//node weight (total cost of path to this node)
GraphNode* m_pPrevNode;//pointer to prev graph node (for liveware algo)
NeighboorhoodContainer m_neighborhood;//list of neighborhood (for liveware algo),
//second parametr is cost of transition from this node to
};//class GraphNode
//---------------------------------------------------------------------------------------------------------
//predicate
class less
: public std::binary_function<GraphNode*, GraphNode*, bool>
{
public:
bool operator()(const GraphNode* pNode1, const GraphNode* pNode2);
};//class less
}//namespace liveware
{
class ImageGraph
{
public:
typedef std::vector<GraphNode*>::iterator iterator;
typedef std::vector<GraphNode*>::const_iterator const_iterator;
public:
ImageGraph(void);
~ImageGraph(void);
public:
//set size for image graph
void SetSize(int w, int h);
//return begin iterator for ImageGraph
iterator Begin();
//return begin iterator for ImageGraph
const_iterator Begin() const;
//return end iterator for ImageGraph
iterator End();
//return end iterator for ImageGraph
const_iterator End() const;
//return elemet count of ImageGraph
size_t GetSize() const;
//return width of ImageGraph
int GetWidth() const;
//return height of ImageGraph
int GetHeight() const;
//return element at cell
GraphNode* ElementAt(int x, int y);
GraphNode* ElementAt(int index);
//make image graph from QImage
bool LoadImage(const QImage& img);
private:
//release resources
void release();
private:
int m_w;//width of image graph
int m_h;//height of image graph
std::vector<GraphNode*> m_nodes;//image graph nodes
};//class ImageGraph
}//namespace liveware
namespace liveware
{
class less;
class ImageGraph;
class GraphNode
{
public:
friend class liveware::less;
friend class liveware::ImageGraph;
//first param of pair is dst node
//second param of pair is transition cost to dst node
typedef std::vector<std::pair<GraphNode*, double> > NeighboorhoodContainer;
typedef NeighboorhoodContainer::iterator iterator;
typedef NeighboorhoodContainer::const_iterator const_iterator;
public:
GraphNode(double weight = 0.0);
~GraphNode();
public:
//return x coord of node
int GetX() const;
//return y coord of node
int GetY() const;
//set x coord of node
void SetX(int);
//set y coord of node
void SetY(int);
//set x, y coord of node
void SetXY(int x, int y);
//set state of node (used for live ware)
void SetState(int);
//return state of node
int state() const;
//set weight of node
void SetWeight(double);
//return const reference for node weight
double Weight() const;
//return itertor for first neighborhood node
iterator NeighborhoodBegin();
//return const itertor for first neighborhood node
const_iterator NeighborhoodBegin() const;
//return iterator for end neighborhood node
iterator NeighborhoodEnd();
//return const iterator for end neighborhood node
const_iterator NeighborhoodEnd() const;
//return prev Node (for solve)
GraphNode* PrevNode();
//set prev Node
void SetPrevNode(GraphNode*);
private:
int m_x;//x coord of node
int m_y;//y coord of node
int m_state;// node state (for live ware algo)
double m_weight;//node weight (total cost of path to this node)
GraphNode* m_pPrevNode;//pointer to prev graph node (for liveware algo)
NeighboorhoodContainer m_neighborhood;//list of neighborhood (for liveware algo),
//second parametr is cost of transition from this node to
};//class GraphNode
//---------------------------------------------------------------------------------------------------------
//predicate
class less
: public std::binary_function<GraphNode*, GraphNode*, bool>
{
public:
bool operator()(const GraphNode* pNode1, const GraphNode* pNode2);
};//class less
}//namespace liveware
а SeedNode всегда одна?
т.е. можно увидеть как процесс алгоритма запускается на практике и какие данные в него кидаются? Сложно смотреть сам алгоритм в отрыве, нужно в голове реальную ситуацию прокрутить.
т.е. можно увидеть как процесс алгоритма запускается на практике и какие данные в него кидаются? Сложно смотреть сам алгоритм в отрыве, нужно в голове реальную ситуацию прокрутить.
Сейчас, расскажу как на практике, всю задачу как ты понимаешь решает алгоритм дейкстры.
На вход ему подается 3 параметра ImageGraph - взвешенный граф изображения и хSeed, ySeed это координаты затравочной точки.
Дальше дейкстра находит кратчайшие пути к каждой из вершин графа от затравочной. ImageGraph строится по картинке например QImage, число вершин графа соответсвует количеству пикселей изображения. Пути после очень просто построить к затравочной точке, взять любой GraphNode и спустится по PrevNode к затаравочной точке (PrevNode затравочной точки равен 0) вот так на практике. Как вычисляются веса это уже соответсвует качеству того или иного алгоритма.
На вход ему подается 3 параметра ImageGraph - взвешенный граф изображения и хSeed, ySeed это координаты затравочной точки.
Дальше дейкстра находит кратчайшие пути к каждой из вершин графа от затравочной. ImageGraph строится по картинке например QImage, число вершин графа соответсвует количеству пикселей изображения. Пути после очень просто построить к затравочной точке, взять любой GraphNode и спустится по PrevNode к затаравочной точке (PrevNode затравочной точки равен 0) вот так на практике. Как вычисляются веса это уже соответсвует качеству того или иного алгоритма.
а что происходит после того, как кратчайшие пути построены? Что обратный путь построить можно из любой это понятно, но зачем? Т.е. что алгоритм делает дальше?
второе - как вычисляются веса? Сама идея.
второе - как вычисляются веса? Сама идея.
Если ты видел в фотошопе магнетик лассо, то он основан именно на этом алгоритме Дальше просто стораятся траетории от заданной вершины к Затравочной. как вычисляются веса почитай вот тут http://cgm.computergraphics.ru/content/view/172 (там весьма бщие сведения правда))
в статье есть ряд неточностей но они больше касаюся формул, идея думаю там будет понятна
вот еще одна очень наглядная статья http://www.cs.washington.edu/education/cou...t1/project1.htm сейчас вычисление весов взято отсюда, но это не главное в данной задаче.
Дальше просто стораятся траетории от заданной вершины к Затравочной. как вычисляются веса почитай вот тут http://cgm.computergraphics.ru/content/view/172 (там весьма бщие сведения правда))в статье есть ряд неточностей но они больше касаюся формул, идея думаю там будет понятна
вот еще одна очень наглядная статья http://www.cs.washington.edu/education/cou...t1/project1.htm сейчас вычисление весов взято отсюда, но это не главное в данной задаче.
ну вот смотри, промелькнуло название "заданная вершина". Как вывод, нас интересуют кратчайшие маршруты от этих точек до затравочной. Как вариант, возможно использование A*, либо алгоритм Флойда. Во втором случае мы получаем уже просчитанную матрицу, поэтому для всех заданных вершин значения будут вычислены, а не считаться "до затравочной" - это как минимум снижает объем вычислений. В первом - вычисление всей матрицы становится нафиг не нужно, но возникает определенная погрешность, вызываемая эвристической функцией (но здесь нужно продумать правильно эвристику, возможно вариант будет очень быстрым).
А сколько "заданных вершин" участвуют в алгоритме? Т.е. откуда они беруться? Это те пиксели где пользователь провел пером?
про вычисление весов спрашивал в том контексте, что нельзя ли матрицу "сжать" по размером, не слишком теряя точность.
еще попробуй поставь вывод счетчиков времени на каждый кусок алгоритма, т.е. после каждой важной части (к примеру - а) просчет матрицы Дейкстры б) просчет кратчайших путей от заданных точек в) ... ), тогда можно сразу увидеть что сколько занимает времени и что нужно оптимизировать.
А сколько "заданных вершин" участвуют в алгоритме? Т.е. откуда они беруться? Это те пиксели где пользователь провел пером?
про вычисление весов спрашивал в том контексте, что нельзя ли матрицу "сжать" по размером, не слишком теряя точность.
еще попробуй поставь вывод счетчиков времени на каждый кусок алгоритма, т.е. после каждой важной части (к примеру - а) просчет матрицы Дейкстры б) просчет кратчайших путей от заданных точек в) ... ), тогда можно сразу увидеть что сколько занимает времени и что нужно оптимизировать.
1. в алгоритме участвует 1 заданная вершина (затравачная) и 1 (любая) вершина выбранная пользователем (для построения пути).
2. матрица весов не вычисляется каждый раз (ее вычисление производится толко при создании ImageGraph 1раз)
Есть один ньюанс переход из 1->2 не обязательно будет совпадать по стоимости с переходом из 2->1
я тестил профайлером
построение путей в решенной задаче занимает << времени чем решение задачи
2. матрица весов не вычисляется каждый раз (ее вычисление производится толко при создании ImageGraph 1раз)
Есть один ньюанс переход из 1->2 не обязательно будет совпадать по стоимости с переходом из 2->1
я тестил профайлером
построение путей в решенной задаче занимает << времени чем решение задачи
а теперь поподробнее про ньюанс. В чем конкретно он выражается, если веса просчитаны? Что-то еще влияет на маршрут?
если учавствуют всего две вершины, то путь находится куда быстрее именно алгоритмом A*, тем более на больших полях где число точек глобально. Я его использую на гпс навигаторах для прокладки маршрута по десяткам тысяч точек и работает - секунды, на компе - менее полсекунды на самых диких атласах. Могу скинуть код-схему алгоритма.
ну если отставить пути, то что занимает большее количество времени? Какая часть? Как я понял, основные части:
1. просчет весов графа
2. построение путей
3. что-то дальше
какие пропорции по временным затратам?
если учавствуют всего две вершины, то путь находится куда быстрее именно алгоритмом A*, тем более на больших полях где число точек глобально. Я его использую на гпс навигаторах для прокладки маршрута по десяткам тысяч точек и работает - секунды, на компе - менее полсекунды на самых диких атласах. Могу скинуть код-схему алгоритма.
ну если отставить пути, то что занимает большее количество времени? Какая часть? Как я понял, основные части:
1. просчет весов графа
2. построение путей
3. что-то дальше
какие пропорции по временным затратам?
переход и вершины "а" в вершину "b" стоит не столько же сколькоперехо из "b" в "a" ребра имеют 2 направления
и альго Флойда здесь не совсем подойдет т.к. его сложность O(n^3) тогда как Дейкстра решает задачу за O(n^2 + m) m-число ребер (это самая плохая оценка для Дейкстры)
Хех, круто зато Флойд паралелится спс за подсказку
и альго Флойда здесь не совсем подойдет т.к. его сложность O(n^3) тогда как Дейкстра решает задачу за O(n^2 + m) m-число ребер (это самая плохая оценка для Дейкстры)
Хех, круто зато Флойд паралелится
спс за подсказку
с Флойдом сразу "отпало" как только речь зашла о двух вершинах - в таких случаях обычно играют роль алгоритмы более узкого назначения.
по весам понял, т.е. путь из b в a может быть не кратчайшим, просто совпадает с из а в b.
по весам понял, т.е. путь из b в a может быть не кратчайшим, просто совпадает с из а в b.
Самая критичная операция именно решение дейкстры, на моей машине рассчитывается порядка 0.8 сек (это дороговато)
Если могешь, скинь А* просто ничего про него не слышал
Если могешь, скинь А* просто ничего про него не слышал
А просчет дейкстры - это как раз часть прокладки маршрута, поэтому я об этом речь и завел.
A* - наверное самый популярный алгоритм в геймдеве. Описание ниже. Если нужно, могу скинуть код с классами для Open, Closed и сам алгоритм в Qt.
A* - наверное самый популярный алгоритм в геймдеве. Описание ниже. Если нужно, могу скинуть код с классами для Open, Closed и сам алгоритм в Qt.
/*
приоритетная очередь Open
список Closed
ПоискАЗвездочка
s.g = 0 // s - стартовый узел
s.h = ЭвристическаяОценка( s )
s.f = s.g + s.h
s.родитель = null
добавить s в Open
пока очередь Open не пуста
извлечь n из Open // n - узел с наименьшей стоимость в Open
если n целевой узел
сконструировать путь
выйти с кодом "успешное завершение"
для каждого наследника n' узла n
newg = n.g + стоимость(n,n')
если n' в Open или Closed, и n'.g <= newg
пропустить n'
n'.родитель = n
n'.g = newg
n'.h = ЭвристическаяОценка( n' )
n'.f = n'.g + n'.h
если n' в Closed
удалить n' из Closed
если n' не в Open
положить n' в Open
положить n в Closed
выйти с кодом "путь не найден"
*/
А можешь сказать временную сложность?
Вся суть сего алгоритма - в правильном задании эвристической оценки, здесь нужно подумать. Сокращает работу алгоритма просто в десятки и сотни раз. А если про нее забыть - это будет обычный обход графа в ширину.
На вики есть описание
к примеру, ситуация на практике - 70к вершин, 100к ребер. Прокладка из А в Б "обход в ширину" - около 45к итераций, через А* - около 700. Дейкстру использовать на мобильных девайсах предполагается невозможным, поэтому это чисто практика работы с GPS маршрутами.
На вики есть описание
к примеру, ситуация на практике - 70к вершин, 100к ребер. Прокладка из А в Б "обход в ширину" - около 45к итераций, через А* - около 700. Дейкстру использовать на мобильных девайсах предполагается невозможным, поэтому это чисто практика работы с GPS маршрутами.
ну у меня количиства измеряются через 1М+ порядка ну или около того это по вершинам.
надо попробовать твой алгоритм, тем более что у меня есть статья как вычислять эвристики
ну или около того это по вершинам.надо попробовать твой алгоритм, тем более что у меня есть статья как вычислять эвристики
ну по атласам у меня тоже миллионные значения идут, но там в моем случае уже идет разбивка на три уровня графов ))
вычисление эвристики если у тебя по данной теме - дак тем более здорово должно быть. А дейкстра реально не имеет смысла на таких значениях - 0.8 сек - это слишком много, особенно для декстопа.
с эвристикой еще так - чем она выше (т.е. ее роль), тем больше погрешность. Чем ниже - тем точнее. С этим всегда можно играть, добиваясь разнообразных результатов.
вычисление эвристики если у тебя по данной теме - дак тем более здорово должно быть. А дейкстра реально не имеет смысла на таких значениях - 0.8 сек - это слишком много, особенно для декстопа.
с эвристикой еще так - чем она выше (т.е. ее роль), тем больше погрешность. Чем ниже - тем точнее. С этим всегда можно играть, добиваясь разнообразных результатов.
Если положить h(x) = 0 для всех вершин, то мы получим ещё один специальный случай — алгоритм Дейкстры.
а ты очередь с приоритетом сам писал или заимствовал гдето? (просто я у себя использовал стл вариант а апдейт сделал тупо окучивание всей последовательности, если какойто более производительный вариант?)
а ты очередь с приоритетом сам писал или заимствовал гдето? (просто я у себя использовал стл вариант а апдейт сделал тупо окучивание всей последовательности, если какойто более производительный вариант?)
Если h(x) = 0 (а это и есть эвристическая функция), то мы получим не алгоритм Дейкстры, а обход графа в ширину, это немного разные вещи
очередь с приоритетом писал сам, на основе QList для хранения самой очереди и QSet для быстрой отсечки "есть/нет" в очереди. Не факт что оптимально, но для моих целей работает как часы. Список Closed у меня тоже свой, но все основано на QHash - у меня просто стандартизированный под мой проект интерфейс.
вот еще ссылочка хорошая, там по некоторым алгоритмам хорошо написано: http://khpi-iip.mipk.kharkiv.edu/library/d...gsu/oglav6.html
дядька из КГУ нашего писал, плюс я сам немного лапку для создания некоторых шагов приложил
очередь с приоритетом писал сам, на основе QList для хранения самой очереди и QSet для быстрой отсечки "есть/нет" в очереди. Не факт что оптимально, но для моих целей работает как часы. Список Closed у меня тоже свой, но все основано на QHash - у меня просто стандартизированный под мой проект интерфейс.
вот еще ссылочка хорошая, там по некоторым алгоритмам хорошо написано: http://khpi-iip.mipk.kharkiv.edu/library/d...gsu/oglav6.html
дядька из КГУ нашего писал, плюс я сам немного лапку для создания некоторых шагов приложил
Цитата(wiz29 @ 20.8.2010, 16:06)
Реализовывал ли кто нибудь данный алгоритм?(нужна консультация по производительности, моя реализация считает несколько секунд на картинке 1500+ х 1500+, тогда как продвинутые реализации справляются "мгновенно" с точки зрения пользователя, не беру в расчет время на вычисление весов ребер)
привет! ты не мог бы мне кинуть свою реализацию? nikolas9292@rambler.ru
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.