0
Die unter CodeReview präsentierte Lösung funktioniert auf CentOS 7.1 einwandfrei. Ich habe versucht, es auf Windows 7, Visual Studio 2012 zu portieren. Mit kleinen Änderungen, die für die Teile von C++ 11 zulassen, dass VS 2012 den Code nicht unterstützt, kompiliert, und die erste Ausführung der Schleife funktioniert ordnungsgemäß. Der Rest der Ausführung von Testfällen schlägt fehl und wird mit jeder Ausführung zunehmend inkorrekter.Recursive Breath Erste Suche funktioniert bei der ersten Ausführung, aber nicht bei der Ausführung
Der Code für dieses Problem kann auf github gefunden werden.
beendet Berechnung bei 0/* Problem hier nicht in Frage */
verstrichene Zeit enthalten: 0,202012 Sekunden
Der Entstehungsort war A3
Der Zielpunkt für alle Pfad Suche wurde H4
Die Anzahl der Quadrate an jeder Kante der Karte ist 8
Die Slicing-Methode, die zur weiteren Einschränkung der Suche verwendet wurde, bestand nicht in wiederholten Besuchen von Zeilen oder Spalten.
Es gibt 5 Resultierende Paths
Es waren 323 versuchten Wege
Die durchschnittliche Pfadlänge beträgt 4,8
Die mittlere Weglänge 4
Der längste Weg 6 bewegt
Der kürzeste Weg ist 4 bewegt sich
Ich glaube, das Problem ist in einer der unten aufgeführten Dateien. Ich habe das für 2 Tage getestet, ich kann Hilfe gebrauchen.
CRKnightMoves_Cpp2.cpp
/*
* KnightMoves.cpp
*
* Author: pacmaninbw
*/
#include "stdafx.h"
#include <iostream>
#include <stdexcept>
#include <chrono>
#include <ctime>
#include <algorithm>
#include <functional>
#include <vector>
#include "KnightMoves.h"
#include "KnightMovesImplementation.h"
#include "KMBoardDimensionConstants.h"
double Average(std::vector<double> TestTimes)
{
double AverageTestTime = 0.0;
double SumOfTestTimes = 0.0;
int CountOfTestTimes = 0;
for (auto TestTimesIter : TestTimes)
{
SumOfTestTimes += TestTimesIter;
CountOfTestTimes++;
}
if (CountOfTestTimes) { // Prevent division by zero.
AverageTestTime = SumOfTestTimes/static_cast<double>(CountOfTestTimes);
}
return AverageTestTime;
}
void OutputOverAllStatistics(std::vector<double> TestTimes)
{
if (TestTimes.size() < 1) {
std::cout << "No test times to run statistics on!" << std::endl;
return;
}
std::cout << std::endl << "Overall Results" << std::endl;
std::cout << "The average execution time is " << Average(TestTimes) << " seconds" << std::endl;
std::nth_element(TestTimes.begin(), TestTimes.begin() + TestTimes.size()/2, TestTimes.end());
std::cout << "The median execution time is " << TestTimes[TestTimes.size()/2] << " seconds" << std::endl;
std::nth_element(TestTimes.begin(), TestTimes.begin()+1, TestTimes.end(), std::greater<double>());
std::cout << "The longest execution time is " << TestTimes[0] << " seconds" << std::endl;
std::nth_element(TestTimes.begin(), TestTimes.begin()+1, TestTimes.end(), std::less<double>());
std::cout << "The shortest execution time is " << TestTimes[0] << " seconds" << std::endl;
}
double ExecutionLoop(KMBaseData UserInputData)
{
KnightMovesImplementation *KnightPathFinder = new KnightMovesImplementation(UserInputData);
std::chrono::time_point<std::chrono::system_clock> start, end;
start = std::chrono::system_clock::now();
KMOutputData OutputData = KnightPathFinder->CalculatePaths();
end = std::chrono::system_clock::now();
std::chrono::duration<double> elapsed_seconds = end-start;
std::time_t end_time = std::chrono::system_clock::to_time_t(end);
double ElapsedTimeForOutPut = elapsed_seconds.count();
char ctimebuffer[1024];
std::cout << "finished computation at " << ctime_s(ctimebuffer, 1024, &end_time) << "\n"
<< "elapsed time: " << ElapsedTimeForOutPut << " Seconds\n" << "\n" << "\n";
// Don't include output of results in elapsed time calculation
OutputData.DontShowPathData();
// OutputData.ShowPathData();
OutputData.ShowResults();
delete KnightPathFinder;
return ElapsedTimeForOutPut;
}
int LetUserEnterTestCaseNumber(std::vector<KMBaseData> &TestData)
{
int i = 1;
int Choice = -1;
std::cout << "Select the number of the test case you want to run.\n";
std::cout << "Test Case #" << "\tStart Name" << "\tTarget Name" << "\tBoard Size" << "\tSlicing Method" << "\n";
for (auto TestCase: TestData) {
std::cout << i << "\t" << TestCase.m_StartName << "\t" << TestCase.m_TargetName << "\t" << TestCase.m_DimensionOneSide << "\t";
switch (TestCase.m_LimitationsOnMoves)
{
default :
throw std::runtime_error("LetUserEnterTestCaseNumber : Unknown type of Path Limitation.");
case DenyByPreviousLocation :
std::cout << "Can't return to previous location";
break;
case DenyByPreviousRowOrColumn:
std::cout << "Can't return to previous row or column";
break;
}
std::cout << "\n";
i++;
}
std::cout << i << "\tAll of the above except for 13 and 14\n";
std::cout << ++i <<"\tAll of the above (Go get lunch)\n";
std::cin >> Choice;
if (Choice == 15)
{
std::vector<KMBaseData> TempTests;
for (auto TestCase: TestData)
{
if ((TestCase.m_DimensionOneSide != MaximumBoardDimension) && (TestCase.m_LimitationsOnMoves != DenyByPreviousLocation))
{
TempTests.push_back(TestCase);
}
}
TestData = TempTests;
}
return Choice;
}
void InitTestData(std::vector<KMBaseData> &TestData)
{
KMBaseData TestCases[] = {
{1,3,"A3",8,4,"H4", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{1,1,"A1",8,8,"H8", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{1,8,"A8",8,1,"H1", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{2,3,"B3",8,4,"H4", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{2,3,"B3",8,8,"H8", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{3,1,"C1",8,4,"H4", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{3,1,"A3",8,8,"H8", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{1,3,"A3",2,5,"B5", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn}, // Minimum should be one move
{8,4,"H4",1,3,"A3", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{4,4,"D4",1,8,"A8", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{4,4,"D4",5,6,"E6", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{1,3,"A3",2,5,"B5", 12, DenyByPreviousRowOrColumn}, // Minimum should be one move
{1,3,"A3",2,5,"B5", DefaultBoardDimensionOnOneSide, DenyByPreviousLocation}, // Minimum should be one move
{1,3,"A3",2,5,"B5", MaximumBoardDimension, DenyByPreviousRowOrColumn} // Minimum should be one move
};
for (int i = 0; i < sizeof(TestCases)/sizeof(KMBaseData); i++) {
TestData.push_back(TestCases[i]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int status = 0;
std::vector<KMBaseData> TestData;
std::vector<double> TestTimes;
try {
InitTestData(TestData);
int Choice = LetUserEnterTestCaseNumber(TestData);
if (Choice < 0)
{
return status;
}
if (Choice < 15)
{
ExecutionLoop(TestData[Choice-1]);
}
else
{
for (auto TestDataIter: TestData) {
TestTimes.push_back(ExecutionLoop(TestDataIter));
}
}
OutputOverAllStatistics(TestTimes);
return status;
}
catch(std::runtime_error &e) {
std::cerr << "A fatal error occurred in KnightMoves: ";
std::cerr << e.what() << std::endl;
status = 1;
}
catch(std::runtime_error *e) {
std::cerr << "A fatal error occurred in KnightMoves: ";
std::cerr << e->what() << std::endl;
status = 1;
}
catch(...) {
std::cerr << "An unknown fatal error occurred in KnightMoves." << std::endl;
status = 1;
}
return status;
}
KnightMovesImplementation.h
#pragma once
/*
* KnightMovesImplementation.h
*
* Created on: Mar 18, 2016
* Modified on: June 20, 2016
* Author: pacmaninbw
*
* This class provides the search for all the paths a Knight on a chess
* board can take from the point of origin to the destination. It
* implements a modified Knights Tour. The classic knights tour problem
* is to visit every location on the chess board without returning to a
* previous location. That is a single path for the knight. This
* implementation returns all possible paths from point a to point b.
* The actual implementation is documented in the CPP file because it
* can be changed. This head file provides the public interface which
* should not be changed. The public interface may be moved to a
* super class in the future.
*/
#ifndef KNIGHTMOVESIMPLEMENTATION_H_
#define KNIGHTMOVESIMPLEMENTATION_H_
#include "KMPath.h"
#include "KMOutputData.h"
#include "KMMoveFilters.h"
class KnightMovesImplementation {
private:
KMBoardLocation m_PointOfOrigin;
KMBoardLocation m_Destination;
unsigned int m_SingleSideBoardDimension;
KnightMovesMethodLimitations m_PathLimitations;
KMOutputData *m_Results;
KMMoveFilters *m_MoveFilters;
KMPath *m_Path;
protected:
bool CalculatePath(KMMove CurrentMove); // Recursive function
void InitPointOfOrigin(KMBaseData UserData);
void InitDestination(KMBaseData UserData);
public:
KnightMovesImplementation(KMBaseData UserData);
virtual ~KnightMovesImplementation(void);
KMOutputData CalculatePaths();
};
#endif /* KNIGHTMOVESIMPLEMENTATION_H_ */
KnightsImplementation.cpp
/*
* KnightMovesImplementation.cpp
*
* Created on: Mar 18, 2016
* Modified on: June 21, 2016
* Commented on: June 24, 2016
* Author: pacmaninbw
*
* This class implements the search for all possible paths for a Knight
* on a chess board from one particular square on the board to another
* particular square on the board.
*
* The current implementation is a Recursive Breadth First Search. Conceptually
* the algorithm implements a B+ tree with a maximum of 8 possible branches
* at each level. The root of the tree is the point of origin. A particular
* path terminates in a leaf. A leaf is the result of either reaching the
* destination, or reaching a point where there are no more branches to
* traverse.
*
* The m_Path variable is used as a stack within the search.
*
* The public interface CalculatePaths establishes the root and creates
* the first level of branching. The protected interface CalculatePath
* performs the recursive depth first search, however, the
* m_MoveFilters.GetPossibleMoves() function it calls performs a breadth
* first search of the current level.
*
*/
#include "stdafx.h"
#include "KnightMoves.h"
#include "KnightMovesImplementation.h"
#include "KMBoardDimensionConstants.h"
KnightMovesImplementation::~KnightMovesImplementation(void)
{
delete m_MoveFilters;
delete m_Results;
delete m_Path;
}
KnightMovesImplementation::KnightMovesImplementation(KMBaseData UserInputData)
: m_SingleSideBoardDimension(UserInputData.m_DimensionOneSide),
m_PathLimitations(UserInputData.m_LimitationsOnMoves)
{
InitPointOfOrigin(UserInputData);
InitDestination(UserInputData);
m_Path = new KMPath;
m_MoveFilters = new KMMoveFilters(static_cast<unsigned int>(UserInputData.m_DimensionOneSide), UserInputData.m_LimitationsOnMoves);
m_Results = new KMOutputData(m_PointOfOrigin, m_Destination, m_SingleSideBoardDimension, m_PathLimitations);
}
void KnightMovesImplementation::InitPointOfOrigin(KMBaseData UserInputData)
{
m_PointOfOrigin.SetRow(UserInputData.m_StartRow);
m_PointOfOrigin.SetColumn(UserInputData.m_StartColumn);
m_PointOfOrigin.SetName(UserInputData.m_StartName);
m_PointOfOrigin.SetBoardDimension(m_SingleSideBoardDimension);
}
void KnightMovesImplementation::InitDestination(KMBaseData UserInputData)
{
m_Destination.SetRow(UserInputData.m_TargetRow);
m_Destination.SetColumn(UserInputData.m_TargetColumn);
m_Destination.SetName(UserInputData.m_TargetName);
m_Destination.SetBoardDimension(m_SingleSideBoardDimension);
}
KMOutputData KnightMovesImplementation::CalculatePaths()
{
KMRandomAccessMoveCollection PossibleFirstMoves = m_MoveFilters->GetPossibleMoves(m_PointOfOrigin);
if (PossibleFirstMoves.empty())
{
std::cerr << "No Possible Moves in KnightMovesImplementation::CalculatePaths" << std::endl;
}
else
{
for (auto CurrentMoveIter : PossibleFirstMoves)
{
KMMove CurrentMove = CurrentMoveIter;
CurrentMove.SetOriginCalculateDestination(m_PointOfOrigin);
if (CurrentMove.IsValid()) {
CalculatePath(CurrentMove);
}
}
}
return *m_Results;
}
bool KnightMovesImplementation::CalculatePath(KMMove CurrentMove)
{
bool CompletedSearch = false;
KMBoardLocation CurrentLocation = CurrentMove.GetNextLocation();
m_Path->AddMoveToPath(CurrentMove);
m_MoveFilters->PushVisited(CurrentLocation);
if (CurrentLocation == m_Destination)
{
m_Results->AddPath(*m_Path);
CompletedSearch = true;
m_Results->IncrementAttemptedPaths();
}
else
{
if (CurrentMove.IsValid())
{
KMRandomAccessMoveCollection PossibleMoves = m_MoveFilters->GetPossibleMoves(CurrentLocation);
if (!PossibleMoves.empty())
{
for (auto NextMove : PossibleMoves)
{
CalculatePath(NextMove);
}
}
else
{
// No more moves to test, record the attempted path
m_Results->IncrementAttemptedPaths();
}
}
else
{
// There is a logic error if we get here.
std::cerr << "In KnightMovesImplementation::CalculatePath CurrentMove Not Valid" << std::endl;
}
}
m_Path->RemoveLastMove();
m_MoveFilters->PopVisited();
return CompletedSearch;
}
KMMoveFilters.h
#pragma once
/*
* KMMoveFilters.h
*
* Created on: Jun 20, 2016
* Author: pacmaninbw
*
* This class provides all the possible Knight moves for a specified location
* on the chess board. In the center of the chess board there are 8 possible
* moves. In the middle of the edge on the chess board there are 4 possible
* moves. In a corner of the chess board there are 2 possible moves. The
* location on the board provides the first filter.
* Slicing is used to allow the program to complete in a reasonable finite
* amount of time. The slicing method can be varied, the default slicing
* method is the knight can't return to any row or column it has previously
* visited. The slicing is the second filter.
*/
#ifndef KMMOVEFILTERS_H_
#define KMMOVEFILTERS_H_
#include <vector>
#include "KnightMoves.h"
#include "KMMove.h"
class KMMoveFilters {
private:
std::vector<KMBoardLocation> m_VisitedLocations;
std::vector<unsigned int> m_VisitedRows;
std::vector<unsigned int> m_VisitedColumns;
unsigned int m_SingleSideBoardDimension;
KnightMovesMethodLimitations m_PathLimitations;
static KMRandomAccessMoveCollection AllPossibleMoves;
// The 8 possible moves the knight can make.
static KMMove Left1Up2;
static KMMove Left2Up1;
static KMMove Left2Down1;
static KMMove Left1Down2;
static KMMove Right1Up2;
static KMMove Right2Up1;
static KMMove Right2Down1;
static KMMove Right1Down2;
protected:
bool IsNotPreviouslyVisited(KMMove Move) const { return IsNotPreviouslyVisited(Move.GetNextLocation()); };
bool IsNotPreviouslyVisited(KMBoardLocation Destination) const;
public:
KMMoveFilters(void);
KMMoveFilters(unsigned int BoardDimension, KnightMovesMethodLimitations SlicingMethod);
void ResetFilters(unsigned int BoardDimension, KnightMovesMethodLimitations SlicingMethod) {m_SingleSideBoardDimension = BoardDimension; m_PathLimitations = SlicingMethod; }
virtual ~KMMoveFilters(void);
void PushVisited(KMBoardLocation Location);
void PopVisited();
KMRandomAccessMoveCollection GetPossibleMoves(const KMBoardLocation CurrentLocation) const;
};
KMMoveFilters.cpp
/*
* KMMoveFilters.cpp
*
* Created on: Jun 20, 2016
* Author: pacmaninbw
*/
#include "stdafx.h"
#include <stdexcept>
#include <algorithm>
#include "KMBoardDimensionConstants.h"
#include "KMMoveFilters.h"
KMMoveFilters::~KMMoveFilters(void)
{
}
KMMoveFilters::KMMoveFilters(void)
: m_SingleSideBoardDimension(DefaultBoardDimensionOnOneSide),
m_PathLimitations(DenyByPreviousRowOrColumn)
{
AllPossibleMoves.push_back(Left1Up2);
AllPossibleMoves.push_back(Left2Up1);
AllPossibleMoves.push_back(Left2Down1);
AllPossibleMoves.push_back(Left1Down2);
AllPossibleMoves.push_back(Right1Up2);
AllPossibleMoves.push_back(Right2Up1);
AllPossibleMoves.push_back(Right2Down1);
AllPossibleMoves.push_back(Right1Down2);
}
KMMoveFilters::KMMoveFilters(unsigned int BoardDimension, KnightMovesMethodLimitations SlicingMethod)
: m_SingleSideBoardDimension(BoardDimension), m_PathLimitations(SlicingMethod)
{
AllPossibleMoves.push_back(Left1Up2);
AllPossibleMoves.push_back(Left2Up1);
AllPossibleMoves.push_back(Left2Down1);
AllPossibleMoves.push_back(Left1Down2);
AllPossibleMoves.push_back(Right1Up2);
AllPossibleMoves.push_back(Right2Up1);
AllPossibleMoves.push_back(Right2Down1);
AllPossibleMoves.push_back(Right1Down2);
}
const int Left1 = -1;
const int Left2 = -2;
const int Down1 = -1;
const int Down2 = -2;
const int Right1 = 1;
const int Right2 = 2;
const int Up1 = 1;
const int Up2 = 2;
KMMove KMMoveFilters::Left1Up2(Left1, Up2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left2Up1(Left2, Up1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left2Down1(Left2, Down1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left1Down2(Left1, Down2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right1Up2(Right1, Up2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right2Up1(Right2, Up1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right2Down1(Right2, Down1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right1Down2(Right1, Down2, DefaultBoardDimensionOnOneSide);
KMRandomAccessMoveCollection KMMoveFilters::AllPossibleMoves;
KMRandomAccessMoveCollection KMMoveFilters::GetPossibleMoves(const KMBoardLocation CurrentLocation) const
{
KMRandomAccessMoveCollection PossibleMoves;
for (auto PossibeMove : AllPossibleMoves) {
KMMove *TempMove = new KMMove(PossibeMove);
TempMove->SetBoardDimension(m_SingleSideBoardDimension);
TempMove->SetOriginCalculateDestination(CurrentLocation);
if ((TempMove->IsValid()) && (IsNotPreviouslyVisited(*TempMove))) {
PossibleMoves.push_back(*TempMove);
}
}
return PossibleMoves;
}
bool KMMoveFilters::IsNotPreviouslyVisited(KMBoardLocation PossibleDestination) const
{
bool NotPrevioslyVisited = true;
if (!m_VisitedLocations.empty()) { // This is always a test, we can't move backwards
if (std::find(m_VisitedLocations.begin(), m_VisitedLocations.end(), PossibleDestination)
!= m_VisitedLocations.end()) {
NotPrevioslyVisited = false;
}
}
switch (m_PathLimitations) {
default :
throw std::runtime_error("KMPath::CheckMoveAgainstPreviousLocations : Unknown type of Path Limitation.");
case DenyByPreviousLocation :
// Always tested above.
break;
case DenyByPreviousRowOrColumn:
if ((!m_VisitedRows.empty()) && (!m_VisitedColumns.empty())) {
unsigned int PossibleRow = PossibleDestination.GetRow();
if (std::find(m_VisitedRows.begin(), m_VisitedRows.end(), PossibleRow) != m_VisitedRows.end()) {
NotPrevioslyVisited = false;
break;
}
unsigned int PossibleColum = PossibleDestination.GetColumn();
if (std::find(m_VisitedColumns.begin(), m_VisitedColumns.end(), PossibleColum) != m_VisitedColumns.end()) {
NotPrevioslyVisited = false;
}
}
break;
}
return NotPrevioslyVisited;
}
void KMMoveFilters::PushVisited(KMBoardLocation Location)
{
m_VisitedRows.push_back(Location.GetRow());
m_VisitedColumns.push_back(Location.GetColumn());
m_VisitedLocations.push_back(Location);
}
void KMMoveFilters::PopVisited()
{
m_VisitedRows.pop_back();
m_VisitedColumns.pop_back();
m_VisitedLocations.pop_back();
}
Sie haben eine Version, die auf einer Plattform arbeitet, und eine Version, die auf einer anderen Plattform aus, und Sie können nicht Finden Sie, wo sie auseinander gehen? – Beta
@Beta Mehr oder weniger. Die Version, die fehlschlägt, übergibt tatsächlich den ersten Durchlauf durch die Schleife. Es ist nur, wenn ich mehrere Testfälle in der Schleife verwende, dass es fehlschlägt. Es ist möglich, dass der statische Vektor in MoveFilters.cpp irgendwann aktiviert wird. Es führt definitiv zu Speicherproblemen bei der 4. Iteration der Testfallschleife. – pacmaninbw
Es scheitert an der 4. Iteration, bedeutet das, dass es 1-3 passieren? Was passiert, wenn Sie den 3. und 4. Testfall in der Warteschlange tauschen? Sollte dieser statische Vektor zwischen Testfällen zurückgesetzt werden? Mit ein wenig Detektivarbeit können Sie dieses Problem ziemlich eingrenzen. – Beta