0

A* アルゴリズムを利用する 4x4 スライディング ブロック パズル ソルバーを実装しようとしています。可能な限りきちんとした方法でコーディングしようとしましたが、segfault がコードに滑り込み、std::priority_queueインスタンスへのポインターをプッシュする試みが失敗したことを示しています。これが完全なコードであり、その後にデバッグの試行が続きます。動作するテスト ケースに切り分ける方法がわかりませんでした。

#include <iostream>
#include <iomanip>

#include <cstring>
#include <cmath>

#include <vector>
#include <set>
#include <queue>

#include <functional>

#include <ctime>
#include <cstdlib>

using namespace std;

const char GOAL_STATE[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0};

class Puzzle
{
protected:
    char puzzle[16];

    int index(char searched) const
    {
        for(int i=0; i<16; i++)
        {
            if (puzzle[i]==searched)
                return i;
        }
        return -1;
    }

public:

    Puzzle(const char init[16] = NULL)
    {
        if(init!=NULL)
        {
            memcpy(puzzle, init, sizeof(char)*16);
        }
        else
        {
            memcpy(puzzle, GOAL_STATE, sizeof(char)*16);
        }
    }

    void show() const
    {
        for(int i=0; i<4; i++)
        {
            for(int j=0; j<4; j++)
            {
                cout << setw(3) << (int)puzzle[i*4+j] << " ";
            }
            cout << endl;
        }
    }

    bool move(int m_pos)
    {
        int b_pos = index(0);
        int b_x = b_pos / 4;
        int b_y = b_pos % 4;
        int x = m_pos / 4;
        int y = m_pos % 4;
        if (m_pos < 16 && (
                    (x == b_x && (y == b_y + 1 || y == b_y - 1)) ||
                    (y == b_y && (x == b_x + 1 || x == b_x - 1))
                )
            )
        {
            char tmp = puzzle[m_pos];
            puzzle[m_pos] = puzzle[b_pos];
            puzzle[b_pos] = tmp;
            return true;
        }
        else
            return false;
    }

    int count_correct() const
    {
        int ret = 0;
        for(int i=0; i<16; i++)
            if ((i<15 && (puzzle[i])==i+1) || (i==15 && puzzle[i]==0))
                ret++;
        return ret;
    }

    vector<int> possible_moves() const
    {
        vector<int> ret;
        int b_pos = index(0);
        int b_x = b_pos / 4;
        int b_y = b_pos % 4;
        ret.push_back(b_y * 4 + b_x - 1);
        ret.push_back((b_y - 1) * 4 + b_x);
        if (b_x<3)
            ret.push_back(b_y * 4 + b_x + 1);
        if (b_y<3)
            ret.push_back((b_y + 1) * 4 + b_x);
        return ret;
    }

};

class AStarPuzzle : public Puzzle
{
    int H;
    int f;

public:

    int tried;

    AStarPuzzle* previous;

    AStarPuzzle(const char init[16] = NULL,
            int _f = 0, int _tried = 0, AStarPuzzle* _previous = NULL) : Puzzle(init)
    {
        f = _f;
        tried = _tried;
        previous = _previous;
    }

    AStarPuzzle (const AStarPuzzle& old) : Puzzle(old.puzzle)
    {
        f = old.f;
        tried = old.tried;
        previous = old.previous;
    }

    double heur() const
    {
        double ret = 0.0;
        for (int goalIndex = 0 ; goalIndex<16; goalIndex++)
        {
            int tileIndex = index( GOAL_STATE[goalIndex] );
            ret += abs((double)((goalIndex % 4) - (tileIndex % 4)));
            ret += abs(floor(goalIndex / 4.0) - floor(tileIndex / 4.0));

        }

        return 0.1*f + max(ret, (double)count_correct());
    }

    bool operator<(const AStarPuzzle& other) const
    {
        return heur()>other.heur();
    }

    int get_f()
    {
        return f;
    }

    void increase_f()
    {
        f++;
    }

    AStarPuzzle operator=(const AStarPuzzle& rhs)
    {
        cout << "STUB: AStarPuzzle::operator=" << endl;
    }

    ~AStarPuzzle()
    {
        cout << "STUB: AStarPuzzle::~AStarPuzzle" << endl;
    }


    void operator delete(void *p)
    {
        cout << "Attempting to delete AStarPuzzle?" << endl;
    }

};


struct CompareHeuristics : public std::binary_function<AStarPuzzle*, AStarPuzzle*, bool >
{
    bool operator()(AStarPuzzle* lhs, AStarPuzzle* rhs) const
    {
        return lhs->heur() > rhs->heur();
    }
};

vector<int> retracePath(AStarPuzzle* c)
{
    vector<int> ret;
    while (c->previous!=NULL)
    {
        c = c->previous;
        ret.push_back(c->tried);
    }
    return ret;
}

