开始试了下，要保证最短路径会极大扩大搜查范围，在4x4的情况下，会内存不足

所以放弃A*。

后面的优化是针对问题加入剪枝规则


【 在 here080 的大作中提到: 】
: 这里有A*算法？我读书少你别骗我。
: 【 在 ArchLinux (a lightweight and flexible distribution) 的大作中提到: 】
: : 标  题: Re: 数字华容道程序速度快速下降，比C#慢几十倍
: ....................
--
FROM 117.136.0.*

是的，如果是工作，拿钱干活还行。
论坛交流，没有耐心看。一般讨论，想深入讨论，这样贴代码确实太粗糙了。
他说的倒也没毛病，懂的自然懂。这就是交流的典型醉汉困境，各说各的，
我没醉你醉了。——我才没醉你醉了！
【 在 here080 的大作中提到: 】
: 我不太乐意特别细地去看他的代码，因为据我多年code review的经验，特别难读的未提交代码，你各脑补把代码读清楚了，最后多半会发现代码本身就有问题，你脑补出来的不是作者想要达到的效果。读代码首先要弄清作者想要干嘛，然后才不会浪费时间去分析。
:
--
FROM 117.39.234.*

代码：

constexpr int kLength = 4;
constexpr int kTileCount = kLength * kLength;
constexpr int kEmpty = kTileCount - 1;  // The value for the empty tile.
constexpr uint64_t kOkId = 0xfedcba9876543210;

constexpr int kMaxSteps = 100;

using TileArray = std::array<int, kTileCount>;

constexpr std::pair<int, int> FromOffset(int offset) {
  return {offset / kLength, offset % kLength};
}

constexpr int ToOffset(int row, int col) { return row * kLength + col; }

template <typename C, typename E>
bool Contains(const C& container, const E& value) {
  return container.find(value) != container.end();
}

// The numerical value of each enum here is the offset in tiles index.
enum Direction { kLeft = -1, kRight = 1, kUp = -kLength, kDown = kLength };

void PrintTiles(const TileArray& tiles,
                std::array<std::string, kLength>& output) {
  for (int r = 0; r < kLength; ++r) {
    std::string& line = output[r];
    for (int c = 0; c < kLength; ++c) {
      int tile = tiles[ToOffset(r, c)];
      line.push_back(tile == kEmpty ? '*' : 'A' + tile);
      line.push_back(' ');
    }
  }
}

class Board {
public:
  explicit Board(const TileArray& tiles) : tiles_(tiles) {
    int score = 0;
    for (int i = 0; i < tiles_.size(); ++i) {
      score += ScoreTile(i);
    }
    score_ = score;
  }

  uint64_t GenerateId() const {
    uint64_t id = 0;
    for (int i = 0; i < tiles_.size(); ++i) {
      id |= static_cast<uint64_t>(tiles_[i]) << i * 4;
    }
    return id;
  }

  // Tries to move the empty tile towards the specified direction.
  // If the move is valid, generate a new board as the moved state and store it
  // in the all_boards and returns the id of it. Otherwise returns -1.
  std::unique_ptr<Board> TryMove(Direction d) const {
    int empty_tile_offset =
        std::find(tiles_.begin(), tiles_.end(), kEmpty) - tiles_.begin();
    auto [row, col] = FromOffset(empty_tile_offset);
    if (row == 0 && d == kUp || row == kLength - 1 && d == kDown ||
        col == 0 && d == kLeft || col == kLength - 1 && d == kRight) {
      return nullptr;
    }

    auto child = std::make_unique<Board>(*this);
    int target_offset = empty_tile_offset + static_cast<int>(d);
    std::swap(child->tiles_[empty_tile_offset], child->tiles_[target_offset]);
    child->score_ +=
        child->ScoreTile(empty_tile_offset) + child->ScoreTile(target_offset) -
        this->ScoreTile(empty_tile_offset) - this->ScoreTile(target_offset);
    child->step_ = step_ + 1;
    child->parent_ = this;
    return child;
  }

