私は、プレイヤーがゲームボードで最初から最後まで自分の道を見つけなければならないゲームを作ろうとしています。
ご覧のとおり、このゲームボードにはたくさんの赤い円形の障害物が含まれています。ゲームに勝つためには、プレイヤーは最小限の障害物を取り除く必要があります。だから私の質問は、パスを解放するために、削除する障害物の最小量をプログラムで見つけるにはどうすればよいですか？自由行程は、円が重なり合っておらず、接触していない間のスペースと見なされます。
したがって、私が本当に必要としているのは、削除する円の最小数です。実際のパスは必要ありません。これを行う簡単な方法はありますか？
そして、このゲームボードの理解を補うために、円はそれぞれ同じ半径を持ち、黒い線で制限されています。
また、直線で移動する必要はありません。
グラフ理論のmaximum flow問題です。
すべての円がグラフのノードであると仮定します。さらに、2つの特別なノードを導入します：TOPとBOTTOM。TOP / BOTTOM側と交差する場合は、これらのノードに円を接続します。円が交差する場合は、円に対応するノードを相互に接続します。
次に、 TOPをソース、BOTTOMをシンク、またはその逆として、このグラフで最小カットを見つける必要があります。Max-flow_min-cut_theoremを使用して解決できます。それが述べているのは、それMinimum-cut problemは最大フロー問題と同等であるということです。あなたはTopCoderMax-Flow problemで解決する方法の詳細を見つけることができます。
各ノードを1回しか通過できないため、ノードを、各円にインノードとアウトノードを備えた容量の有向エッジに変換する必要があります。最大フローアルゴリズムは、結果のグラフの問題を解決し、円間の接続ではなく円を削除しているという事実を考慮に入れます。ノードを削除することで常にエッジを削除できるため、この問題では、エッジではなくグラフ内のノードを削除することをお勧めします。ノードを追加で削除すると、複数のエッジが削除される可能性があります。
ちなみに、同様の問題はUvaOnlineJudgeで見つけることができます。裁判官にこのタスクを解決してみるのは良い考えです。そうすれば、あなたはあなたの解決策が正しいことを確信するでしょう。
しし座が書いたものを視覚化しようとして、次の図を作成しました。
グラフの変換では、このようなものが機能する可能性があります。
2つの円が重なっている場合は、2つの円の間に壁（青い線）を作成します。上と下の境界線も追加することを忘れないでください。これにより、いくつかのリージョンが作成されます。これらはグラフのすべてのノードになります。
次に、エッジ、つまりあるノードから別のノードに移動するためのコストを見つける必要があります。2つの隣接する領域を取得します（壁を共有します）。次に、ブルートフォース、または思いついた巧妙な方法によって、この領域から別の領域に移動するコストを決定します。円を削除すると、つまり、その円に向かうすべての壁が削除されます。これにより2つの領域が1つの領域になる場合、エッジのコストは1です。2つの領域を結合するために2つの円（それらが持つすべての壁）を削除する必要がある場合、コストは2です。
いくつかのエッジ（緑）が描かれています。開始領域から終了領域に移動する必要があります。これで、毎日の加重グラフが得られました。
これはかなり改善できると思いますが、演習として残しておきます=）
この場合、最小値は3です。
警告、絵は手で描かれています、私はいくつかの壁、端と領域を忘れました。説明のみを目的としています。
よし、これを pygame で視覚化することにしました。
予想以上に大変でした。
他の提案と同様のアイデアは、Max Flowを使用することです。ソースからシンクへの流れのボトルネックは、流れが最も密集している場所です。この密集したボトルネック (つまりmin-cut ) でグラフを半分に切ると、円の数が最小になります。maxflow = min-cut となります。
ここに私が取ったステップがあります：
円をランダムに生成できる pygame の世界を作成する
円の間のすべての衝突を解決する関数を作成します。
これには、円を x 座標で並べ替える必要がありました。Circle[0] のすべての衝突を見つけるために、x 値が circle[0] の sx 値より 2*radius より大きい円が見つかるまで、衝突をテストする配列に沿って移動し続けます。その後、circle[0 をポップできます。 ] プロセスを繰り返します..
手順 4 ～ 5 は「 findflow()関数」で実行されます。
ノードを持つ円を表す基本的な無向 networkX グラフを作成します。対応する円が衝突する場合にのみノードを接続します。
そして、ここからが難しくなります.無向グラフから新しい有向グラフを作成します。エッジではなく円 (ノード) を通るフローを計算する必要があったため、各ノードを 2 つのノードに分割し、その間にエッジを配置する必要がありました。
ノード X がノード Y (Y<->X) (元のグラフ) に接続されているとします。
Xa を Xb に接続するように、X を Xa と Xb に変更します (Xa->Xb) また、Y を (Ya->Yb) に変更します。
また、X と Y の間の元の接続を表すために、(Yb->Xa) と (Xb->Ya) を追加する必要があります。
無向グラフのすべての辺には capacity=1 が与えられます (たとえば、円は 1 回しか交差できません)。
flowValue は整数です。これは最小カット (またはソースからシンクへの最大フロー) です。これが私たちが探し求めていた答えです。これは、削除する必要がある円の最小数を表します。
ボーナス割り当て:
削除する円の数があるのはいいことですが、削除する必要がある正確な円を知りたいのです。これを行うには、flowGraph で最小カットが実際に発生する場所を見つける必要があります。私はこれを行う方法を理解することができましたが、私の実装にはどこかにバグがあるため、カットがわずかに間違って選択され、間違った円が得られることがあります。
最小カットを見つけるために、ステップ 6 で生成された flowGraph を使用します。このグラフのボトルネックは最小カットになるという考えです。ソースからシンクへの流れを試みると、ボトルネックの周りのすべてのエッジが最大容量になるため、ボトルネックで行き詰まります。したがって、単純に DFS ( Depth First Search ) を使用して、可能な限り下に流れます。DFS は、フロー グラフの最大容量に達していないエッジに沿ってのみ移動できます。(たとえば、フローは 1 ではなく 0 です)。ソースから DFS を使用して、self.seen に格納されているすべてのノードを記録しました。DFS の後、表示されたすべてのノードについて、ノードが DFS では表示されなかったノードに対して最大容量のエッジを持っているかどうかを確認します。そのようなノードはすべて最小カットにあります。
これは、私が実行したシミュレーションの 1 つの図です。
円を削除して、ペイントで塗りつぶしました (実際に円の間に隙間があることを確認するには、少し拡大する必要があるかもしれません)。
学習:
Python でも速度は問題なく、1000 円まで実行できます。
思ったより難しかったし、DFS を使用して元の円を見つけようとすると、まだバグがあります。（誰かがバグを見つけるのを手伝ってくれるなら、それは素晴らしいことです）.
コードは最初はエレガントでしたが、視覚化などを変更するためにハックを追加し続けました.
作業コード (DFS のわずかな時折のバグは別として):
__author__ = 'Robert'
import pygame
import networkx
class CirclesThing():
def __init__(self,width,height,number_of_circles):
self.removecircles = False #display removable circles as green.
self.width = width
self.height = height
self.number_of_circles = number_of_circles
self.radius = 40
from random import randint
self.circles = sorted(set((randint(self.radius,width-self.radius),randint(2*self.radius,height-2*self.radius)) for i in range(self.number_of_circles)))
self.sink = (self.width/2, self.height-10)
self.source = (self.width/2, 10)
self.flowValue,self.flowGraph = self.find_flow()
self.seen = set()
self.seen.add(self.source)
self.dfs(self.flowGraph,self.source)
self.removable_circles = set()
for node1 in self.flowGraph:
if node1 not in self.seen or node1==self.source:
continue
for node2 in self.flowGraph[node1]:
if self.flowGraph[node1][node2]==1:
if node2 not in self.seen:
self.removable_circles.add(node1[0])
def find_flow(self):
"finds the max flow from source to sink and returns the amount, along with the flow graph"
G = networkx.Graph()
for node1,node2 in self.get_connections_to_source_sink()+self.intersect_circles():
G.add_edge(node1,node2,capacity=1)
G2 = networkx.DiGraph()
for node in G:
if node not in (self.source,self.sink):
G2.add_edge((node,'a'),(node,'b'),capacity=1) #each node is split into two new nodes. We add the edge between the two new nodes flowing from a to b.
for edge in G.edges_iter():
if self.source in edge or self.sink in edge:
continue #add these edges later
node1,node2 = edge
G2.add_edge((node1,'b'),(node2,'a'),capacity=1) #if we flow through a circle (from node1a to node1b) we need to be able to flow from node1b to all node1's children
G2.add_edge((node2,'b'),(node1,'a'),capactiy=1) #similarly for node2..
for node in G[self.source]:
G2.add_edge(self.source,(node,'a'))
for node in G[self.sink]:
G2.add_edge((node,'b'),self.sink)
flowValue, flowGraph = networkx.ford_fulkerson(G2,self.source,self.sink)
return flowValue, flowGraph
def dfs(self,g,v):
"depth first search from source of flowGraph. Don't explore any nodes that are at maximum capacity. (this means we can't explore past the min cut!)"
for node in g[v]:
if node not in self.seen:
self.seen.add(node)
if g[v][node]!=1 or v==self.source:
self.dfs(g,node)
def display(self):
self.draw_circles()
self.draw_circles(circle_radius=5, circle_colour=(255,0,0))
if not self.removecircles:
lines = self.intersect_circles()
self.draw_lines(lines)
self.draw_source_sink()
def draw_circles(self,circle_radius=None,circle_colour=(0,0,255),circles=None):
if circle_radius is None:
circle_radius = self.radius
if circles is None:
circles = self.circles
circle_thickness = 2
for pos in circles:
cc = circle_colour if pos not in self.removable_circles else (100,200,0) #change colour of removable circles
ct = circle_thickness if pos not in self.removable_circles else 4 #thicken removable circles
if pos not in self.removable_circles or not self.removecircles:
pygame.draw.circle(screen, cc, pos, circle_radius, ct)
def intersect_circles(self):
colliding_circles = []
for i in range(len(self.circles)-1):
for j in range(i+1,len(self.circles)):
x1,y1 = self.circles[i]
x2,y2 = self.circles[j]
if x2-x1>2*self.radius+5: #add 5 to make a more obvious gap visually
break #can't collide anymore.
if (x2-x1)**2 + (y2-y1)**2 <= (2*self.radius)**2+5:
colliding_circles.append(((x1,y1),(x2,y2)))
return colliding_circles
def draw_lines(self,lines,line_colour=(255, 0, 0)):
for point_pair in lines:
point1,point2 = point_pair
try:
tot = self.flowGraph[(point1,'b')][(point2,'a')] + self.flowGraph[(point2,'b')][(point1,'a')] #hack, does anything flow between the two circles?
except KeyError:
tot = 0
thickness = 1 if tot==0 else 3
lc = line_colour if tot==0 else (0,90,90)
pygame.draw.line(screen, lc, point1, point2, thickness)
def draw_source_sink(self):
self.draw_circles(circles=(self.sink,self.source),circle_radius=15,circle_colour=(0,255,0))
bottom_line = ((0,self.height-3*self.radius),(self.width,self.height-3*self.radius))
top_line = ((0,3*self.radius),(self.width,3*self.radius))
self.draw_lines([top_line, bottom_line],line_colour=(60,60,60))
if not self.removecircles:
self.draw_lines(self.get_connections_to_source_sink(),line_colour=(0,255,0))
def get_connections_to_source_sink(self):
connections = []
for x,y in self.circles:
if y<4*self.radius:
connections.append((self.source,(x,y)))
elif y>height-4*self.radius:
connections.append((self.sink,(x,y)))
return connections
def get_caption(self):
return "flow %s, circles removes %s" %(self.flowValue,len(self.removable_circles))
time_per_simulation = 5 #5 seconds
width, height = 1400, 600
background_colour = (255,255,255)
screen = pygame.display.set_mode((width, height))
screen.fill(background_colour)
from pygame.locals import USEREVENT
pygame.time.set_timer(USEREVENT+1,time_per_simulation*1000)
simulations = 0
simulations_max = 20
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
if event.type == USEREVENT+1:
if simulations % 2 ==0:
world = CirclesThing(width,height,120) #new world
else:
world.removecircles = True #current world without green circles
screen.fill(background_colour)
world.display()
pygame.display.set_caption(world.get_caption())
pygame.display.flip()
if simulations>=2*simulations_max:
running = False
simulations+=1
if False:
pygame.image.save(screen,'sim%s.bmp'%simulations)
1つのオプションは、最初に、オーバーラップまたはタッチの数が最も多い円を削除することです。削除するたびに、解決策があるかどうかを確認します。解決しない場合は、削除を続行します。
var circle;
circle = findMostOverlapCircle();
while(circle != null) {
circle.remove();
circle = findMostOverlapCircle();
}