vector<int> aStar(AStarPuzzle* current)
{
    set<AStarPuzzle*> openList;
    set<AStarPuzzle*> closedList;
    std::priority_queue<AStarPuzzle*, std::vector<AStarPuzzle*>, CompareHeuristics> openHeap;

    int max_corr = 0;
    int min_step = 0;


    openList.insert(current);
    openHeap.push(current);
    while (openList.size()!=0)
    {
        current = openHeap.top();
        cout << "An iteration. heur()==" << current->heur()  << endl;
        current->show();
        openHeap.top();
        if (current->count_correct() == 16)
        {
            //return vector<int>();
            return retracePath(current);
        }
        openList.erase(current);
        closedList.insert(current);
        vector<int> directions = current->possible_moves();
        for(unsigned int i=0; i<directions.size(); i++)
        {
            AStarPuzzle* tile = new AStarPuzzle(*current);
            tile->move(directions[i]);
            tile->increase_f();

            if (closedList.count(tile)==0)
            {
                int corr = tile->count_correct();
                int f = tile->get_f();
                if (corr > max_corr or (corr == max_corr && f < min_step))
                {
                    max_corr = corr;
                    min_step = f;
                    cout << corr << "," << f << endl;
                }
                tile->previous = current;
                if (openList.count(tile)==0)
                {
                    openList.insert(tile);
                    openHeap.push(tile);
                }
            }

        }
    }


    return vector<int>();
}

int main(int argc, char **argv) {

    char shuffled[16];
    memcpy(shuffled, GOAL_STATE, sizeof(char)*16);
    srand(time(0));
    for (int i=0; i<16; i++) {
        int r = i + (rand() % (16-i));
        char temp = shuffled[i];
        shuffled[i] = shuffled[r];
        shuffled[r] = temp;
    }

    shuffled = {0, 3, 7, 5, 9, 12 , 13 , 11, 8, 6 , 14, 4 , 15, 2 , 10 , 1 };

    AStarPuzzle* p = new AStarPuzzle(shuffled);
    p->show();
    aStar(p);

    return 0;
}

そしてgdb出力：

> gdb ./si-proj2cpp
GNU gdb (GDB) 7.0.1-debian
Copyright (C) 2009 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i486-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /home/d33tah/workspace/si-proj2cpp/Debug/si-proj2cpp...done.
(gdb) r
Starting program: /home/d33tah/workspace/si-proj2cpp/Debug/si-proj2cpp
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
An iteration. heur()==44
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
An iteration. heur()==44
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
An iteration. heur()==44
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
An iteration. heur()==44
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1

Program received signal SIGSEGV, Segmentation fault.
0xb7dab5fc in _int_free (av=<value optimized out>, p=0x80502b0) at malloc.c:4957
4957    malloc.c: No such file or directory.
        in malloc.c
Current language:  auto
The current source language is "auto; currently c".
(gdb) bt
#0  0xb7dab5fc in _int_free (av=<value optimized out>, p=0x80502b0) at malloc.c:4957
#1  0xb7dae8ad in *__GI___libc_free (mem=0x80502b8) at malloc.c:3739
#2  0xb7f86701 in operator delete(void*) () from /usr/lib/libstdc++.so.6
#3  0x0804b97b in __gnu_cxx::new_allocator<AStarPuzzle*>::deallocate (this=0xbffff564, __p=0x80502b8) at /usr/include/c++/4.4/ext/new_allocator.h:95
#4  0x0804ab4b in std::_Vector_base<AStarPuzzle*, std::allocator<AStarPuzzle*> >::_M_deallocate (this=0xbffff564, __p=0x80502b8, __n=16)
    at /usr/include/c++/4.4/bits/stl_vector.h:146
#5  0x0804b2a9 in std::vector<AStarPuzzle*, std::allocator<AStarPuzzle*> >::_M_insert_aux (this=0xbffff564, __position=..., __x=@0xbffff554)
    at /usr/include/c++/4.4/bits/vector.tcc:361
#6  0x0804a5cf in std::vector<AStarPuzzle*, std::allocator<AStarPuzzle*> >::push_back (this=0xbffff564, __x=@0xbffff554) at /usr/include/c++/4.4/bits/stl_vector.h:741
#7  0x08049bbb in std::priority_queue<AStarPuzzle*, std::vector<AStarPuzzle*, std::allocator<AStarPuzzle*> >, CompareHeuristics>::push (this=0xbffff564, __x=@0xbffff554)
    at /usr/include/c++/4.4/bits/stl_queue.h:511
#8  0x08049054 in aStar (current=0x8050008) at ../main.cpp:248
#9  0x08049273 in main (argc=1, argv=0xbffff704) at ../main.cpp:275