  int score() const { return score_; }
  int step() const { return step_; }
  const Board* parent() const { return parent_; }

  void Print(std::array<std::string, kLength>& output) const {
    PrintTiles(tiles_, output);
  }

private:
  static int ScoreTile(int offset, int tile) {
    auto [row, col] = FromOffset(offset);
    auto [vr, vc] = FromOffset(tile);
    return 3 * std::abs(row - vr) + std::abs(col - vc);
  }

  int ScoreTile(int offset) const { return ScoreTile(offset, tiles_[offset]); }

  TileArray tiles_;
  int score_;
  int step_ = 0;
  const Board* parent_ = nullptr;
};

void PrintBoardPath(const Board* board) {
  std::vector<const Board*> boards;
  while (board != nullptr) {
    boards.push_back(board);
    board = board->parent();
  }
  std::array<std::string, kLength> buffer;
  for (std::string& line : buffer) {
    line.append("      ");
  }
  int buffed = 0;
  auto flash = [&buffer, &buffed](int number) {
    std::cout << number - buffed + 1 << " -- " << number << std::endl;
    for (std::string& line : buffer) {
      std::cout << line << std::endl;
      line.clear();
      line.append("      ");
    }
    buffed = 0;
  };
  for (int i = boards.size() - 1; i >= 0; --i) {
    boards[i]->Print(buffer);
    buffer[0].append("      ");
    buffer[1].append("  =>  ");
    buffer[2].append("  =>  ");
    buffer[3].append("      ");
    ++buffed;
    if (buffed >= 5) {
      flash(boards.size() - 1 - i);
    }
  }
  flash(boards.size() - 1);
}

void Go(std::unique_ptr<Board> root) {
  std::unordered_map<uint64_t, std::unique_ptr<Board>> all_boards;
  auto compare_boards_by_id = [&all_boards](uint64_t id_a, uint64_t id_b) {
    return all_boards[id_a]->score() > all_boards[id_b]->score();
  };
  std::priority_queue<uint64_t, std::vector<uint64_t>,
                      decltype(compare_boards_by_id)>
      q(compare_boards_by_id);

  uint64_t root_id = root->GenerateId();
  all_boards[root_id] = std::move(root);
  q.push(root_id);

  std::cout << "Root Id = " << root_id << std::endl;
  std::cout << "Start Searching ========================= " << std::endl;
  while (!q.empty()) {
    uint64_t id = q.top();
    q.pop();
    const Board& board = *all_boards[id];
    if (all_boards.size() % 100000 == 0) {
      std::cout << "[" << id << "]  searched=" << all_boards.size()
                << ", steps=" << board.step() << ", score=" << board.score()
                << std::endl;
    }
    if (id == kOkId) {
      // TODO: output results.
      std::cout << " !!! Result found after " << all_boards.size() << " searches\n";
      PrintBoardPath(&board);
      return;
    }
    if (board.step() > kMaxSteps) {
      // Too deep, no more search.
      // std::cout << "TOO DEEP: [" << id << "]  searched=" << all_boards.size()
      //          << ", steps=" << board.step() << ", score=" << board.score()
      //          << std::endl;
      continue;
    }
    for (Direction d : {kLeft, kRight, kUp, kDown}) {
      std::unique_ptr<Board> child = board.TryMove(d);
      if (child == nullptr) {
        continue;
      }
      uint64_t child_id = child->GenerateId();
      auto [it, inserted] = all_boards.try_emplace(child_id, std::move(child));
      if (inserted) {
        q.push(child_id);
      }
    }
  }
}

TileArray FromText(std::string_view tiles_text) {
  TileArray tiles;
  for (int i = 0; i < tiles.size(); ++i) {
    tiles[i] = tiles_text[i] - 'A';
  }
  return tiles;
}

