0

制約の問題をスケーリングするのに苦労しています (大きな値の場合、および/または解決策を探すのではなく最適化しようとすると失敗します)。以前の質問からのアドバイスに基づいて、検索スペースを分割するためのいくつかの手順を実行しましたが、まだ行き詰まっています。この計算を最適化するのに役立つテクニックは他にありますか?

%%% constants %%%
#const nRounds = 4.
#const nPlayers = 20.
#const nRooms = 4.
#const nDecks = 7.

player(1..nPlayers).
room(1..nRooms).
deck(1..nDecks).
writer(1,1;2,2;3,3;4,4).

% For reference - that's what I started with:
%nRounds { seat(Player, 1..nRooms, 1..nDecks) } nRounds :- player(Player).

% Now instead I'm using a few building blocks
% Each player shall only play nRounds decks
nRounds { what(Player, 1..nDecks) } nRounds :- player(Player).
% Each player shall only play in up to nRounds rooms.
1 { where(Player, 1..nRooms) } nRounds :- player(Player).
% For each deck, 3 or 4 players can play in each room.
3 { who(1..nPlayers, Room, Deck) } 4 :- room(Room), deck(Deck).
% Putting it all together, hopefully, this leads to fewer combinations than the original monolithic choice rule.
{ seat(Player, Room, Deck) } :- what(Player, Deck), where(Player, Room), who(Player, Room, Deck).

% A player can only play a deck in a single room.
:- seat(Player, Room1, Deck), seat(Player, Room2, Deck), Room1 != Room2.
% A player must play nRounds decks overall.
:- player(Player), #count { Room, Deck: seat(Player, Room, Deck) } != nRounds.
% Any deck in any room must be played by 3-4 players.
legal_player_count(3..4).
:- room(Room), deck(Deck),
  Players = #count { Player: seat(Player, Room, Deck) },
  Players > 0,
  not legal_player_count(Players).
% Writers cannot play their own decks.
:- writer(Player, Deck), seat(Player, _, Deck).
% At least one non-playing player per room.
:- deck(Deck),
  Playing = #count { Player, Room: seat(Player, Room, Deck) },
  Rooms = #count { Room: seat(_, Room, Deck) },
  nPlayers - Playing < Rooms.

%:- room(R1), deck(D), room(R2), X = #sum { P: seat(P, R1, D) }, Y = #sum { P: seat(P, R2, D) }, R1 > R2, X > Y.

#minimize { D: decks(D) }.

#show decks/1.
#show seat/3.
% #show common_games/3.

これが管理可能になると、次のような最適な構成を選択するための最適化目標をさらに追加したいと考えています。

% Input points(P, R, D, X) to report points.
% winner(P, R, D) :- points(P, R, D, X), X = #max { Y : points(_, R, D, Y) }.
% Compute each player's rank based on each round:
% rank(P, D, R) :- points(P, Room, D, X), winner(Winner, Room, D), D_ = D - 1,
%   rank(P, D_, R_),
%   R = some_combination_of(X, P=Winner, R_).
% latest_rank(P, R) :- D = #max { DD: rank(P, DD, _) }, rank(P, D, R).

% Total number of decks played throughout the night (for minimisation?)
decks(Decks) :- Decks = #count { Deck: seat(_, _, Deck) }.
% Total number of games played together by the same players (for minimisation)
% The total sum of this predicate is invariant
% Minimisation should took place by a superlinear value (e.g. square)
common_games(Player1, Player2, Games) :-
  player(Player1), player(Player2), Player1 != Player2,
  Games = #count { Room, Deck:
    seat(Player1, Room, Deck),
    seat(Player2, Room, Deck)
  }, Games > 0.

% For example:
% common_game_penalty(X) :- X = #sum { Y*Y, P1, P2 : common_games(P1, P2, Y) }.

% Another rank-based penalty needs to be added once the rank mechanics are there

% Then the 2 types of penalties need to be combined and / or passed to the optimiser

更新 - 問題の説明

  • Pプレイヤーが集まってクイズナイト。DデッキとRルームが 遊べます。
  • 各部屋には 3 人または 4 人のプレイヤーしか収容できません (スペースではなく、ゲームのルールによります)。
  • 各デッキは最大で 1 回プレイされ、複数の部屋で同時にプレイされるため、ある意味でデッキは「ラウンド」と同義です。
  • 各プレイヤーは同じデッキを最大 1 回しかプレイできません。
  • 各プレイヤーは、夜間に N 回しかプレイできません (N はほぼ固定されており、4 回です)。
  • したがって、夜間に 9 つのデッキがプレイされる場合 (つまり、多数のプレイヤーが存在する場合)、それぞれがこれらの 9 つのデッキのうち 4 つをプレイします。
  • したがって、各プレイヤーが各「デッキ/ラウンド」でプレイする必要はありません。実際、各デッキにはライターがいて、通常は参加しているプレイヤーの 1 人です。
  • 当然、ライターは自分のデッキをプレイすることはできないため、そのラウンドに参加することはできません。さらに、各デッキ/ラウンドでは、誰かが各部屋で質問を読まなければならないため、16 人のプレイヤーが存在し、4 つの部屋がある場合、16 人のプレイヤー全員がプレイすることは不可能です。それぞれ 3 人のプレーヤーがいる 4 つの部屋 (そして残りの 4 人のプレーヤーが質問を読み上げる) または 4 人のプレーヤーがいる 3 つの部屋 (3 人のプレーヤーが質問を読み上げ、1 つの観戦) を持つことができます。

うまくいけば、これで混乱が解消されます。そうでない場合は、より複雑な例を挙げることができますが、基本的には、4 つの部屋と 30 人のプレーヤーがあるとします。

  • プレイする 16 人と、質問を読み上げる 4 人を選択します。
  • 次に、1/4 のデッキ/ラウンドをプレイした 16 人と、まだ 0/4 のままの 14 人がいるとします。
  • したがって、残りの 14 人にプレイさせる (1 ルームあたり 4、4、3、3 人のプレイヤー) か、引き続きルーム ユーティリティを最大化して、第 2 ラウンド後に全員が少なくとも 1 回プレイし、2/30 人のプレイヤーがすでに 2/ をプレイするようにすることができます。 4 ゲーム。
  • そのため、全員がちょうど 4 デッキ/ラウンドをプレイするまで、何人かの人を選び続けます。

PS ラウンドには 2 つの概念があります。1 つは全員が 4 をプレイする個人レベルで、もう 1 つはリーグ レベルで 4 を超えるデッキがいくつかあり、各デッキは出席者全員の目には「ラウンド」と見なされます。 . 私が理解したところでは、これが最初によく理解できなかったセットアップに関する最も紛らわしい部分でした。

4

1 に答える 1