誰かが示唆したように、valgrind を使用して何が起こるかを確認しました。

> valgrind ./si-proj2cpp
==26655== Memcheck, a memory error detector
==26655== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
==26655== Using Valgrind-3.6.0.SVN-Debian and LibVEX; rerun with -h for copyright info
==26655== Command: ./si-proj2cpp
==26655==
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
An iteration. heur()==44
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
==26655== Invalid read of size 1
==26655==    at 0x804950E: Puzzle::move(int) (main.cpp:74)
==26655==    by 0x8048F3A: aStar(AStarPuzzle*) (main.cpp:231)
==26655==    by 0x8049272: main (main.cpp:275)
==26655==  Address 0x42ca1ef is 1 bytes before a block of size 32 alloc'd
==26655==    at 0x402471C: operator new(unsigned int) (vg_replace_malloc.c:255)
==26655==    by 0x8048EF6: aStar(AStarPuzzle*) (main.cpp:230)
==26655==    by 0x8049272: main (main.cpp:275)
==26655==
==26655== Invalid write of size 1
==26655==    at 0x8049525: Puzzle::move(int) (main.cpp:75)
==26655==    by 0x8048F3A: aStar(AStarPuzzle*) (main.cpp:231)
==26655==    by 0x8049272: main (main.cpp:275)
==26655==  Address 0x42ca1ef is 1 bytes before a block of size 32 alloc'd
==26655==    at 0x402471C: operator new(unsigned int) (vg_replace_malloc.c:255)
==26655==    by 0x8048EF6: aStar(AStarPuzzle*) (main.cpp:230)
==26655==    by 0x8049272: main (main.cpp:275)
==26655==
An iteration. heur()==44
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
An iteration. heur()==44
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
(...looks like an infinite loop, so I'm stopping the program with ctr+c)
  0   3   7   5
  9  12  13  11
  8   6  14   4
 15   2  10   1
^CAn iteration. heur()==44
==26655==
==26655== HEAP SUMMARY:
==26655==     in use at exit: 17,076 bytes in 579 blocks
==26655==   total heap usage: 805 allocs, 226 frees, 21,156 bytes allocated
==26655==
==26655== LEAK SUMMARY:
==26655==    definitely lost: 0 bytes in 0 blocks
==26655==    indirectly lost: 0 bytes in 0 blocks
==26655==      possibly lost: 0 bytes in 0 blocks
==26655==    still reachable: 17,076 bytes in 579 blocks
==26655==         suppressed: 0 bytes in 0 blocks
==26655== Rerun with --leak-check=full to see details of leaked memory
==26655==
==26655== For counts of detected and suppressed errors, rerun with: -v
==26655== ERROR SUMMARY: 288 errors from 2 contexts (suppressed: 19 from 8)
4

3 に答える 3

1

ここでint演算に署名します

vector<int> possible_moves() const
{
    vector<int> ret;
    int b_pos = index(0);
    int b_x = b_pos / 4;
    int b_y = b_pos % 4;
    ret.push_back(b_y * 4 + b_x - 1);
    ret.push_back((b_y - 1) * 4 + b_x);
    if (b_x<3)
        ret.push_back(b_y * 4 + b_x + 1);
    if (b_y<3)
        ret.push_back((b_y + 1) * 4 + b_x);
    return ret;
}

次に、それをアドレスとして使用します。

    vector<int> directions = current->possible_moves();
    for(unsigned int i=0; i<directions.size(); i++)
    {
        AStarPuzzle* tile = new AStarPuzzle(*current);
        tile->move(directions[i]);    // <<------ here, line 231
        tile->increase_f();

intインデックスをsに置き換えunsigned int、コンパイラの要求に応じてコードを変更し、何が起こるかを確認します。

于 2013-03-03T14:20:54.740 に答える
1

で値を返すのを忘れましたAStarPuzzle::operator=。次に、Ideone は segfault を報告しませんが、タイムアウトします。先に進む前に無限ループを修正する必要があるかもしれません...また、intin Puzzle::moveforを使用してm_posおり、負の値をチェックしていません。unsigned int代わりに使用してください。

編集: Visual C++ 2010 でテスト済み、segfault なし、無限ループ。正しいランタイムを使用していることを確認する必要があります。

于 2013-03-03T14:10:13.620 に答える
0

問題は実際にはメモリに関連していませんでした。@Synxisが指摘したように、負のm_posがPuzzle::moveに渡されていました。それが起こった理由は、possible_moves（）が0ブロックが（0,0）にあるときの状況を考慮していなかったためです-possible_movesを修正することは役に立ちました。別のバグは、xとyが逆であり、openHeap.top（）、openHeap.pop（）の代わりにopenHeap.top（）が2回呼び出されることに関連していました。

于 2013-03-03T14:23:03.473 に答える