找到一个算法来赢得这场打击犯罪的战斗

A crime committed in a city and the suspect starts to run away. A map of the city is given. At the moment, there are some police cars at some given places and they try to stop the suspect. The car of police and the suspect have a same maximum speed. The suspect can only pass a point if he reaches it earlier than any police car. There are several exits in the map, and the suspect evades if he reaches any of them. Find an algorithm allocating the police cars so that no path can the suspect take to evade.

For example, below is a possible city map.

enter image description here

White circle is where the suspect starts, black circles are police cars, and little squares are exits. In this situation, suspect can be stopped. A possible plan is police car A goes to A', B stays and C goes to C'.


An equivalent description of my problem could be:

A chemical factory (marked by the white circle) explodes and poisonous fluid starts to flow at each possible direction at speed v, and the rescue teams (marked by black circles) whose maximum speed is also v are trying to block it. The little squares are villagers they are protecting.


My Thoughts

If we have n police cars, a highly inefficient approach is to list all possible k-element subsets P of vertices such that:

a) k <= n;

b) Remove all vertices in P in the map will cause any exit unreachable to the suspect;

c) Remove any proper subset of P will let at least one exit reachable to the suspect.

Then we can easily determine if every vertex in P can be covered by a police no later than the suspect.

But how do I list all the possible Ps?


@Lior Kogan:

Look at this map:

enter image description here

If it is a turning game in which both sides knowing other's strategy, the police will win because he can just guard the side where the suspect go.

But in my problem, the police loses because he'll never know which side the suspect may choose.

#0

Edit2: Based on your clarifications:

I couldn't find any research concerning the exact posed problem.

Another close subject is virus spread and inoculation in networks. Here are some papers:

I think that the posed problem is very interesting. Though I believe it is NP-hard.

Sorry for being unable to help any further.

--

Edit1: Changed from Cops and Robbers game to Graph guarding game.

New answer:

This is a variant of the Graph Guarding game.

A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the agents and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges.

See: Guard Games on Graphs and How to Guard a Graph?

In your variant, there are two differences:

  • You are trying to guard more than one area
  • Each guarded area is a single node

--

Original answer:

This is a variant of the well studied Cops and Robbers game.

The Cops and Robbers game is played on undirected graphs where a group of cops tries to catch a robber. The game was defined independently by Winkler-Nowakowski and Quilliot in the 1980s and since that time has been studied intensively. Despite of that, its computation complexity is still an open question.

The problem of determining if k cops can capture a robber on an undirected graph, as well as the problem of computing the minimum number of cops that can catch a robber on a given graph were proven to be NP-hard.

Here are some resources:

#1

Now I have a clearer view of my problem. Although simpler than the Cops and Robbers Game or Graph Guarding game, it is nevertheless an NP-hard problem.

Two separate tasks this problem can actually be divided into:

Task a) Find a possible set of vertices that cuts the suspect unreachable to any exits.
Task b) Validate if this set of vertices can be all in-timely covered by police cars.

Now we are going to prove that Task a) is NP-complete.

First we consider when there is only one exit. Look at this simple map:

enter image description here

Assign False to a vertex if it is blocked by police and True if it's passable. We know that the suspect can evade if A & (B | D) & C == True. Now we clearly see that Task a) is equivalent to the famous NP-complete Boolean satisfiability problem.

If we have several exits, simply create several boolean expressions and connect them with AND(&).

Task b) is simply a bipartite graph matching problem, can be easily solved by Hungarian algorithm. It's time complexity is O(n^4).

So this whole problem is an NP-hard.

推荐文章

jQuery原型的继承部分失败

jQuery原型的继承部分失败

推荐文章

用Perl一行代码重新排序列

用Perl一行代码重新排序列

推荐文章

如何防止JComboBox下拉列表超过垂直屏幕大小

如何防止JComboBox下拉列表超过垂直屏幕大小

推荐文章

插件的评论对新的facebook账户不起作用

插件的评论对新的facebook账户不起作用

推荐文章

获取对ASP.NETweb.config文件自定义错误部分

获取对ASP.NETweb.config文件自定义错误部分

推荐文章

编译器指令-Delphi版本

编译器指令-Delphi版本

推荐文章

用ZBar委托方法实现视图的模块化表示

用ZBar委托方法实现视图的模块化表示

推荐文章

UIImageView是否缓存映像?

UIImageView是否缓存映像?

推荐文章

在squirrelsql中调试SQL查询

在squirrelsql中调试SQL查询

推荐文章

从codebhind向datagrid字段转换器发送多个值

从codebhind向datagrid字段转换器发送多个值

推荐文章

什么是javascript中的mvc

什么是javascript中的mvc

推荐文章

Spring应用程序上下文外部属性?

Spring应用程序上下文外部属性?

推荐文章

Modernizr不给CSS渐变添加前缀

Modernizr不给CSS渐变添加前缀

推荐文章

语言检测

语言检测

推荐文章

将param传递给javaandroid类

将param传递给javaandroid类

推荐文章

如何使用apachepoi在ppt中跨多张幻灯片拆分长表

如何使用apachepoi在ppt中跨多张幻灯片拆分长表