int main() {
  std::cout << "Hello World!\n";
  TileArray tiles = FromText(
      "AEHC"
      "BFDO"
      "JILG"
      "MNKP");
  Go(std::make_unique<Board>(tiles));
  std::cout << "Go finished!\n";
}
【 在 here080 (hero080) 的大作中提到: 】
: 标  题: Re: 数字华容道程序速度快速下降，比C#慢几十倍
: 发信站: 水木社区 (Sun Dec  5 05:28:36 2021), 站内
:
: 为啥你算出来才60步？我把你的程序用C++重写了一下，算出来要100步……
: 这个结果是秒出的，但是如果我把搜索深度限定在80以内，那我搜了几千万个结点也出不了结果。
:
: Start Searching =========================
:  !!! Result found after 90411 searches
: 0 -- 4
:       A E H C       A E H C       A E H C       A E H C       A E H C
:       B F D O   =>  B F D O   =>  B F D O   =>  B F D O   =>  B F D O   =>
:       J I L G   =>  J I L *   =>  J I * L   =>  J I K L   =>  J I K L   =>
:       M N K *       M N K G       M N K G       M N * G       M N G *
: 5 -- 9
:       A E H C       A E H C       A E H C       A E * C       A E C *
:       B F D O   =>  B F D *   =>  B F * D   =>  B F H D   =>  B F H D   =>
:       J I K *   =>  J I K O   =>  J I K O   =>  J I K O   =>  J I K O   =>
:       M N G L       M N G L       M N G L       M N G L       M N G L
: 10 -- 14
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       B F H *   =>  B F * H   =>  B F K H   =>  B F K H   =>  B F K H   =>
:       J I K O   =>  J I K O   =>  J I * O   =>  J I G O   =>  J I G O   =>
:       M N G L       M N G L       M N G L       M N * L       M N L *
: 15 -- 19
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       B F K H   =>  B F K H   =>  B F * H   =>  B F H *   =>  B F H G   =>
:       J I G *   =>  J I * G   =>  J I K G   =>  J I K G   =>  J I K *   =>
:       M N L O       M N L O       M N L O       M N L O       M N L O
: 20 -- 24
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       B F H G   =>  B F H G   =>  B F H G   =>  B F H G   =>  B F H G   =>
:       J I * K   =>  J I L K   =>  J I L K   =>  J I L *   =>  J I * L   =>
:       M N L O       M N * O       M N O *       M N O K       M N O K
: 25 -- 29
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       B F * G   =>  B F G *   =>  B F G L   =>  B F G L   =>  B F G L   =>
:       J I H L   =>  J I H L   =>  J I H *   =>  J I H K   =>  J I H K   =>
:       M N O K       M N O K       M N O K       M N O *       M N * O
: 30 -- 34
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       B F G L   =>  B F G L   =>  B F G *   =>  B F * G   =>  B F K G   =>
:       J I * K   =>  J I K *   =>  J I K L   =>  J I K L   =>  J I * L   =>
:       M N H O       M N H O       M N H O       M N H O       M N H O
: 35 -- 39
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       B F K G   =>  B F K G   =>  B F K G   =>  B F K G   =>  B F * G   =>
:       J I H L   =>  J I H L   =>  J I H *   =>  J I * H   =>  J I K H   =>
:       M N * O       M N O *       M N O L       M N O L       M N O L
: 40 -- 44
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       B F G *   =>  B F G H   =>  B F G H   =>  B F G H   =>  B F G H   =>
:       J I K H   =>  J I K *   =>  J I K L   =>  J I K L   =>  J I K L   =>
:       M N O L       M N O L       M N O *       M N * O       M * N O
: 45 -- 49
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       B F G H   =>  B F G H   =>  B F G H   =>  B * G H   =>  * B G H   =>
:       J I K L   =>  * I K L   =>  I * K L   =>  I F K L   =>  I F K L   =>
:       * M N O       J M N O       J M N O       J M N O       J M N O
: 50 -- 54
:       A E C D       A E C D       A E C D       A E C D       A E C D
:       I B G H   =>  I B G H   =>  I B G H   =>  I B G H   =>  I B G H   =>
:       * F K L   =>  J F K L   =>  J F K L   =>  J F K L   =>  J F * L   =>
:       J M N O       * M N O       M * N O       M N * O       M N K O
: 55 -- 59
:       A E C D       A E C D       A E C D       A E C D       A * C D
:       I B G H   =>  I B G H   =>  * B G H   =>  B * G H   =>  B E G H   =>
:       J * F L   =>  * J F L   =>  I J F L   =>  I J F L   =>  I J F L   =>
:       M N K O       M N K O       M N K O       M N K O       M N K O
: 60 -- 64
:       A C * D       A C G D       A C G D       A C G D       A C G D
:       B E G H   =>  B E * H   =>  B E F H   =>  B E F H   =>  B * F H   =>
:       I J F L   =>  I J F L   =>  I J * L   =>  I * J L   =>  I E J L   =>
:       M N K O       M N K O       M N K O       M N K O       M N K O
: 65 -- 69
:       A C G D       A C * D       A * C D       A F C D       A F C D
:       B F * H   =>  B F G H   =>  B F G H   =>  B * G H   =>  B E G H   =>
:       I E J L   =>  I E J L   =>  I E J L   =>  I E J L   =>  I * J L   =>
:       M N K O       M N K O       M N K O       M N K O       M N K O
: 70 -- 74
:       A F C D       A F C D       A F C D       A F C D       A F C D
:       B E G H   =>  B E G H   =>  B E G H   =>  B E G H   =>  B E G H   =>
:       I J * L   =>  I J K L   =>  I J K L   =>  I J K L   =>  * J K L   =>
:       M N K O       M N * O       M * N O       * M N O       I M N O
: 75 -- 79
:       A F C D       A F C D       A F C D       A F C D       A F C D
:       * E G H   =>  E * G H   =>  E J G H   =>  E J G H   =>  E J G H   =>
:       B J K L   =>  B J K L   =>  B * K L   =>  * B K L   =>  I B K L   =>
:       I M N O       I M N O       I M N O       I M N O       * M N O
: 80 -- 84
:       A F C D       A F C D       A F C D       A F C D       A F C D
:       E J G H   =>  E J G H   =>  E J G H   =>  E J G H   =>  E * G H   =>
:       I B K L   =>  I B K L   =>  I B * L   =>  I * B L   =>  I J B L   =>
:       M * N O       M N * O       M N K O       M N K O       M N K O
: 85 -- 89
:       A * C D       A C * D       A C G D       A C G D       A C G D
:       E F G H   =>  E F G H   =>  E F * H   =>  E F B H   =>  E F B H   =>
:       I J B L   =>  I J B L   =>  I J B L   =>  I J * L   =>  I J K L   =>
:       M N K O       M N K O       M N K O       M N K O       M N * O
: 90 -- 94
:       A C G D       A C G D       A C G D       A C G D       A C * D
:       E F B H   =>  E F B H   =>  E * B H   =>  E B * H   =>  E B G H   =>
:       I J K L   =>  I * K L   =>  I F K L   =>  I F K L   =>  I F K L   =>
:       M * N O       M J N O       M J N O       M J N O       M J N O
: 95 -- 99
:       A * C D       A B C D       A B C D       A B C D       A B C D
:       E B G H   =>  E * G H   =>  E F G H   =>  E F G H   =>  E F G H   =>
:       I F K L   =>  I F K L   =>  I * K L   =>  I J K L   =>  I J K L   =>
:       M J N O       M J N O       M J N O       M * N O       M N * O
: 100 -- 100
:       A B C D
:       E F G H   =>
:       I J K L   =>
:       M N O *
: 【 在 finlab (挨踢卢瑟) 的大作中提到: 】
: : 标  题: Re: 数字华容道程序速度快速下降，比C#慢几十倍
: : 发信站: 水木社区 (Sat Dec  4 09:22:06 2021), 站内
: :
: : 这段程序是求解数字华容道。 就是在N*N的矩阵里，随意放入数字1到N*N-1，留1个空格，然后利用空格移动数字，使的数字按顺序排列。
: :
: : 因为闺女这几天老玩这个，非常溜，1分钟就能完成， 我就想给闺女露一手，编程求解出更快的走法。
: :
: : 一开始的C++程序慢，使因为未unordered_set提供的hash函数太差，改成 hash=hash*13+A[i]之后，C++就比C#更快了。
: :
: : 启发式搜索就是宽度优先搜索中，普通队列换成优先队列，优先搜索最接近目标的分支。会更快找打解法，但是不能保证是最短的走法。
: :
: : 一个输出如下：*表示空格
: :
: : 0------
: :         1       5       8       3
: :         2       6       4       15
: :         10      9       12      7
: :         13      14      11      *
: : 1------
: :         1       5       8       3
: :         2       6       4       15
: :         10      9       12      *
: :         13      14      11      7
: : 2------
: :         1       5       8       3
: :         2       6       4       15
: :         10      9       *       12
: :         13      14      11      7
: : 3------
: :         1       5       8       3
: :         2       6       4       15
: :         10      9       11      12
: :         13      14      *       7
: : 4------
: :         1       5       8       3
: :         2       6       4       15
: :         10      9       11      12
: :         13      14      7       *
: : 5------
: :         1       5       8       3
: :         2       6       4       15
: :         10      9       11      *
: :         13      14      7       12
: : 6------
: :         1       5       8       3
: :         2       6       4       *
: :         10      9       11      15
: :         13      14      7       12
: : 7------
: :         1       5       8       3
: :         2       6       *       4
: :         10      9       11      15
: :         13      14      7       12
: : 8------
: :         1       5       *       3
: :         2       6       8       4
: :         10      9       11      15
: :         13      14      7       12
: : 9------
: :         1       5       3       *
: :         2       6       8       4
: :         10      9       11      15
: :         13      14      7       12
: : 10------
: :         1       5       3       4
: :         2       6       8       *
: :         10      9       11      15
: :         13      14      7       12
: : 11------
: :         1       5       3       4
: :         2       6       *       8
: :         10      9       11      15
: :         13      14      7       12
: : 12------
: :         1       5       3       4
: :         2       6       11      8
: :         10      9       *       15
: :         13      14      7       12
: : 13------
: :         1       5       3       4
: :         2       6       11      8
: :         10      9       15      *
: :         13      14      7       12
: : 14------
: :         1       5       3       4
: :         2       6       11      8
: :         10      9       15      12
: :         13      14      7       *
: : 15------
: :         1       5       3       4
: :         2       6       11      8
: :         10      9       15      12
: :         13      14      *       7
: : 16------
: :         1       5       3       4
: :         2       6       11      8
: :         10      9       *       12
: :         13      14      15      7
: : 17------
: :         1       5       3       4
: :         2       6       *       8
: :         10      9       11      12
: :         13      14      15      7
: : 18------
: :         1       5       3       4
: :         2       6       8       *
: :         10      9       11      12
: :         13      14      15      7
: : 19------
: :         1       5       3       4
: :         2       6       8       12
: :         10      9       11      *
: :         13      14      15      7
: : 20------
: :         1       5       3       4
: :         2       6       8       12
: :         10      9       11      7
: :         13      14      15      *
: : 21------
: :         1       5       3       4
: :         2       6       8       12
: :         10      9       11      7
: :         13      14      *       15
: : 22------
: :         1       5       3       4
: :         2       6       8       12
: :         10      9       *       7
: :         13      14      11      15
: : 23------
: :         1       5       3       4
: :         2       6       8       12
: :         10      9       7       *
: :         13      14      11      15
: : 24------
: :         1       5       3       4
: :         2       6       8       *
: :         10      9       7       12
: :         13      14      11      15
: : 25------
: :         1       5       3       4
: :         2       6       *       8
: :         10      9       7       12
: :         13      14      11      15
: : 26------
: :         1       5       3       4
: :         2       6       7       8
: :         10      9       *       12
: :         13      14      11      15
: : 27------
: :         1       5       3       4
: :         2       6       7       8
: :         10      9       11      12
: :         13      14      *       15
: : 28------
: :         1       5       3       4
: :         2       6       7       8
: :         10      9       11      12
: :         13      14      15      *
: : 29------
: :         1       5       3       4
: :         2       6       7       8
: :         10      9       11      *
: :         13      14      15      12
: : 30------
: :         1       5       3       4
: :         2       6       7       *
: :         10      9       11      8
: :         13      14      15      12
: : 31------
: :         1       5       3       4
: :         2       6       *       7
: :         10      9       11      8
: :         13      14      15      12
: : 32------
: :         1       5       3       4
: :         2       *       6       7
: :         10      9       11      8
: :         13      14      15      12
: : 33------
: :         1       *       3       4
: :         2       5       6       7
: :         10      9       11      8
: :         13      14      15      12
: : 34------
: :         1       3       *       4
: :         2       5       6       7
: :         10      9       11      8
: :         13      14      15      12
: : 35------
: :         1       3       6       4
: :         2       5       *       7
: :         10      9       11      8
: :         13      14      15      12
: : 36------
: :         1       3       6       4
: :         2       5       7       *
: :         10      9       11      8
: :         13      14      15      12
: : 37------
: :         1       3       6       4
: :         2       5       7       8
: :         10      9       11      *
: :         13      14      15      12
: : 38------
: :         1       3       6       4
: :         2       5       7       8
: :         10      9       11      12
: :         13      14      15      *
: : 39------
: :         1       3       6       4
: :         2       5       7       8
: :         10      9       11      12
: :         13      14      *       15
: : 40------
: :         1       3       6       4
: :         2       5       7       8
: :         10      9       11      12
: :         13      *       14      15
: : 41------
: :         1       3       6       4
: :         2       5       7       8
: :         10      *       11      12
: :         13      9       14      15
: : 42------
: :         1       3       6       4
: :         2       *       7       8
: :         10      5       11      12
: :         13      9       14      15
: : 43------
: :         1       3       6       4
: :         *       2       7       8
: :         10      5       11      12
: :         13      9       14      15
: : 44------
: :         1       3       6       4
: :         10      2       7       8
: :         *       5       11      12
: :         13      9       14      15
: : 45------
: :         1       3       6       4
: :         10      2       7       8
: :         5       *       11      12
: :         13      9       14      15
: : 46------
: :         1       3       6       4
: :         10      2       7       8
: :         5       9       11      12
: :         13      *       14      15
: : 47------
: :         1       3       6       4
: :         10      2       7       8
: :         5       9       11      12
: :         13      14      *       15
: : 48------
: :         1       3       6       4
: :         10      2       7       8
: :         5       9       *       12
: :         13      14      11      15
: : 49------
: :         1       3       6       4
: :         10      2       *       8
: :         5       9       7       12
: :         13      14      11      15
: : 50------
: :         1       3       *       4
: :         10      2       6       8
: :         5       9       7       12
: :         13      14      11      15
: : 51------
: :         1       *       3       4
: :         10      2       6       8
: :         5       9       7       12
: :         13      14      11      15
: : 52------
: :         1       2       3       4
: :         10      *       6       8
: :         5       9       7       12
: :         13      14      11      15
: : 53------
: :         1       2       3       4
: :         *       10      6       8
: :         5       9       7       12
: :         13      14      11      15
: : 54------
: :         1       2       3       4
: :         5       10      6       8
: :         *       9       7       12
: :         13      14      11      15
: : 55------
: :         1       2       3       4
: :         5       10      6       8
: :         9       *       7       12
: :         13      14      11      15
: : 56------
: :         1       2       3       4
: :         5       *       6       8
: :         9       10      7       12
: :         13      14      11      15
: : 57------
: :         1       2       3       4
: :         5       6       *       8
: :         9       10      7       12
: :         13      14      11      15
: : 58------
: :         1       2       3       4
: :         5       6       7       8
: :         9       10      *       12
: :         13      14      11      15
: : 59------
: :         1       2       3       4
: :         5       6       7       8
: :         9       10      11      12
: :         13      14      *       15
: : 60------
: :         1       2       3       4
: :         5       6       7       8
: :         9       10      11      12
: :         13      14      15      *
: :
: :
: :
: :
: :
: : 【 在 DoorWay 的大作中提到: 】
: : : 大眼一扫，优先队列，上次见是opecv里分水岭算法。
: : : 算法mental model是根据灰度值，将图像素三维化，假设有高度，然后注水。
: : : 低的地方汇聚成洼，高的地方分割成坝，达到分割的效果。
: : : ...................
: :
: : --
: :
: : ※ 来源:·水木社区 http://www.mysmth.net·[FROM: 123.112.64.*]
:
:
: --
:
: ※ 来源:·水木社区 mysmth.net·[FROM: 73.15.185.*]
--
FROM 73.15.185.*

