当我尝试编译时出现以下错误:
In member function 'double search::IDAstar::dfs(const State&, double)': 153:18: error: need 'typename' before
'MoveContainer:: const_iterator' because 'MoveContainer' is a dependent scope 153:48: error: expected ';' before 'it' 154:17: error: 'it'
was not declared in this scope
In member function '{anonymous}::State& {anonymous}::State::operator=(const {anonymous}::State&)':
234:9: warning: no return statement in function returning non-void [-Wreturn-type] In instantiation of
'double search::IDAstar::dfs(const State&, double) [with State = {anonymous}::State; MoveContainer = std::list >]':
122:34: required from 'std::list search::IDAstar::solve(const State&)
[with State = {anonymous}::State; MoveContainer = std::list >]' 371:55: required from here
152:57: error: invalid initialization of non-const reference of type 'std::list >&' from an rvalue of type
'{anonymous}::State::MoveContainer {aka std::list >}' 153:66: error: dependent-name 'MoveContainer:: const_iterator'
is parsed as a non-type, but instantiation yields a type 153:66: note: say 'typename MoveContainer:: const_iterator' if a type is meant
search_IDAstar.h
///////////////////////////////////////////////////////////////// //// ////////////////////////////////
//
// search_IDAstar.h
//
///////////////////////////////////////////////////////////////// //// ////////////////////////////////
#ifndef SEARCH_IDASTAR_H
#define SEARCH_IDASTAR_H
#include
#include // infinity
namespace search
{
// A Move is a generic successor of a State (see IDAstar below).
template
class Move
{
công cộng:
// Create a move to the given successor state with the given cost.
Move(const State& s, double g) :
s(s),
g(g)
{
// empty
}
// Destructor
~Move()
{
// empty
}
// Copy constructor
Move(const Move& copy) :
s(copy.s),
g(copy.g)
{
// empty
}
// Assignment operator
Move& operator= (const Move& rhs)
{
s = rhs.s;
g = rhs.g;
}
// Return successor state.
State state() const
{
return s;
}
// Return cost of this move.
double cost() const
{
return g;
}
riêng tư:
State s;
double g;
};
// IDAstar is a generic implementation of the IDA* search algorithm.
//
// Instances of the parameter State should implement the following methods:
//
// double State::h() const;
// bool State::isGoal() const;
// MoveContainer State::successors(std::list& solution) const;
//
// where h() is an admissible heuristic, isGoal() returns true iff the
// state is a goal state, and successors() returns a container of moves,
// each of which implements the following methods:
//
// State state() const;
// double cost() const;
//
// where state() is a successor state and cost() is the cost of the
// corresponding move. The successors() method may exclude cycles using
// the given partial solution sequence of states.
template<> > >
class IDAstar
{
công cộng:
// Constructor
IDAstar() :
solution(),
solved(false),
fLimit(0),
inf(std::numeric_limits::infinity())
{
// empty
}
// Destructor
~IDAstar()
{
// empty
}
// Use IDA* search to find an optimal path from the given state to a
// goal state. Return a list of states from the given state to the
// goal state, or an empty list if no solution exists.
std::list solve(const State& s)
{
solution.clear();
solved = false;
fLimit = s.h();
while (!solved && fLimit < inf)
{
fLimit = dfs(s, 0);
}
return solution;
}
riêng tư:
// Private unimplemented copy constructor and assignment operator
IDAstar(const IDAstar& copy);
IDAstar& operator= (const IDAstar& rhs);
std::list solution;
bool solved;
double fLimit;
double inf;
double dfs(const State& s, double g)
{
double f = g + s.h();
if (f > fLimit)
{
return f;
}
solution.push_back(s);
if (s.isGoal())
{
solved = true;
return f;
}
double fMin = inf;
MoveContainer& moves = s.successors(solution);
for (MoveContainer::const_iterator it = moves.begin();
it != moves.end(); ++it)
{
f = dfs(it->state(), g + it->cost());
if (solved)
{
return f;
}
if (f < fMin)
{
fMin = f;
}
}
solution.pop_back();
return fMin;
}
};
} // namespace search
#endif
瓷砖.cpp
///////////////////////////////////////////////////////////////// //// ////////////////////////////////
//
// tiles.cpp
//
///////////////////////////////////////////////////////////////// //// ////////////////////////////////
#include "search_IDAstar.h"
#include
#include // find
#include // abs
#include
#include
namespace // unnamed namespace
{
// Number of rows/columns in the sliding tile puzzle.
const int rows = 4;
const int columns = 4;
const int size = rows*columns;
// Manhattan distance heuristic.
int manhattan[size][size];
// A State is a configuration of a sliding tile puzzle.
class State
{
công cộng:
// A state may be specified as a vector, where tiles[i] is the tile in
// the i-th position in row-major order, and the blank is specified as
// rows*columns == size == tiles.size().
typedef std::vector Tiles;
// Constructor
State(const Tiles& tiles) :
tiles(tiles),
blank(0)
{
for (int i = 0; i < size; ++i)
{
if (tiles[i] == size)
{
blank = i;
phá vỡ;
}
}
}
// Destructor
~State()
{
// empty
}
// Copy constructor
State(const State& copy) :
tiles(copy.tiles),
blank(copy.blank)
{
// empty
}
// Assignment operator
State& operator= (const State& rhs)
{
tiles = rhs.tiles;
blank = rhs.blank;
}
// Equality operator
bool operator== (const State& rhs)
{
for (int i = 0; i < size; ++i)
{
if (tiles[i] != rhs.tiles[i])
{
trả về sai;
}
}
trả về sự thật;
}
// Return admissible heuristic.
double h() const
{
int cost = 0;
for (int i = 0; i < size; ++i)
{
if (i != blank)
{
cost += manhattan[i][tiles[i] - 1];
}
}
return cost;
}
// Return true iff this state is a goal state.
bool isGoal() const
{
for (int i = 0; i < size; ++i)
{
if (tiles[i] != i + 1)
{
trả về sai;
}
}
trả về sự thật;
}
// Return successors of this state.
typedef search::Move Move;
typedef std::list MoveContainer;
MoveContainer successors(std::list& solution) const
{
MoveContainer moves;
// Move blank right.
if ((blank + 1)%columns != 0)
{
State s(*this);
s.tiles[blank] = tiles[blank + 1];
s.tiles[blank + 1] = size;
s.blank = blank + 1;
if (std::find(solution.begin(), solution.end(), s) ==
solution.end())
{
moves.push_back(Move(s, 1));
}
}
// Move blank up.
if (blank - columns >= 0)
{
State s(*this);
s.tiles[blank] = tiles[blank - columns];
s.tiles[blank - columns] = size;
s.blank = blank - columns;
if (std::find(solution.begin(), solution.end(), s) ==
solution.end())
{
moves.push_back(Move(s, 1));
}
}
// Move blank left.
if (blank%columns != 0)
{
State s(*this);
s.tiles[blank] = tiles[blank - 1];
s.tiles[blank - 1] = size;
s.blank = blank - 1;
if (std::find(solution.begin(), solution.end(), s) ==
solution.end())
{
moves.push_back(Move(s, 1));
}
}
// Move blank down.
if (blank + columns < size)
{
State s(*this);
s.tiles[blank] = tiles[blank + columns];
s.tiles[blank + columns] = size;
s.blank = blank + columns;
if (std::find(solution.begin(), solution.end(), s) ==
solution.end())
{
moves.push_back(Move(s, 1));
}
}
return moves;
}
Tiles tiles;
int blank;
};
} // unnamed namespace
int chính()
{
// Initialize pre-computed Manhattan distance heuristic.
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < size; ++j)
{
manhattan[i][j] = std::abs(i/columns - j/columns) +
std::abs(i%columns - j%columns);
}
}
// Get starting puzzle configuration.
std::cout << "Enter puzzle: ";
State::Tiles tiles;
for (int i = 0; i < size; ++i)
{
int t;
std::cin >> t;
tiles.push_back(t);
}
// Search for a solution.
search::IDAstar ida;
std::clock_t tic = std::clock();
std::list solution = ida.solve(State(tiles));
std::clock_t toc = std::clock();
// Display solution.
std::cout << "Solution in " << static_cast(solution.size()) - 1 <<
" moves." << std::endl;
for (std::list::iterator it = solution.begin(); it != solution.end(); ++it)
{
State::Tiles& tiles = (*it).tiles;
for (size_t i = 0; i < tiles.size(); ++i)
{
std::cout << tiles[i] << " ";
}
std::cout << std::endl;
}
std::cout << "Elapsed time = " <<
static_cast(toc - tic)/CLOCKS_PER_SEC << " seconds." <<
std::endl;
}
第一个错误 MoveContainer::const_iterator 我输入 auto 并且这是临时修复。首先我认为是 namespace 或 iostream 的问题,但事实并非如此。我在 linux 中用 c++11、c++14 编译。该程序是用于解决 15 个谜题的算法 IDA* 的示例。
153:18: error: need 'typename' before 'MoveContainer:: const_iterator'
because 'MoveContainer' is a dependent scope
这一篇告诉你该怎么做。改变
for (MoveContainer::const_iterator it = moves.begin();
đến
for (typename MoveContainer::const_iterator it = moves.begin();
Nhìn thấy Where and why do I have to put the "template" and "typename" keywords?
234:9: warning: no return statement in function returning non-void
如其所说,您的 State::operator=
缺少返回语句。
// Assignment operator
State& operator= (const State& rhs)
{
tiles = rhs.tiles;
blank = rhs.blank;
trả lại *cái này;
}
或者更好的是,根据零规则,根本不要定义 operator=
.
52:57: error: invalid initialization of non-const reference of type
'std::list >&' from an rvalue of type
'{anonymous}::State::MoveContainer {aka
std::list >}'
就在这里:
MoveContainer& moves = s.successors(solution);
您尝试从按值返回的函数中初始化引用。删除引用:
MoveContainer moves = s.successors(solution);
Tôi là một lập trình viên xuất sắc, rất giỏi!