3

船が重なったり、接触したり (斜めであっても) できないというルールに従って、多数の船をボードに配置するためのアルゴリズムの構築についてアドバイスが必要です。ランダムな位置を選択した後、残りの船に十分なスペースを確保するにはどうすればよいですか?

たとえば、6x6 ボード (2D 配列) に 5 隻の船を合わせたいとします。船のサイズは : 5、4、3、1、1 です。配置方法はいくつかありますが、その 1 つを以下に示します。

 -------------
| 1 1 1 1 1 . |
| . . . . . . |
| 2 2 2 2 . 4 |
| . . . . . . |
| 3 3 3 . . 5 |
| . . . . . . |
 -------------

ランダムアルゴリズムは次のようになります。

1. Get next ship
2. Get random cell and orientation
3. Try to fit ship (find any conflicts)
    3a. If ship cannot fit, try different 
        cell and orientation, untill all cells 
        have been tried (function fails)
    3b. If ship fits, get another ship (goto 1)

しかし、私がそれを使用すると、次のように終わる可能性があります (編集: ステップ 0 で船のサイズによるソートを反映するように変更されました):

 -------------
| . 3 3 3 . 4 |   5
| . . . . . . |
| . 2 2 2 2 . |
| . . . . . . |
| 1 1 1 1 1 . |
| . . . . . . |
 -------------

1セルサイズの船の居場所がないことを意味します。どうすればそのような問題を回避できますか? verifyRestShipsWillFit()3b に配置する関数をどのように実装しますか?

4

3 に答える 3

2

いくつかのヒューリスティックを使用して船を並べ替えます。たとえば、最大のものを最初に並べます。次に、空のボードと船の完全なリストから始めて、配置を再帰的にします。これは基本的にツリー検索です。

不変クラスがある場合は、再帰を使用する方が常に簡単であることを覚えておいてください。船をボードに配置すると、ボードを変更せずに新しいボードが作成されます。

Board GetRandomBoard()
{
   List<Ship> ships = { .. }   // List of all ships.
   Board = Board.Empty();
   Board result = PlaceShips(ships, board);
   return result; // You could have a retry here as well if it fails.
}

private Board PlaceShips(IEnumerable<Ship> shipsRemaining, Board board)
{    
   Ship shipToPlace = shipsRemaining.FirstOrDefault();

   // If all ships were placed, we are done.
   if (shipToPlace == null)
      return board;

   int attempts = 0;       
   while (attempts++ < MaxAttempts)
   {
       // Get a position for the new ship that is OK with the current board.
       ShipPosition pos = GetRandomShipPosition(board, shipToPlace); 

       // If it isn't possible to find such a position, this branch is bad.
       if (pos == null)
          return null;

       // Create a new board, including the new ship.
       Board newBoard = new board.WithShip(shipToplace, pos);

       // Recurse by placing remaining ships on the new board.
       board nextBoard = PlaceShips(shipsRemaining.Skip(1).ToList(), newBoard);
       if (nextBoard != null)
          return nextBoard;
   }
   return null;
}
于 2013-05-02T12:10:02.257 に答える
1

このような小さな問題の場合は、これが最も簡単です

1. Get next ship
2. Get random cell and orientation
3. Try to fit ship (find any conflicts)
    3a. If ship doesn't fit there, **delete all ships and start over**
    3b. If ship fits, get another ship (goto 1)

終了について偏執的である場合は、(高い) 反復制限を設定し、決定論的な構成にフォールバックします。

于 2013-05-02T12:01:01.407 に答える