你这个优化方式太看运气了吧。如果最优节点恰好是个死胡同，那不就卡死所有正确答案了？

你选的这个15步标准，是对这一个初始条件有用吧？换一个初始条件是不是就有可能不行了？
【 在 finlab (挨踢卢瑟) 的大作中提到: 】
: 标  题: Re: 数字华容道程序速度快速下降，比C#慢几十倍
: 发信站: 水木社区 (Sun Dec  5 07:58:10 2021), 站内
:
: 我贴的答案是后来优化过的。
:
: 在主循环中，记录全局最优节点，也就是score最小的。
:
: 然后
:
: if (node->gen - best->gen >15 && node->score > best->score)
:            continue;
:
: 就是如果比最优节点多走了15步，还不如最优解点，就不再搜索这个分支。
:
: 这时候只要52步就能完成。
:
: 我把剪枝额步数跳到14， 就反而要60步。
:
: 如果再少， 可能就把正确的路径都剪掉了， 出不来答案了。
:
:
: 【 在 here080 的大作中提到: 】
: : 为啥你算出来才60步？我把你的程序用C++重写了一下，算出来要100步……
: : 这个结果是秒出的，但是如果我把搜索深度限定在80以内，那我搜了几千万个结点也出不了结果。
: : Start Searching =========================
: : ...................
:
: --
:
: ※ 来源:·水木社区 http://www.mysmth.net·[FROM: 123.112.64.*]
--
FROM 73.15.185.*

关键是你能不能保证任意有解的初始状态，你这个算法都能出解？
【 在 finlab (挨踢卢瑟) 的大作中提到: 】
: 标  题: Re: 数字华容道程序速度快速下降，比C#慢几十倍
: 发信站: 水木社区 (Sun Dec  5 08:26:16 2021), 站内
:
: 我确实是试了几次，试出来这个数字，
:
: 不过实际上人工求解的时候有固定的解法。 就是固定一行，再摆下一行。
:
: 在当前局势下，再多摆好一个，花费的步骤上限是可以确定的。  不过手工我也不熟，不好确定。
:
: 还有一个优化思路，就是参照人工，判断第一行摆好了，就做个标记，以后不再动。然后是第二行。
:
: 但最后两行要一起完成。
:
: 这样应该可以更快找到一个解法，但是用的步数会多一些。
:
:
: 【 在 here080 的大作中提到: 】
: : 你这个优化方式太看运气了吧。如果最优节点恰好是个死胡同，那不就卡死所有正确答案了？
: : 你选的这个15步标准，是对这一个初始条件有用吧？换一个初始条件是不是就有可能不行了？
: :
:
: --
:
: ※ 来源:·水木社区 http://www.mysmth.net·[FROM: 123.112.64.*]
--
FROM 73.15.185.*